deleteMin appears to be O(n); not O(log(n)) as expected from a balanced binary tree.

[glycerine]

deleteMin calls remoteAt(0). This code

https://github.com/google/btree/blob/master/btree.go#L153

makes it look like every deleteMin will therefore be O(n) in the size of the tree n, as it does a full copy of the entire tree.

This is really, really, not what I would expect from a balanced binary tree implementation. Deleting the entire tree becomes an O(n*n) operation.

[gconnell]

Incorrect, but I can see how you got there. :)

The items field is used to store items within a single node. The https://github.com/google/btree/blob/master/btree.go#L153 function removes an element from that node. items will have a length determined by the degree of the tree, so the function will run in O(degree), not O(n).

The actual delete (and associated O(logn) tree traversal) is at https://github.com/google/btree/blob/master/btree.go#L380. It does an O(logn) to find the node, then the O(degree) to remove from that node's items list.

[glycerine]

Whew.