Binary Search Trees/ADT

This page covers an abstract data type (or, a generic interface for a data container) for binary search trees. These are trees (directed acyclic graphs) that follow a particular convention or interface, and provide certain basic functions. See Trees/ADT or Binary Trees/ADT for other, related tree-based abstract data types.

See also BinarySearchTree class here: https://charlesreid1.com:3000/cs/java/src/master/trees/search-trees/Weiss.java

or LinkedBinTree here: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java

Trees

Binary trees should follow the basic tree ADT and implement:

• size
• isempty

Further:

• iterable
• depth
• height

Utility methods (confusing, b/c using Tree, but checking Node...)

• isInternal
• isExternal
• isLeaf
• isRoot
• parent
• children
• numberOfChildren

Trees:

• allPositions
• iterator

Some of these can be left out, particularly in a trimmed-down binary tree.

Binary Trees

The binary tree implementation can replace the children functionality with a left and right. See Binary_Trees/ADT, which we follow here.

Node class provides two methods to access two children:

• left/getLeft
• right/getRight

Additional:

• sibling
• parent

Support iteration:

• positions() should return all positions in tree
• iter() should make it iterable

Trimming Down

To really trim things down, our binary search tree only implements a few methods, so we can focus on the actual search tree organization.

The minimal methods for a binary search tree are:

• insert
• remove
• contains/find

Optionally:

• findMin/findMax

These are "easiest" to implement recursively (and usually, easiest to handle the empty case separately.)