A Concise Introduction to Data Structures using Java

Chapter 9

Binary Search Trees

The next several chapters focus on data structures that provide fast search, insertion, and deletion. Binary search trees generally give very good performance on all three of these operations. Recall from Section 8.1 that we assume binary search trees do not contain duplicate elements.

Table 9.1 lists the public API of the the BinarySearchTree class.

Table 9.1

Binary Search Tree API

void add(E item) Adds item to tree if not already present.

boolean contains(E item) True if item is in tree.

E min() Returns smallest item in tree.

E max() Returns largest item in tree.

E pred(E item) Returns inorder predecessor of item in tree.

boolean remove(E item) True if item is found and removed from tree.