🌳 Binary Search Tree (BST)

• Overview and Fundamental Properties: Definition, historical background, and core structural characteristics.
• Complexity Analysis: Time complexities for average and worst-case scenarios across operations.
• Basic Operations: Detailed breakdown of searching (recursive, iterative, successor, predecessor), insertion, and deletion.
• Tree Traversal: Inorder, preorder, and postorder tree walks.
• Balanced Binary Search Trees: Need for rebalancing, height-balanced trees, weight-balanced trees, and popular variants.
• Applications: Usage in sorting algorithms and priority queue implementations.

---

💡 Overview

In computer science, a binary search tree (BST)—also called an ordered or sorted binary tree—is a rooted binary tree data structure.

Core Properties

• The key of each internal node is greater than all the keys in its respective left subtree.
• The key of each internal node is less than all the keys in its respective right subtree.
• Nodes are arranged in a strict total order, satisfying the binary search property.

Historical Context

• Devised in the 1960s for the efficient storage of labeled data.
• Attributed to Conway Berners-Lee and David Wheeler.

Advantages & Performance Dependency

• Allows binary search for fast lookup, addition, and removal of data items.
• Each comparison skips about half of the remaining tree, making lookup performance proportional to the binary logarithm.
• Performance depends on the order of insertion: Arbitrary insertions may lead to degeneracy (forming a structure resembling a singly linked list), which degrades worst-case performance to linear search time.

---

📊 Complexity Analysis

Operation	Average Case	Worst Case (Unbalanced)	Worst Case (Balanced)
Search	$\Theta(\log n)$	$O(n)$	$O(\log n)$
Insertion	$\Theta(\log n)$	$O(n)$	$O(\log n)$
Deletion	$\Theta(\log n)$	$O(n)$	$O(\log n)$

Key Takeaway: While standard BSTs can degrade to $O(n)$ like a singly linked list due to arbitrary insertions and deletions, self-balancing variants bound the worst lookup complexity to binary logarithmic time.

---

⚙️ Core Operations

Operations such as insertion and deletion cause the BST representation to change dynamically while maintaining the core BST properties.

1. Searching

Searching begins by examining the root node and proceeds recursively or iteratively:

• If the tree is nil, the key does not exist.
• If the key equals the root's key, the search is successful.
• If the key is less than the root, examine the left subtree.
• If the key is greater than the root, examine the right subtree.

Search Implementation Variations

• Recursive Search: Continues recursively until a nil or the target key is encountered.
• Iterative Search: Unrolls the recursive version into a while loop (found to be more efficient on most machines).

Successor and Predecessor

Assuming all keys in a BST are distinct:

• Successor of node $x$: The node with the smallest key greater than $x$'s key.
• Predecessor of node $x$: The node with the largest key smaller than $x$'s key.
• Finding minimum and maximum keys is a critical prerequisite for determining node successors and predecessors.

---

2. Insertion

• New nodes are always inserted as leaf nodes in the BST.
• The insertion procedure maintains a trailing pointer $y$ as the parent of $x$.
• If $y$ is nil, the BST is empty, and the new node $z$ becomes the root. Otherwise, keys are compared against $y$ to place $z$ correctly.

---

3. Deletion

Deleting a node $Z$ from a BST involves three primary cases:

1. Case 1: $Z$ is a leaf node
   • $Z$ is simply replaced by NIL.
2. Case 2: $Z$ has only one child
   • The child node gets elevated by modifying $Z$'s parent to point to the child, taking $Z$'s position in the tree.
3. Case 3: $Z$ has both left and right children
   • The in-order successor of $Z$ (let's call it $Y$) displaces $Z$:
     • If $Y$ is $Z$'s right child: $Y$ displaces $Z$, and $Y$'s right child remains unchanged.
     • If $Y$ is in $Z$'s right subtree but not its immediate right child: $Y$ first gets replaced by its own right child, and then displaces $Z$'s position in the tree.
   • Alternative: The in-order predecessor can be used instead.

Implementation Note: The BST-Delete procedure handles these three cases using the helper function Shift-Nodes, which replaces node $u$ with node $v$ within the BST.

---

🚶 Traversal Algorithms

A BST can be traversed using three basic tree-walk algorithms:

• Inorder Tree Walk:
  • Visit left subtree $\rightarrow$ Root node $\rightarrow$ Right subtree.
  • Result: Visits all nodes in non-decreasing key sequence.
• Preorder Tree Walk:
  • Visit Root node $\rightarrow$ Left subtree $\rightarrow$ Right subtree.
• Postorder Tree Walk:
  • Visit Left subtree $\rightarrow$ Right subtree $\rightarrow$ Root node.

---

⚖️ Balanced Binary Search Trees

Without rebalancing, arbitrary insertions/deletions lead to tree degeneration (height $n$), degrading performance to a linear search. Maintaining a height-bounded by $O(\log n)$ is critical.

Classification of Balanced Trees

Balance Type	Core Mechanism / Criterion	Examples
Height-Balanced	Heights of the left and right subtrees are guaranteed to be related by a constant factor. Every insert/delete observes and corrects heights along the root-to-leaf path.	AVL trees, Red-black trees
Weight-Balanced	Balanced based on the number of leaves in subtrees. Left and right subtree weights differ by at most a ratio $\alpha$ ($\alpha$-weight-balanced trees).	Weight-balanced trees

Popular Self-Balanced BST Variants

• T-tree
• Treap
• Red-black tree
• B-tree
• 2–3 tree
• Splay tree

---

📱 Applications of BSTs

1. Sorting (Tree Sort)

• Binary search trees are used in sorting algorithms.
• Elements are inserted all at once, and the tree is traversed in an in-order fashion to retrieve sorted data.
• Also utilized within algorithms like quicksort.

2. Priority Queue Operations

• BSTs can implement priority queues by using a node's key as its priority.
• Adding elements: Follows standard BST insertion.
• Removing elements: Depends on priority queue ordering:
  • Ascending order priority queue: Removal of the element with the lowest priority via leftward traversal.
  • Descending order priority queue: Removal of the element with the highest priority via rightward traversal.