A Practical Guide to Data Structures and Algorithms using Java

OrderedCollection

Chapter 33

Balanced Binary Search Trees

AbstractCollection<E> implements Collection<E>

↑

AbstractSearchTree<E> implements OrderedCollection<E>

↑

BinarySearchTree<E> implements OrderedCollection<E>, Tracked<E>

↑

BalancedBinarySearchTree<E> implements OrderedCollection<E>, Tracked<E>

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