ABSTRACT

In this chapter we introduce an abstract class for a balanced binary search tree, which we later extend for both RedBlackTree (Chapter 34) and SplayTree (Chapter 35). All forms of balanced search trees use rotations to maintain balance when one path to a leaf becomes “too much longer” than another. An interesting property of rotations is that no comparisons are needed. The structural changes made by rotations preserve INORDER, and consequently an inorder traversal produces the same sequence before and after a rotation is performed. Therefore, the iteration order, including the relative order for equivalent elements, is not changed by a rotation.