Balanced Search Trees

See also: Trees and Binary Search Trees

On the Binary Search Trees page we covered the use of a binary tree to store items in a sorted order. In the analysis of binary search trees, 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 binary search tree such that 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 actually getting to the insertion index takes O(N) time
• Stacks/queues: provide O(1) insert/remove, but no random access
• Priority queues: while these maintain data in a sorted order, like queues, they provide no random access