PadhaikoAll subjects

Balanced binary tree · Introduction to red-black tree · B-Tree: Need…

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

5.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:

Standard BST vs Balanced BST Search Performance
Operation / MetricBalanced BST ()Unbalanced Skewed BST ()Impact of Degeneration
Search TimeLinear scan through all nodes
Insertion TimeMust traverse entire chain to insert
Deletion TimeWorst-case linear pointer shifts
Height for nodes comparisons comparisonsOver slower

5.4.2 Balanced binary search tree

Definition

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

Definition

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

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.

Classification of the Four AVL Rotations
Rotation NameImbalance ConditionTriggering Insertion PathAction Taken to Restore Balance
LL Rotation, Left subtree of left childSingle Right Rotation on node
RR Rotation, Right subtree of right childSingle Left Rotation on node
LR Rotation, Right subtree of left childDouble Rotation: Left rotate child , then Right rotate node
RL Rotation, Left subtree of right childDouble Rotation: Right rotate child , then Left rotate node

1. Single Right Rotation (LL Rotation)

When node has and its left child has :

         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 :

     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 :

  1. Left rotate node with respect to its right child .
  2. Right rotate node with respect to node .

4. Double Right-Left Rotation (RL Rotation)

When node has and right child has :

  1. Right rotate node with respect to its left child .
  2. Left rotate node with respect to node .

5.5 Introduction to red-black tree

Definition

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

The Five Defining Red-Black Properties
Rule #Property NameInvariant Description
1Node ColorEvery node is colored either RED or BLACK.
2Root PropertyThe root node is always BLACK.
3Leaf PropertyAll leaves (NIL sentinel nodes) are BLACK.
4Red PropertyIf a node is RED, both its children must be BLACK (no two consecutive red nodes on any path).
5Black-HeightEvery path from a given node down to any descendant leaf must contain the exact same number of black nodes (Black-Height, ).
Illustration of Red-Black Tree and Black HeightText
                  [ 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:

  1. It is inserted at a leaf position following standard BST insertion.
  2. The newly inserted node is initially colored RED (to preserve property 5, black-height).
  3. 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:

Definition of B-Tree of Order

Definition

B-Tree of Order m

A B-Tree of order is a self-balancing, multi-way search tree satisfying:

  1. Every node has at most children and at most keys.
  2. Every internal node (except the root) has at least children and at least keys.
  3. The root has at least children if it is not a leaf node (and at least key).
  4. All leaf nodes appear at the exact same level (perfect balance).
  5. A non-leaf node with children contains keys sorted in ascending order: , serving as partition boundaries for its subtrees.
B-Tree Constraints for Common Orders
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:

  1. Locate Target Leaf: Perform multi-way search to locate the leaf where the new key belongs.
  2. Insert into Leaf:
    • If the leaf currently contains fewer than keys, insert the key in sorted order.
  3. 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

Example 1

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 of 10. .
  • Insert 30: Right child of 20. . Imbalance at node 10 (, right child ) RR Rotation (Single Left Rotation) around node 10.
    10 (-2)                     20 (0)
      \                        /      \
      20 (-1)    ==>        10 (0)   30 (0)
        \
        30 (0)

Insertions 40, 50:

  • Insert 40: Right child of 30. . (Balanced)
  • Insert 50: Right child of 40. . Imbalance at node 30 (, right child ) RR Rotation around node 30.
         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 of 30. 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).
  1. Right rotate right child 40 around 30: 30 moves up, 25 stays left child of 30, 40 becomes right child of 30.
  2. Left rotate root 20 around 30: 30 becomes new root; 20 becomes left child with children 10 and 25; 40 becomes right child with child 50.
Answer:

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.

Example 2

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      50

Evaluating 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).

Answer:

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.

Example 3

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 is 10. 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 key 20 is 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]. Median 6 promoted to root. Root overflows: was [10, 20], now receives 6 (Root Overflow!). Median of root 10 promoted 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 with 12 .
Answer:

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.

Example 4

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 of 10. New nodes are inserted as RED: 10 (B) -> 20 (R). Parent 10 is BLACK no violation.

