17.1. Binary Search Trees¶
17.1.1. Binary Search Tree Definition¶
A binary search tree (BST) is a binary tree that conforms to the following condition, known as the binary search tree property:
All nodes stored in the left subtree of a node whose key value is \(K\) have key values less than or equal to \(K\).
All nodes stored in the right subtree of a node whose key value is \(K\) have key values greater than \(K\).
Figure 17.1.1 shows two BSTs for a collection of values. One consequence of the binary search tree property is that if the BST nodes are printed using an inorder traversal, then the resulting enumeration will be in sorted order from lowest to highest.
Figure 17.1.1: Two Binary Search Trees for a collection of values. Tree (a) results if values are inserted in the order 37, 24, 42, 7, 2, 42, 40, 32, 120. Tree (b) results if the same values are inserted in the order 120, 42, 42, 7, 2, 32, 37, 24, 40.
Below is a partial class declaration for a Binary Search Tree.
Note
We will cover other methods in the BinarySearchTree class in following sections.
public class BinarySearchTree<T extends Comparable<T>> {
private BinaryTreeNode<T> root;
public BinarySearchTree() {
root = null;
}
// Inserts a value into the BST
public void insert(T value) {
root = insert(root, value);
}
private BinaryTreeNode<T> insert(BinaryTreeNode<T> node, T value) {
// Base case: node is null - create a node to
// hold the new value and return it
if (node == null) {
return new BinaryTreeNode<T>(value);
}
// Recursive case 1: the new value is less than the value in
// node. Recurse on the left subtree
if(value.compareTo(node.getValue()) < 0) {
node.setLeft(insert(node.getLeft(), value));
}
// Recursive case 2: the new value is greater than or equal to the
// value in node. Recurse on the right subtree
else {
node.setRight(insert(node.getRight(), value));
}
return node;
}
17.1.2. BST insert()¶
We first look at how to insert a new node into a Binary Search Tree.
Note that, except for the last node in the path, the recursive call to
insert() will not actually change the child pointer for any of the
nodes that are visited.
In that sense, many of the assignments seem redundant.
However, the cost of these additional assignments is worth paying to
keep the insertion process simple.
The alternative is to check if a given assignment is necessary, which
is probably more expensive than the assignment!
The shape of a BST depends on the order in which elements are inserted. A new element is added to the BST as a new leaf node, potentially increasing the depth of the tree. Figure 17.1.1 illustrates two BSTs for a collection of values. It is possible for the BST containing \(n\) nodes to be a chain of nodes with height \(n\). This would happen if, for example, all elements were inserted in sorted order. In general, it is preferable for a BST to be as shallow as possible. This keeps the average cost of a BST operation low.