VietMX Staff asked 4 years ago
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.
