Binary Search Tree (Data Structure)

A Binary Search Tree (BST) is a binary tree where each node has a key, a value, and pointers to its left/right children as well as its parent. They are mainly used for efficient lookup of the stored values.

Representation

Each node satisfies the following property: given a node x with children l and r, l.key ≤ x.key and r.key ≥ x.key. It follows that this property also applies recursively to the children of the left and right sub-trees.

Usage

Traversal

The BST property allows us to traverse the elements in sorted order by following an inorder tree walk, which is done by recursively visiting the left child followed by getting the value of the current node, then recursively visiting the right child. Doing so visits every node in the tree in sorted order, so it takes [math]\displaystyle{ \Theta(n) }[/math] time.

Retrieval

We can retrieve an element from a BST by key in [math]\displaystyle{ \mathcal{O}(\text{log}_2 n) }[/math] time by checking if the key matches the key of the current node. If it does, return its value. If it doesn't, compare the searched key to the key of the current node. If it's less, set the current node to the left child. If it's greater, set the current node to the right child and repeat. If there is no valid current node, then the key is not in the BST.

We can retrieve the maximal element from a BST by following the right child repeatedly. This takes [math]\displaystyle{ \mathcal{O}(\text{log}_2 n) }[/math] time. The maximal element necessarily does not have a right sub-tree.

We can retrieve the minimal element from a BST by following the left child repeatedly. This takes [math]\displaystyle{ \mathcal{O}(\text{log}_2 n) }[/math] time. The minimal element necessarily does not have a left sub-tree.

We can retrieve the "successor" (next largest, i.e. smallest node that is still larger than the initial node) node from a BST by taking the minimum element of the element's right sub-tree (if it exists) and otherwise iterating up the tree from the element until we reach the first node whose left sub-tree contains the initial element. This takes [math]\displaystyle{ \mathcal{O}(\text{log}_2 n) }[/math] time.

Insertion and Deletion

To insert, start at the root and follow either the left or right child based on the inserted element's key until you hit the end of the tree. Then, insert the node.

To remove, there are 2 cases:

• If the element to remove has just a single child, simply replace the element with its child.
• If the element has 2 children, find its successor (minimal node in right sub-tree). If the successor is not a direct child of the removed node, replace the successor with its right child and set the successor's right child to the removed node's right child (we do to fix the "hole" that would be left when the successor later replaces the removed node). Finally, replace the parent with its successor and set the successor's left child to the removed node's left child.