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
• Hash tables: O(1) insertion and deletion, but not in sorted order
• Sorted hash tables: now we are starting to get closer to a key-value tree, or a structure that maintains key-value pairs in sorted order

Reviewing what we know about binary search trees:

• Binary trees are trees with the property that each node has at most two children. (Left precedes right.)
• A proper binary tree is a binary tree in which each node has 0 or 2 children.
• A full binary tree is a binary tree in which each level of the tree is completely full.
• Properties of binary trees, and full binary trees
• Height is between log(n+1)-1 and n-1
• Number of external nodes = number of internal nodes + 1
• Performance:
  • O(1) left/right, sibling/child, number of children, parent
  • O(c) to get children(p), where c is number of children
  • O(d + 1) depth of position p (where d is depth of position p)
  • O(N) height
  • O(1) add root, add left, add right, replace, delete
  • O(N) tree traversal (in order, pre-order, post-order) (breadth-first, depth-first)