A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children, it supports several operations common to any search tree such as search, insert and delete. Operations on a BST always start at the root node and work their way down, because of this they take time based on how high the tree is. For example a tree with n nodes where there are no right children will take \(O(n)\) time, a complete BST however (every level except the last is completely filled, with nodes on the last as left as possible) has the worst case time of \(O(\log n)\).
Complexity
| Operation | Average case | Worst case |
|---|---|---|
| Delete | \(O(\log n)\) | \(O(n)\) |
| Insert | \(O(\log n)\) | \(O(n)\) |
| Search | \(O(\log n)\) | \(O(n)\) |
| Space | \(O(n)\) | \(O(n)\) |
Representation
There are two main ways of representing a binary tree. The first is using node objects that have references to their children.
The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i + 1 and the index of the right being 2i + 2 where i is the index of the parent.
Properties
- For each node x, every value found in the left sub-tree of x is less than or equal to the value found in x.
- For each node x, every value found in the right sub-tree of x is greater than or equal to the value found in x.
Operations
Delete(n)
The delete operation looks at the root node and compares its value with n. If the node is equal to n then this node is selected for deletion, if n is less than the node it moves to the left node, if n is greater than the node it moves to the right now. This continues until a node has been selected for deletion.
When a node has been selected for deletion the tree needs to be reorganised depending on how many children the node being deleted had.
- If the node has no children then it is simply deleted.
- If the node has only a left child node then move the left child to the deleted node's position.
- If the node has only a right child node then move the right child to the deleted node's position.
- If the node has both children then the minimum node from the right sub-tree is moved to the deleted node's position. If the minimum node had a right child then it is moved into the minimum node's old position.
These images illustrate Delete(5) which has both left and right children.
Insert(n)
The insert operation first looks at the root node and compares its value with n. If n is less than the root node it moves to the left node, if n is greater than the root node it moves to the right node. This continues until the left or right children do not exist, then it is inserted in that position.
Search(n)
The search operation follows the same process as insert to find whether n exists.
Code
Here is a binary search tree implemented in Java.
public class BinarySearchTree {
private TreeNode root;
public BinarySearchTree() { }
public void insert(int key) {
if (root == null) {
root = new TreeNode(key);
return;
}
insert(key, root);
}
private void insert(int key, TreeNode node) {
if (node == null) {
node = new TreeNode(key);
return;
}
if (key < node.getKey()) {
if (node.leftExists())
insert(key, node.getLeft());
else
node.setLeft(new TreeNode(key));
}
if (key > node.getKey()) {
if (node.rightExists())
insert(key, node.getRight());
else
node.setRight(new TreeNode(key));
}
}
public void delete(int key) {
if (root == null)
return;
delete(key, root);
}
private void delete(int key, TreeNode node) {
if (key < node.getKey()) {
if (node.leftExists())
delete(key, node.getLeft());
if (node.getLeft().isDeleted())
node.setLeft(null);
return;
}
if (key > node.getKey()) {
if (node.rightExists())
delete(key, node.getRight());
if (node.getRight().isDeleted())
node.setRight(null);
return;
}
delete(node);
}
private void delete(TreeNode node) {
if (!(node.leftExists() || node.rightExists())) {
node.setDeleted(true);
return;
}
if (node.leftExists() && !node.rightExists()) {
node.setKey(node.getLeft().getKey());
if (node.getLeft().rightExists())
node.setRight(node.getLeft().getRight());
if (node.getLeft().leftExists())
node.setLeft(node.getLeft().getLeft());
else
node.setLeft(null);
return;
}
if (node.rightExists() && !node.leftExists()) {
node.setKey(node.getRight().getKey());
if (node.getRight().leftExists())
node.setLeft(node.getLeft().getLeft());
if (node.getRight().rightExists())
node.setRight(node.getLeft().getRight());
else
node.setRight(null);
return;
}
// both exist, replace with minimum from right sub-tree
int min = findMin(node.getRight());
node.setKey(min);
}
private int findMin(TreeNode node) {
if (!node.leftExists()) {
node.setDeleted(true);
return node.getKey();
}
int min = findMin(node.getLeft());
if (node.getLeft().isDeleted())
node.setLeft(null);
return min;
}
public boolean search(int key) {
if (root == null)
return false;
return search(key, root);
}
private boolean search(int key, TreeNode node) {
if (key == node.getKey())
return true;
if (key < node.getKey()) {
if (!node.leftExists())
return false;
return search(key, node.getLeft());
}
if (key > node.getKey()) {
if (!node.rightExists())
return false;
return search(key, node.getRight());
}
return false;
}
public String toString() {
return root.toString();
}
}