Insert 30 (Double-Red Violation):

  • Insert 30: Placed as right child of 20, colored RED. Violation: 20 is RED and child 30 is RED (Property 4 violated!).
    • Check uncle of 30: left child of 10 is NIL (BLACK).
    • Shape: 10 (B) -> 20 (R) -> 30 (R) forms a straight right-leaning line (RR).
    • Resolution: Left rotate grandparent 10, and swap colors of parent 20 and grandparent 10:
      • 20 becomes root, colored BLACK.
      • 10 becomes left child, colored RED.
      • 30 stays right child, colored RED.

Insert 15 (Uncle RED Case):

  • Insert 15: right child of 10, colored RED. Violation: 10 is RED and 15 is RED.
    • Check uncle of 15: sibling of parent 10 is 30, which is RED.
    • Resolution (Case 1: Uncle RED): Recolor parent 10 to BLACK, uncle 30 to BLACK, and grandparent 20 to RED.
    • Fix root color: Grandparent 20 is root, so recolor 20 back to BLACK (Property 2).
Answer:

Final Red-Black Tree Configuration:

  • Root: 20 (Black)
  • Left Child: 10 (Black) with Right Child 15 (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

Question 1

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.

Answer:

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 .

Question 2

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:

  1. Insert 21: Root ().
  2. Insert 26: Right of 21 ().
  3. Insert 30: Right of 26 . Imbalance at 21 RR Rotation. 26 becomes root, with left child 21 and right child 30.
  4. Insert 9: Left of 21 ().
  5. Insert 4: Left of 9 . Imbalance at 21 LL Rotation around 21. 9 becomes left child of 26, with children 4 and 21.
  6. Insert 14: Right of 9 and left of 21 placed as left child of 21. Tree remains balanced.
  7. Insert 28: Left child of 30. Balanced.
  8. Insert 18: Placed as right child of 14. Check balance factors: Subtree at 9: left child 4 (height 0), right subtree 21 with left child 14 (which has right child 18, height 2) . Right child 21 has left child 14 () RL Rotation around 21 or 9.
Answer:

The construction encounters three rotations:

  1. After inserting 30: RR Rotation around 21
  2. After inserting 4: LL Rotation around 21
  3. After inserting 18: RL Rotation around 9

Final tree is balanced with height and all nodes satisfying .

Question 3

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 :
Answer:

The minimum number of nodes required to construct an AVL tree of height is nodes.

Question 4

For a B-Tree of order :

  1. State the maximum and minimum number of keys in an internal node.
  2. State the maximum and minimum number of children for an internal node.
  3. Calculate the maximum number of keys that can be stored in the tree if its height is (levels 0, 1, 2).

Formulas for Order :

  1. Number of Keys in Internal Nodes (excluding root):
    • Maximum keys:
    • Minimum keys:
  2. 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:

Answer:
  1. Keys per internal node: Min = 2, Max = 4.
  2. Children per internal node: Min = 3, Max = 5.
  3. Maximum keys in tree of height : keys.
Question 5

Explain why B-Trees are preferred over standard Binary Search Trees for secondary storage (disk) implementations in databases and file systems.

Key Architectural Differences:

BST vs B-Tree for Disk Storage
FeatureBinary Search Tree (BST/AVL)B-Tree (Order )
Node Capacity1 key, 2 child pointersHundreds of keys matching disk block size
Tree GeometryDeep and narrow ()Extremely shallow and wide ()
Disk I/O FrequencyHigh ( disk accesses)Minimal (– disk accesses for millions of records)
Storage Block AlignmentNodes do not align with disk pagesEach 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 .

Answer:

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.

Question 6

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:

  1. Every node is colored either RED or BLACK.
  2. The root node is always BLACK.
  3. All leaf nodes (NIL sentinels) are BLACK.
  4. If a node is RED, both of its children must be BLACK (no two consecutive red nodes).
  5. 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 .

Answer:

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.

Past exam questions for Data Structure and Algorithms

← Definition and tree terminologies · Binary trees · Binary search treeGraphs →