From charlesreid1

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.)






Flags