Data Structures and the Java Collections Framework, Third Edition

CHAPTER 10

Binary Search Trees

In Chapter 9, you studied an important conceptual tool: the binary tree. This chapter presents the binary search tree data type and a corresponding data structure, the BinarySearchTree class. BinarySearchTree objects are valuable collections because they require only logarithmic time, on average, for inserting, removing, and searching (but linear time in the worst case). This performance is far better than the linear average-case time for insertions, removals and searches in an array, ArrayList or LinkedList object. For example, if n = 1,000,000,000, log₂ n < 30.

The BinarySearchTree class is not part of the Java Collections Framework. The reason for this omission is that the framework already includes the TreeSet class, which boasts logarithmic time for inserting, removing, and searching even in the worst case. The BinarySearchTree class requires linear-in-n time, in the worst case, for those three operations. So the BinarySearchTree class should be viewed as a "toy" class that is simple enough for you to play with and will help you to better understand the TreeSet class. The implementation of the TreeSet class is based on a kind of "balanced" binary search tree, namely, the red-black tree.

To further prepare you for the study of red-black trees and the TreeSet class, this chapter also explains what it means to say that a binary search tree is balanced. To add some substance to that discussion, we introduce the AVL tree data type, which is somewhat ...