Binary Search Tree - 2
A Binary Search Tree (BST) is a fundamental hierarchical data structure used extensively in computer science to manage sorted data efficiently. It is a specialized version of a binary tree that maintains a specific ordering property, making it highly effective for operations like searching, insertion, and deletion.
The defining characteristic of a Binary Search Tree is the relationship between a node and its children. For any given node $x$ in the tree:
- All nodes in the left subtree of $x$ must have key values strictly less than the key of $x$.
- All nodes in the right subtree of $x$ must have key values strictly greater than the key of $x$.
If a system allows for duplicate keys, a consistent rule must be established—for instance, deciding that all duplicate values will always be placed in the left subtree.
The most significant consequence of this property is that an in-order traversal of a BST will always yield a sequence of keys in ascending order. This makes the BST an ideal structure for implementing dynamic sets, dictionaries, and performing efficient range queries.
Node Structure and Representation
At its simplest level, a node in a BST consists of three components: the stored key, a pointer to the left child, and a pointer to the right child.
In Python, a typical implementation of a node looks like this:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
To visualize how a BST is constructed, consider inserting the following sequence of keys: 8, 3, 10, 1, 6, 14, 4, 7, 13. The resulting tree structure would look like this:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
If we perform an in-order traversal on this tree, we get the sorted sequence: 1, 3, 4, 6, 7, 8, 10, 13, 14.
Core Operations
The efficiency of a BST is tied to its height ($h$). Most operations involve traversing a single path from the root down toward the leaves.
1. Searching
To find a specific key, we start at the root and compare the target value with the current node's key:
- If the target matches the current key, the search is successful.
- If the target is smaller, we move to the left child.
- If the target is larger, we move to the right child.
- If we reach a
None(null) pointer, the key does not exist in the tree.
The time complexity for searching is $O(h)$.
2. Insertion
Insertion follows a logic similar to searching. We traverse the tree to find the appropriate empty spot (a None position) where the new key maintains the BST property. Once the correct location is found, a new node is attached to the parent.
def insert(self, key):
if not self.root:
self.root = TreeNode(key)
return
cur = self.root
while True:
if key < cur.key:
if not cur.left:
cur.left = TreeNode(key)
return
cur = cur.left
elif key > cur.key:
if not cur.right:
cur.right = TreeNode(key)
return
cur = cur.right
else:
return # Duplicate keys are not inserted in this implementation
3. Deletion
Deletion is the most complex operation because it must preserve the BST property after the node is removed. There are three distinct scenarios:
- Case 1: The node is a leaf. We simply remove the node and set the parent's corresponding pointer to
None. - Case 2: The node has one child. We "bypass" the node by connecting its parent directly to its child.
- Case 3: The node has two children. We cannot simply remove the node without breaking the structure. Instead, we find the in-order successor (the smallest node in the right subtree). We copy the successor's value to the target node and then delete the successor node. Since the successor is the minimum in its subtree, it is guaranteed to have at most one child, making its removal straightforward.
Tree Traversals
Depending on the application, we may need to visit nodes in different orders:
- In-order (Left, Root, Right): Produces keys in sorted ascending order.
- Pre-order (Root, Left, Right): Useful for creating a copy of the tree structure.
- Post-order (Left, Right, Root): Often used for deleting trees or evaluating expression trees (processing children before the parent).
- Level-order (Breadth-First): Visits nodes level by level, typically implemented using a queue.
Complexity and the Importance of Balance
The performance of a BST is highly dependent on its shape.
In an ideal (balanced) scenario, the tree height is logarithmic relative to the number of nodes, $h \approx \log n$. In this case, search, insertion, and deletion all perform at $O(\log n)$.
However, if keys are inserted in a sorted or nearly sorted order (e.g., 1, 2, 3, 4, 5), the tree becomes skewed, essentially turning into a linked list. In this "degenerate" state, the height $h$ becomes $n$, and the time complexity for all operations degrades to $O(n)$.
To prevent this degradation, production-grade systems use Self-Balancing Binary Search Trees, such as AVL Trees or Red-Black Trees. These structures perform "rotations" during insertion and deletion to ensure the tree remains approximately balanced, guaranteeing $O(\log n)$ performance even in the worst-case scenarios.
Implementation Summary
Below is a complete, simplified implementation of a BST:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = TreeNode(key)
return
cur = self.root
while True:
if key < cur.key:
if not cur.left:
cur.left = TreeNode(key)
return
cur = cur.left
elif key > cur.key:
if not cur.right:
cur.right = TreeNode(key)
return
cur = cur.right
else:
return
def search(self, key):
cur = self.root
while cur:
if key == cur.key:
return True
cur = cur.left if key < cur.key else cur.right
return False
def inorder(self, node):
if node:
self.inorder(node.left)
print(node.key, end=' ')
self.inorder(node.right)
# Usage Example
bst = BST()
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst.insert(k)
print("In-order traversal:")
bst.inorder(bst.root) # Output: 1 3 4 6 7 8 10 13 14
print(f"\nSearch for 6: {bst.search(6)}") # Output: True
print(f"Search for 5: {bst.search(5)}") # Output: False