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
Binary trees should follow the basic tree ADT and implement:
Utility methods (confusing, b/c using Tree, but checking Node...)
Some of these can be left out, particularly in a trimmed-down binary tree.
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:
- positions() should return all positions in tree
- iter() should make it iterable
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:
These are "easiest" to implement recursively (and usually, easiest to handle the empty case separately.)
TreesPart of Computer Science Notes
Series on Data Structures
Abstract data type: Trees/ADT
Preorder traversal: Trees/Preorder
Postorder traversal: Trees/Postorder
In-Order traversal: Binary Trees/Inorder
Breadth-First Search: BFS
Breadth-First Traversal: BFT
Depth-First Search: DFS
Depth-First Traversal: DFT
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT
Flags · Template:TreesFlagBase · e