Balanced Search Trees

Balanced Search Trees

Source: Skiena

Random search trees are usually good. But if we get unlucky with our order of insertion, we can end up with a linear-height tree in the worst case. This worst case is outside of our direct control, since we must build the tree in response to the requests given by our potentially nasty user.

What would be better is an insertion/deletion procedure which adjusts the tree a little after each insertion, keeping it close enough to be balanced so the maximum height is logarithmic. Sophisticated balanced binary search tree data structures have been developed that guarantee the height of the tree always to be O(log n). Therefore, all dictionary operations (insert, delete, query) take O(log n) time each. What are some implementations of balanced tree data structures? red-black trees and splay trees.

From an algorithm design viewpoint, it is important to know that these trees exist and that they can be used as black boxes to provide an efficient dictionary implementation. When figuring the costs of dictionary operations for algorithm analysis, we can assume the worst-case complexities of balanced binary trees to be a fair measure.

Stop and Think: Exploiting Balanced Search Trees

Problem: You are given the task of reading n numbers and then printing them out in sorted order. Suppose you have access to a balanced dictionary data struc- ture, which supports the operations search, insert, delete, minimum, maximum, successor, and predecessor each in O(log n) time.

1. How can you sort in O(n log n) time using only insert and in-order traversal?
2. How can you sort in O(n log n) time using only minimum, successor, and insert?
3. How can you sort in O(n log n) time using only minimum, insert, delete, search?

Solution: The first problem allows us to do insertion and inorder-traversal. We can build a search tree by inserting all n elements, then do a traversal to access the items in sorted order.

Sort1()

initialize-tree(t)
While (not EOF)
read(x);
insert(x,t)
Traverse(t)

Sort2()

initialize-tree(t)
While (not EOF)
read(x);
insert(x,t);
y = Minimum(t)
While (y  = NULL) do
print(y → item)
y = Successor(y,t)

Sort3()

initialize-tree(t)
While (not EOF)
read(x);
insert(x,t);
y = Minimum(t)
While (y  = NULL) do
print(y→item)
Delete(y,t)
y = Minimum(t)

The second problem allows us to use the minimum and successor operations after constructing the tree. We can start from the minimum element, and then repeatedly find the successor to traverse the elements in sorted order.

The third problem does not give us successor, but does allow us delete. We can repeatedly find and delete the minimum element to once again traverse all the elements in sorted order.

Each of these algorithms does a linear number of logarithmic-time operations, and hence runs in O(n log n) time. The key to exploiting balanced binary search trees is using them as black boxes.