Introduction to the Art of Programming Using Scala

Chapter 35

Augmenting Trees

Chapter 29 covered the basics of trees and how to use a binary search tree (BST) to implement the map Abstract Data Type (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)) ...