Balanced binary tree · Introduction to red-black tree · B-Tree: Need…
Open in the Padhaiko app5.4 Balanced binary tree
5.4.1 Problem with unbalanced binary trees
A standard Binary Search Tree (BST) offers an average-case search, insertion, and deletion time complexity of when keys are inserted in random order. However, its topology depends entirely on the sequence of incoming keys:
- Worst-case Skewing: When keys are inserted in sorted order (e.g., ) or reverse sorted order, every new node is attached exclusively as a right (or left) child.
- Degeneration into Linear List: The tree degenerates into a single-chain skewed binary tree with height .
- Performance Collapse: All basic operations—search, insertion, and deletion—collapse from to , entirely negating the algorithmic advantages of the binary tree structure.
| Operation / Metric | Balanced BST () | Unbalanced Skewed BST () | Impact of Degeneration |
|---|---|---|---|
| Search Time | Linear scan through all nodes | ||
| Insertion Time | Must traverse entire chain to insert | ||
| Deletion Time | Worst-case linear pointer shifts | ||
| Height for nodes | comparisons | comparisons | Over slower |
5.4.2 Balanced binary search tree
Balanced Binary Search Tree
A balanced binary search tree is a binary search tree designed with self-adjusting mechanisms (such as tree rotations or colorings) that automatically preserve a height bound of following every insertion and deletion, guaranteeing logarithmic worst-case search and update time.
The Balance Factor
Balance is evaluated using the Balance Factor (), defined for any node as:
(By convention, the height of an empty subtree is defined as , and a single-node leaf subtree has height .)
A node is considered balanced if:
5.4.3 AVL tree, definition and need of AVL tree, construction of AVL tree: Insertion, deletion on AVL tree and rotation operations
AVL Tree
An AVL tree (named after its inventors G.M. Adelson-Velsky and E.M. Landis, 1962) is a self-balancing binary search tree in which the balance factor of every node is strictly restricted to the set .
If an insertion or deletion causes the balance factor of any node to become or , the tree is rebalanced by executing tree rotations at the lowest unbalanced ancestor node.
Height Upper Bound and Minimum Nodes
- The maximum height of an AVL tree containing nodes is bounded by:
- The minimum number of nodes required to construct an AVL tree of height satisfies a Fibonacci-like recurrence:
with base conditions and .
The Four AVL Rotation Operations
Rebalancing is performed using four canonical rotations classified by the path from the unbalanced node () to the newly inserted descendant node.
| Rotation Name | Imbalance Condition | Triggering Insertion Path | Action Taken to Restore Balance |
|---|---|---|---|
| LL Rotation | , | Left subtree of left child | Single Right Rotation on node |
| RR Rotation | , | Right subtree of right child | Single Left Rotation on node |
| LR Rotation | , | Right subtree of left child | Double Rotation: Left rotate child , then Right rotate node |
| RL Rotation | , | Left subtree of right child | Double Rotation: Right rotate child , then Left rotate node |
1. Single Right Rotation (LL Rotation)
When node has and its left child has :
- Node becomes the new root of the subtree.
- becomes the right child of .
- The original right subtree of becomes the left subtree of .
A (+2) B (0)
/ \ / \
B (+1) T3 ==> C (0) A (0)
/ \ / \
C (0) T2 T2 T3
2. Single Left Rotation (RR Rotation)
When node has and its right child has :
- Node becomes the new root of the subtree.
- becomes the left child of .
- The original left subtree of becomes the right subtree of .
A (-2) B (0)
/ \ / \
T1 B (-1) ==> A (0) C (0)
/ \ / \
T2 C (0) T1 T2
3. Double Left-Right Rotation (LR Rotation)
When node has and left child has :
- Left rotate node with respect to its right child .
- Right rotate node with respect to node .
4. Double Right-Left Rotation (RL Rotation)
When node has and right child has :
- Right rotate node with respect to its left child .
- Left rotate node with respect to node .
5.5 Introduction to red-black tree
Red-Black Tree
A Red-Black Tree (RBT) is a self-balancing binary search tree in which each node stores an additional color attribute: either RED or BLACK. Balance is maintained through strict structural coloring rules that prevent any path from root to leaf from becoming more than twice as long as any other path.
While an AVL tree enforces more rigid balancing () and is therefore faster for lookup-intensive workloads, a Red-Black tree requires fewer rotations during insertions (at most 2 rotations) and deletions (at most 3 rotations). RBTs are the foundational data structure behind the C++ STL (std::map, std::set), Java TreeMap, and Linux kernel process schedulers (Completely Fair Scheduler).
The Five Mandatory Red-Black Properties
| Rule # | Property Name | Invariant Description |
|---|---|---|
| 1 | Node Color | Every node is colored either RED or BLACK. |
| 2 | Root Property | The root node is always BLACK. |
| 3 | Leaf Property | All leaves (NIL sentinel nodes) are BLACK. |
| 4 | Red Property | If a node is RED, both its children must be BLACK (no two consecutive red nodes on any path). |
| 5 | Black-Height | Every path from a given node down to any descendant leaf must contain the exact same number of black nodes (Black-Height, ). |
[ 20 (Black) ] <-- Root (Black)
/ \
[ 10 (Red) ] [ 30 (Black) ]
/ \ / \
[NIL(B)] [NIL(B)] [NIL(B)] [NIL(B)]
* Every path from root to NIL contains exactly 2 Black nodes (Black Height = 2)Consequence of Red-Black Properties
Because property 4 forbids two consecutive RED nodes, the shortest possible path from root to a leaf consists entirely of BLACK nodes (), while the longest possible path alternates strictly between RED and BLACK nodes (). Therefore:
This guarantees a maximum tree height of:
Insertion and Violation Handling
When a new key is inserted into a Red-Black tree:
- It is inserted at a leaf position following standard BST insertion.
- The newly inserted node is initially colored RED (to preserve property 5, black-height).
- If the parent is also RED, property 4 is violated (Double-Red Problem). The violation is resolved by examining the Uncle node (the sibling of the parent):
- Case 1 (Uncle is RED): Recoloring. Flip parent and uncle to BLACK, and grandparent to RED. Continue checking upward from grandparent.
- Case 2 (Uncle is BLACK, forming a Triangle): Rotate child to transform into a straight line (reducing to Case 3).
- Case 3 (Uncle is BLACK, forming a Line): Rotate grandparent and swap the colors of parent and grandparent.
5.6 B-Tree: Need, definition and construction of B-tree
Need for B-Trees in Disk-Based Storage
Binary search trees (BST, AVL, Red-Black) are internal memory (in-RAM) data structures:
- In RAM, each memory dereference takes only tens of nanoseconds.
- In massive databases and enterprise file systems (e.g. MySQL InnoDB, PostgreSQL, NTFS, ext4), datasets exceed available RAM by gigabytes or terabytes, residing on secondary disk storage (HDDs/SSDs).
- Disk access is mechanical/block-oriented: reading one disk block takes milliseconds (about slower than RAM).
- A binary tree storing items requires levels of height; traversing it sequentially would require up to separate random disk I/O operations per query.
Definition of B-Tree of Order
B-Tree of Order m
A B-Tree of order is a self-balancing, multi-way search tree satisfying:
- Every node has at most children and at most keys.
- Every internal node (except the root) has at least children and at least keys.
- The root has at least children if it is not a leaf node (and at least key).
- All leaf nodes appear at the exact same level (perfect balance).
- A non-leaf node with children contains keys sorted in ascending order: , serving as partition boundaries for its subtrees.
| Order () | Min Children (Internal) | Max Children () | Min Keys (Internal) | Max Keys () |
|---|---|---|---|---|
| (2-3 Tree) | ||||
| (2-3-4 Tree) | ||||
Construction and Insertion in a B-Tree
Insertions in a B-Tree always take place in a leaf node:
- Locate Target Leaf: Perform multi-way search to locate the leaf where the new key belongs.
- Insert into Leaf:
- If the leaf currently contains fewer than keys, insert the key in sorted order.
- Node Splitting (Overflow Handling):
- If the leaf already contains keys, inserting the new key causes an overflow ( keys).
- Find the median key at index (or ).
- The median key is promoted upward and inserted into the parent node.
- The remaining keys are split into two new sibling nodes: left child (keys before median) and right child (keys after median).
- If the parent node also overflows, splitting propagates recursively up the tree.
- If the root overflows, it splits into two nodes and a new root is created with the single promoted median key. A B-tree grows in height strictly at the root.
Worked Examples
1
Construct an AVL tree by sequentially inserting the keys: 10, 20, 30, 40, 50, 25. Show the balance factor for each node at every step, identify any imbalances, and show the exact rotations (RR, LL, RL) performed.
Insertions 10, 20, 30:
- Insert
10: Root, . - Insert
20: Right child of10. . - Insert
30: Right child of20. . Imbalance at node10(, right child ) RR Rotation (Single Left Rotation) around node10.
10 (-2) 20 (0)
\ / \
20 (-1) ==> 10 (0) 30 (0)
\
30 (0)Insertions 40, 50:
- Insert
40: Right child of30. . (Balanced) - Insert
50: Right child of40. . Imbalance at node30(, right child ) RR Rotation around node30.
20 (-1) 20 (-1)
/ \ / \
10 (0) 30 (-2) ==> 10 (0) 40 (0)
\ / \
40 (-1) 30 (0) 50 (0)
\
50 (0)Insertion of 25 (RL Rotation):
- Insert
25: Left child of30. Let us compute balance factors from the root:- Left subtree of
20: height 0 (node 10). - Right subtree of
20: height 2 (path ). - . Imbalance at root
20! - Right child
40: left subtree height 1 (nodes 30, 25), right subtree height 0 (node 50) . Imbalance condition: and RL Rotation (Double Right-Left Rotation).
- Left subtree of
- Right rotate right child
40around30:30moves up,25stays left child of30,40becomes right child of30. - Left rotate root
20around30:30becomes new root;20becomes left child with children10and25;40becomes right child with child50.
Final Balanced AVL Tree:
30 (0)
/ \
20 (0) 40 (0)
/ \ \
10 (0) 25 (0) 50 (0)
All balance factors are strictly 0 (or ). In-order traversal: 10, 20, 25, 30, 40, 50.
2
From the balanced AVL tree constructed in Example 1:
30
/ \
20 40
/ \ \
10 25 50
Trace the deletion of node 10. Show the resulting balance factor violations and the rotation performed to rebalance the tree.
Standard BST Deletion of Node 10: Node 10 is a leaf node. Set left child of 20 to NULL and free 10. Unbalanced intermediate tree:
30
/ \
20 40
\ \
25 50Evaluating Balance Factors along the Return Path:
- Node
20: left height , right height . (Balanced) - Root node
30:- Left subtree height (node 20, 25): .
- Right subtree height (node 40, 50): .
- . (Balanced)
Wait, let us check node 40: . The tree is already balanced without requiring an extra rotation! Now, if we subsequently delete node 25: Node 20 has height 0 (leaf). Left subtree of 30 has height 0. Right subtree of 30 has height 1 (still balanced).
Deleting leaf node 10 leaves node 20 with right child 25. Node 20 has , and root 30 has left height 1 and right height 1 (). Because all balance factors satisfy , the tree remains fully balanced with zero rotations required.
3
Construct a B-Tree of order (max 2 keys and 3 children per node) by sequentially inserting keys: 10, 20, 5, 6, 12, 30, 7, 17. Show the tree configuration after each node split and key promotion.
Insertions 10, 20, 5 (First Split):
- Insert
10:[10] - Insert
20:[10, 20](Node holds maximum 2 keys) - Insert
5: Node overflows to[5, 10, 20]. Median key is10. Promoted to form new root. Left child:[5], Right child:[20].
[ 10 ]
/ \
[ 5 ] [ 20 ]Insertions 6, 12, 30:
- Insert
6: Goes into left leaf[5]. - Insert
12: Goes into right leaf[20]. - Insert
30: Right leaf becomes[12, 20, 30](Overflow!). Median key20is promoted to root. Root becomes[10, 20]. Right leaves split into[12]and[30].
[ 10, 20 ]
/ | \
[ 5, 6 ] [ 12 ] [ 30 ]Insertions 7, 17:
- Insert
7: Left leaf[5, 6]overflows to[5, 6, 7]. Median6promoted to root. Root overflows: was[10, 20], now receives6(Root Overflow!). Median of root10promoted to create new root[10](tree height increases by 1). Root splits into left child[6]and right child[20]. - Insert
17: Goes into leaf node with12.
Final B-Tree of order 3:
[ 10 ]
/ \
[ 6 ] [ 20 ]
/ \ / \
[ 5 ] [ 7 ] [ 12, 17 ] [ 30 ]
All leaves are at the exact same level (Level 2). Every node contains between 1 and 2 keys.
4
Trace the insertion of keys 10, 20, 30, 15 into an initially empty Red-Black Tree. Show the color of every node (R or B) and explain any recoloring or rotation triggered by property violations.
Insert 10 and Insert 20:
- Insert
10: Placed as root. By Property 2 (Root Property), root must be BLACK:[10 (B)]. - Insert
20: Placed as right child of10. New nodes are inserted as RED:10 (B) -> 20 (R). Parent10is BLACK no violation.
Insert 30 (Double-Red Violation):
- Insert
30: Placed as right child of20, colored RED. Violation:20is RED and child30is RED (Property 4 violated!).- Check uncle of
30: left child of10isNIL(BLACK). - Shape:
10 (B) -> 20 (R) -> 30 (R)forms a straight right-leaning line (RR). - Resolution: Left rotate grandparent
10, and swap colors of parent20and grandparent10:20becomes root, colored BLACK.10becomes left child, colored RED.30stays right child, colored RED.
- Check uncle of
Insert 15 (Uncle RED Case):
- Insert
15: right child of10, colored RED. Violation:10is RED and15is RED.- Check uncle of
15: sibling of parent10is30, which is RED. - Resolution (Case 1: Uncle RED): Recolor parent
10to BLACK, uncle30to BLACK, and grandparent20to RED. - Fix root color: Grandparent
20is root, so recolor20back to BLACK (Property 2).
- Check uncle of
Final Red-Black Tree Configuration:
- Root:
20 (Black) - Left Child:
10 (Black)with Right Child15 (Red) - Right Child:
30 (Black)
Every path from root to NIL leaf passes through exactly 2 Black nodes (Black-Height = 2), satisfying all 5 Red-Black invariants.
Exercises
Exercise Questions: AVL, Red-Black & B-Trees
Why do standard binary search trees degenerate into search time? Explain how the AVL tree overcomes this limitation by defining its Balance Factor and the allowed range of values.
Cause of BST Degeneration: When keys are inserted in sorted or nearly sorted sequence, each subsequent node is attached in the same direction, creating a one-sided linear chain (skewed tree). The tree height grows to . Searching in a tree of height requires inspecting every node sequentially, degrading time complexity from to .
AVL Tree Solution and Balance Factor: An AVL tree guarantees by strictly enforcing a balance invariant after every insertion and deletion:
For every node in an AVL tree, the balance factor must satisfy:
If any operation creates , local tree rotations are immediately executed, restricting tree height to and guaranteeing worst-case search time.
Standard BSTs degenerate to height when keys arrive in sorted order. An AVL tree prevents this by requiring every node to have a Balance Factor , restoring balance via rotations so that height remains strictly bounded by .
Construct an AVL tree by sequentially inserting the keys: 21, 26, 30, 9, 4, 14, 28, 18. Specify the type of rotation (LL, RR, LR, RL) performed at each step where an imbalance occurs.
Tracing Insertions:
- Insert
21: Root (). - Insert
26: Right of21(). - Insert
30: Right of26. Imbalance at21RR Rotation.26becomes root, with left child21and right child30. - Insert
9: Left of21(). - Insert
4: Left of9. Imbalance at21LL Rotation around21.9becomes left child of26, with children4and21. - Insert
14: Right of9and left of21placed as left child of21. Tree remains balanced. - Insert
28: Left child of30. Balanced. - Insert
18: Placed as right child of14. Check balance factors: Subtree at9: left child4(height 0), right subtree21with left child14(which has right child18, height 2) . Right child21has left child14() RL Rotation around21or9.
The construction encounters three rotations:
- After inserting
30: RR Rotation around21 - After inserting
4: LL Rotation around21 - After inserting
18: RL Rotation around9
Final tree is balanced with height and all nodes satisfying .
Using the recurrence relation for the minimum number of nodes in an AVL tree of height :
with base cases and , compute the minimum number of nodes required to construct an AVL tree of height .
Evaluating the Recurrence Relation Step-by-Step:
- Base Case : (single node)
- Base Case : (root with 1 child)
- For :
- For :
- For :
- For :
The minimum number of nodes required to construct an AVL tree of height is nodes.
For a B-Tree of order :
- State the maximum and minimum number of keys in an internal node.
- State the maximum and minimum number of children for an internal node.
- Calculate the maximum number of keys that can be stored in the tree if its height is (levels 0, 1, 2).
Formulas for Order :
- Number of Keys in Internal Nodes (excluding root):
- Maximum keys:
- Minimum keys:
- Number of Children for Internal Nodes:
- Maximum children:
- Minimum children:
Maximum Keys for Height : When every node is maximally full with children and keys:
- Level 0 (Root): node keys.
- Level 1: nodes keys.
- Level 2: nodes keys.
Total maximum keys:
- Keys per internal node: Min = 2, Max = 4.
- Children per internal node: Min = 3, Max = 5.
- Maximum keys in tree of height : keys.
Explain why B-Trees are preferred over standard Binary Search Trees for secondary storage (disk) implementations in databases and file systems.
Key Architectural Differences:
| Feature | Binary Search Tree (BST/AVL) | B-Tree (Order ) |
|---|---|---|
| Node Capacity | 1 key, 2 child pointers | Hundreds of keys matching disk block size |
| Tree Geometry | Deep and narrow () | Extremely shallow and wide () |
| Disk I/O Frequency | High ( disk accesses) | Minimal (– disk accesses for millions of records) |
| Storage Block Alignment | Nodes do not align with disk pages | Each node corresponds directly to one disk block/page |
Core Advantage: Disk read latency is dominated by physical seek and rotational delays (measured in milliseconds). A B-tree node is sized to match a physical disk page (e.g., or ). A single disk read loads an entire node with hundreds of keys into RAM. Searching within the node in RAM is instantaneous (). As a result, B-trees drastically reduce physical disk I/O operations from dozens down to or .
B-Trees minimize expensive disk I/O by having a large branching factor , compressing tree height to 2–3 levels. Each B-Tree node fits into a single secondary storage disk page (4 KB–8 KB), allowing databases to access millions of records with only a few disk block reads.
Enumerate the five mandatory properties of a Red-Black tree. Prove why the longest path from the root to any leaf cannot exceed twice the length of the shortest path.
The Five Red-Black Properties:
- Every node is colored either RED or BLACK.
- The root node is always BLACK.
- All leaf nodes (
NILsentinels) are BLACK. - If a node is RED, both of its children must be BLACK (no two consecutive red nodes).
- For each node, all downward paths to descendant leaf nodes contain the same number of black nodes (Black-Height, ).
Proof of Height Bounding: Let be the black-height of the root node.
- By Property 5, every path from root to leaf has exactly black nodes.
- By Property 4, no path can contain two consecutive RED nodes. Therefore, RED nodes can only alternate with BLACK nodes.
- Shortest path: A path containing only BLACK nodes has length .
- Longest path: A path alternating strictly between RED and BLACK nodes has at most red nodes interspersed among black nodes, yielding a maximum path length of:
Thus, , ensuring the tree remains approximately balanced with height .
The five Red-Black properties guarantee that every path has identical black-height and no two red nodes are consecutive. Consequently, the shortest path has length (all black) and the longest path has length (alternating red-black), proving that the longest path never exceeds twice the shortest path.