ABSTRACT
Chapter 16 covered the basics of trees and how to use a binary search tree (BST) to implement the map ADT. This implementation gave us the possibility of O(log(n)) performance for all the operations on that ADT. Unfortunately, it also allowed the possibility of O(n) performance if the tree were built in a way that made it unbalanced. In this chapter we will see how we can fix that flaw by adding a bit more data to nodes and using the data to tell us when things are out of balance so that operations can be performed to fix the situation. In addition, we will see how we can use a similar approach to let us use a tree as the storage mechanism behind a sequence ADT implementation that is O(log(n)) for direct access, inserting, and removing.
