Balanced Search Trees

See also: Trees and Binary Search Trees

In the analysis of binary search trees, we see that adding and removing from a search tree is O(h), where h is the height of the tree. In the worst case, the tree can have all nodes in the left or right subtree, and each node have one child, such that the height is n, and addition/removal is O(n).

Our goal is to design a data structure where we can *guarantee* O(log N) insertion and deletion.

Let's just recap some other data structures before we do so:

• Unsorted array: this is definitely out, since this is O(N) insertion and O(N) deletion
• Sorted array: we can find the insertion index of our new node in O(log N) time, but if we're inserting to the front of the array, it costs O(N) to move all the elements back
• Linked list: we can perform an O(1) insertion, but to get to where we are inserting can take O(N) time.