[meribold]

You don't need to compare the whole key most of the time. I think the amortized cost for a comparison is in O(1).

[sltkr]

Not in a balanced tree, since the further down the tree you go, the longer the shared prefix between the search key and node key becomes.

So the complexity becomes something like 1 + 2 + 3 + .. + log n = O(log^2 n).

[meribold]

Good point. Perhaps we could store the length of the common prefix from the last time we went left as well as from the last time we went right. The minimum of those two should remain a common prefix with the search key for the rest of the lookup and should therefore be safe to skip during subsequent comparisons.

[SilasX]

But that would actually help it because you can store how far down the match is by that point in the tree, and know how few digits you have to actually compare.