Binary Search Trees (BST)
A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtrees must also be binary search trees.
1. The Core Concept
This structure allows for fast lookup, addition, and removal of items. It works like a sorted list but with faster insertion/deletion.
- Root: The top node.
- Leaf: A node with no children.
2. Operations & Complexity
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | $O(\log n)$ | $O(n)$ |
| Insert | $O(\log n)$ | $O(n)$ |
| Delete | $O(\log n)$ | $O(n)$ |
- Average Case: Occurs when the tree is balanced (height is $\log n$).
- Worst Case: Occurs when the tree is skewed (essentially a linked list), e.g., inserting 1, 2, 3, 4, 5 in order.
3. Tree Traversal
Traversal is the process of visiting all the nodes in the tree.
In-Order (Left, Root, Right)
Visits nodes in ascending sorted order.
Left -> Root -> Right
Pre-Order (Root, Left, Right)
Useful for creating a copy of the tree.
Root -> Left -> Right
Post-Order (Left, Right, Root)
Useful for deleting the tree (delete children before parent).
Left -> Right -> Root
4. Implementation (Python)
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
def search(root, key):
if root is None or root.val == key:
return root
if root.val < key:
return search(root.right, key)
return search(root.left, key)5. Balanced BSTs
To avoid the $O(n)$ worst-case scenario, we use Self-Balancing Binary Search Trees. These trees automatically keep their height small (logarithmic) after insertions and deletions.
- AVL Trees: Strictly balanced.
- Red-Black Trees: Loosely balanced (faster insertion/deletion than AVL).
6. Tree Rotations
Tree rotations are operations that change the structure of a binary search tree without affecting the order of the elements. They are used to rebalance trees (like AVL or Red-Black trees).
- Left Rotation: Moves a node down to the left and its right child up.
- Right Rotation: Moves a node down to the right and its left child up.
Rotations are $O(1)$ operations because they only involve changing a few pointers.
programming/algorithms programming/graph-theory-basics programming/arrays-vs-linked-lists