O'Reilly logo

A Concise Introduction to Data Structures using Java by Mark J. Johnson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required