If we implement a balanced binary search tree, we can always keep the cost of insert()
, delete()
, lookup()
to O(log n)
where n
is the number of nodes in the tree – so the benefit really is that lookups can be done in logarithmic time which matters a lot when n is large. This is much better than the linear time O(n)
required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.