Binary search tree

A binary search tree (BST) is a rooted binary tree data structure in which each internal node stores a key that is strictly greater than all the keys in its left subtree and strictly less than all the keys in its right subtree. This fundamental ordering property enables highly efficient algorithms for searching, inserting, and deleting elements, making the binary search tree a cornerstone data structure in computer science for implementing dynamic sets, lookup tables, and priority queues.

Properties

The structure of a binary search tree is defined by a set of strict mathematical and structural properties:

• Binary Structure: Every node in the tree has at most two children, referred to as the left child and the right child.
• Ordering Property: For any given node, all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater than the node's key.
• Recursive Definition: Both the left and right subtrees of any node must themselves be valid binary search trees.
• Uniqueness: In a standard binary search tree, all keys are distinct. However, some implementations allow duplicate keys by defining a consistent rule, such as placing duplicates in the right subtree.

These properties ensure that an in-order traversal of the tree will always yield the stored keys in a strictly ascending sorted order.

Operations

The primary operations performed on a binary search tree leverage its ordering property to navigate the structure efficiently.

Search

Searching for a specific key begins at the root node. If the tree is empty, the key does not exist. Otherwise, the target key is compared with the root's key. If they are equal, the search is successful. If the target key is less than the root's key, the search proceeds recursively or iteratively to the left subtree. If it is greater, the search proceeds to the right subtree. This process repeats until the key is found or a null pointer is reached, indicating the key is absent.

Insertion

Insertion follows the same traversal path as the search operation. The algorithm searches for the key to be inserted. If the key already exists, the operation may abort or update the associated value. If the key is not found, the search will inevitably terminate at a null link. A new node containing the key is then allocated and linked in place of the null pointer, maintaining the BST property.

Deletion

Deleting a node from a binary search tree is more complex and involves three distinct cases:

1. Deleting a leaf node: The node is simply removed from the tree, and its parent's corresponding child pointer is set to null.
2. Deleting a node with one child: The node is removed, and its single child is promoted to take its place, linking directly to the deleted node's parent.
3. Deleting a node with two children: The node cannot be simply removed without breaking the tree structure. Instead, its value is replaced by either its in-order successor (the smallest key in its right subtree) or its in-order predecessor (the largest key in its left subtree). The successor or predecessor node, which is guaranteed to have at most one child, is then deleted using the rules from case 1 or case 2.

Traversal

Binary search trees support standard tree traversals:

• In-order traversal: Visits the left subtree, the root, and then the right subtree. This yields the elements in sorted ascending order.
• Pre-order traversal: Visits the root, the left subtree, and then the right subtree. This is useful for creating a copy of the tree.
• Post-order traversal: Visits the left subtree, the right subtree, and then the root. This is commonly used to delete or free all nodes in the tree.

Time Complexity

The time complexity of binary search tree operations is directly proportional to the height of the tree ($h$).

• Best and Average Case: In a randomly built binary search tree, the expected height is $O(\log n)$, where $n$ is the number of nodes. Consequently, search, insertion, and deletion operations take $O(\log n)$ time on average.
• Worst Case: If elements are inserted in a sorted or nearly sorted order, the tree degenerates into a linear structure resembling a linked list. In this scenario, the height becomes $n$, and the time complexity for all primary operations degrades to $O(n)$.

To mitigate the worst-case scenario, computer scientists have developed self-balancing binary search trees, which automatically adjust their structure during insertions and deletions to guarantee a height of $O(\log n)$.

Self-Balancing Variants

Several variants of the binary search tree have been designed to maintain optimal height and ensure worst-case logarithmic time complexity:

• AVL Tree: The first self-balancing BST invented. It maintains the invariant that the heights of the two child subtrees of any node differ by at most one. Rebalancing is performed via tree rotations.
• Red-Black Tree: A widely used self-balancing BST where each node has an extra bit for denoting the color of the node, either red or black. It enforces balancing constraints through color properties and rotations, ensuring that the longest path from the root to a leaf is no more than twice as long as the shortest path. It is heavily utilized in standard library implementations, such as the C++ std::map and Java TreeMap.
• Splay Tree: A self-adjusting BST that moves recently accessed elements closer to the root through a process called splaying. While individual operations can take $O(n)$ time, any sequence of $m$ operations takes $O(m \log n)$ time, providing excellent amortized performance and fast access to frequently used elements.
• Treap: A randomized data structure that combines a binary search tree and a binary heap. Each node holds a key (obeying the BST property) and a randomly assigned priority (obeying the heap property). The random priorities ensure that the tree remains balanced with high probability.

Applications

Binary search trees are foundational to numerous computing applications:

• Dynamic Sets and Dictionaries: BSTs efficiently support the insertion, deletion, and lookup of key-value pairs, making them ideal for implementing dictionaries and associative arrays.
• Database Indexing: Variants like B-trees and B+ trees, which are generalized multi-way search trees derived from BST concepts, are the standard indexing structures in relational database management systems.
• Priority Queues: BSTs can function as priority queues, allowing for the efficient extraction of the minimum or maximum element, as well as the removal of arbitrary elements.
• Computational Geometry: BST variants, such as K-d trees and range trees, are used to organize points in multi-dimensional space for efficient spatial queries, like nearest neighbor searches and range reporting.
• Routing and Networking: Binary search trees and their derivatives are employed in network routers for IP address lookup and longest prefix matching.

Comparison with Other Data Structures

When compared to hash tables, binary search trees offer the distinct advantage of maintaining elements in sorted order, which allows for efficient range queries, finding the closest match, and ordered traversal. Hash tables, while offering $O(1)$ average time complexity for lookups, do not preserve order and suffer from $O(n)$ worst-case performance due to collisions.

Compared to sorted arrays, binary search trees provide much faster insertion and deletion times ($O(\log n)$ versus $O(n)$ for arrays, which require shifting elements). However, sorted arrays offer better cache locality and more compact memory usage, as binary search trees incur memory overhead for storing child pointers and require dynamic memory allocation for individual nodes.