1. Binary Search Trees (BST)

Definition – BST

A binary tree in which, for every node of value :

  • all elements in its left subtree have values ;
  • all elements in its right subtree have values .

Most operations then take on average (vs to search a linked list or an unordered binary tree).

flowchart TD
    n7((7)) --> n3((3))
    n7 --> n9((9))
    n3 --> n2((2))
    n3 --> n5((5))

⚠️ The inorder traversal of a BST lists the keys in sorted order — a quick way to check your answer.

current = root
while not found and current != NULL
    if current = searched            → found
    else if searched < current       → follow the left child
    else                             → follow the right child

Worked example – search 5 in the tree above: 7 → (5<7) left → 3 → (5>3) right → 5 found.

Insertion

Descend as for a search until an empty subtree, and create the node there.

template <class Element>
void BTree<Element>::insertNodeHelper(BNode *&ptr, const Element &value) {
    if (ptr == NULL)               ptr = new BNode(value);
    else if (value <= ptr->data)   insertNodeHelper(ptr->left, value);
    else                           insertNodeHelper(ptr->right, value);
}

⚠️ The definition uses strict <, but the code sends equal values to the left (<=) — duplicates end up in the left subtree.

Deletion – three cases

CaseAction
1. Node is a leafremove it directly
2. Node has one childthe child takes the node’s place
3. Node has two childrenreplace its value by the smallest value of the right subtree (its successor), then delete that node (which has at most one child)

Worked examples

  • Case 1: delete 40 (leaf under 41) → simply removed.
  • Case 2: delete 7 in 24 → 7 → 2 → 2 becomes the left child of 24.
  • Case 3: delete 37 in the tree below → successor = min of right subtree = 40 → 40 replaces 37, and the old 40 leaf is removed.
flowchart TD
    subgraph Before
    a37((37)) --> a24((24))
    a37 --> a41((41))
    a24 --> a7((7))
    a24 --> a32((32))
    a41 --> a40((40))
    a41 --> a42((42))
    end
    subgraph After ["After deleting 37"]
    b40((40)) --> b24((24))
    b40 --> b41((41))
    b24 --> b7((7))
    b24 --> b32((32))
    b41 --> b42((42))
    end
template <class Element>
void BTree<Element>::removeNodeHelper(BNode *&t, const Element &value) {
    if (t == NULL) return;                                   // not found
    if (value < t->data)       removeNodeHelper(t->left, value);
    else if (value > t->data)  removeNodeHelper(t->right, value);
    else if (t->left != NULL && t->right != NULL)            // two children
        t->data = removeMin(t->right);                       // replace by successor
    else {                                                   // leaf or one child
        BNode *oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;
        delete oldNode;
    }
}
 
template <class Element>
Element BTree<Element>::removeMin(BNode *&t) {   // removes and returns the min
    if (t->left != NULL) return removeMin(t->left);
    Element replaceValue = t->data;
    BNode *tmp = t;
    t = t->right;
    delete tmp;
    return replaceValue;
}

The BST problem – degeneration

A BST can degenerate into a list. Inserting 1, 4, 6, 15, 17 in this order gives a chain: search becomes .

flowchart TD
    d1((1)) --> d4((4)) --> d6((6)) --> d15((15)) --> d17((17))
BST operationBestWorst
Search / insert / delete

Solution: balanced trees (AVL, red-black).


2. AVL Trees

Definition – AVL tree (Adelson-Velskii & Landis, 1960s)

A BST such that, for every node :

  1. the heights of its left and right subtrees differ by at most one;
  2. its left and right subtrees are themselves AVL trees.

This keeps the depth in .

Definition – Balance factor

A leaf has (empty subtree height ).

Worked example

flowchart TD
    n5((5)) --> n3((3))
    n5 --> n8((8))
    n3 --> n1((1))
    n3 --> n4((4))
    n8 --> n7((7))
    n8 --> n11((11))
    n7 --> n6((6))
Nodeh(left)h(right)
1, 4, 6, 11−1−10
70−1+1
3000
810+1
512−1

All → AVL. Adding 2 as right child of 1 keeps it AVL (, ); a chain like 1 → 4 → 6 would not be ().

AVL node

template <class Element>
class NodeAVL {
public:
    NodeAVL *left;  Element data;  NodeAVL *right;
    int h;                                    // height
    NodeAVL(const Element &d) { left = 0; data = d; right = 0; h = 0; }
};

Operations

  • Find: same as a BST.
  • Insert: as in a BST, then rebalance if needed. Only nodes on the path from the insertion point to the root can become unbalanced.
  • All in .

Rotations

A rotation rearranges nodes to restore balance; it is needed whenever a node’s becomes or .

Insertion into… of the unbalanced node ShapeFix
left subtree of the left childLLsingle right rotation
right subtree of the right childRRsingle left rotation
right subtree of the left childLRdouble right rotation
left subtree of the right childRLdouble left rotation

Single right rotation

The left child becomes the root of the subtree; ‘s right subtree () becomes ‘s left subtree.

void rotationRight(NodeAVL *&N) {
    NodeAVL *C = N->left;
    N->left = C->right;
    C->right = N;
    N->h = max(height(N->left), height(N->right)) + 1;
    C->h = max(height(C->left), N->h) + 1;
    N = C;
}

Worked example – insert 60, 50, 20: node 60 gets (LL) → right rotation at 60.

flowchart LR
    subgraph Unbalanced
    u60((60)) --> u50((50)) --> u20((20))
    end
    subgraph Balanced
    b50((50)) --> b20((20))
    b50 --> b60((60))
    end
    Unbalanced -- "right rotation at 60" --> Balanced

Single left rotation

Symmetric: the right child becomes the subtree root; ‘s left subtree becomes ‘s right subtree.

void rotationLeft(NodeAVL *&N) {
    NodeAVL *C = N->right;
    N->right = C->left;
    C->left = N;
    N->h = max(height(N->left), height(N->right)) + 1;
    C->h = max(N->h, height(C->right)) + 1;
    N = C;
}

Worked example – tree 50(20, 60(–, 80)): adding 80 keeps balance; adding 90 makes (RR) → left rotation at 60 → 50(20, 80(60, 90)).

⚠️ The slide’s code reads N->left->h directly, which crashes when a child is NULL. Use a helper height(p) that returns −1 for NULL (as above).

Double right rotation (LR case)

= single left rotation of ‘s left child, then single right rotation of .

void doubleRotRight(NodeAVL *&N) { rotationLeft(N->left); rotationRight(N); }

Worked example – tree 60(50(20(10, 40), 55), 80(70, 90)); insert 35 (under 40, left).

  • At 50: , → . Left child 20 has → LR.
  • Left rotation at 20 → 40(20(10, 35)); right rotation at 50 → 40(20(10, 35), 50(–, 55)).
flowchart TD
    r60((60)) --> r40((40))
    r60 --> r80((80))
    r40 --> r20((20))
    r40 --> r50((50))
    r20 --> r10((10))
    r20 --> r35((35))
    r50 --> rx[ ]
    r50 --> r55((55))
    r80 --> r70((70))
    r80 --> r90((90))
    style rx fill:none,stroke:none

Double left rotation (RL case)

= single right rotation of ‘s right child, then single left rotation of .

void doubleRotLeft(NodeAVL *&N) { rotationRight(N->right); rotationLeft(N); }

Worked example – tree 50(20, 80(60, 90)); insert 70 (right child of 60).

  • At 50: ; right child 80 has → RL.
  • Right rotation at 80 → 60(–, 80(70, 90)); left rotation at 50 → 60(50(20), 80(70, 90)).

Worked example – insert 4, 3, 1, 6, 7, 5, 2 into an empty AVL

InsertUnbalanced nodeCaseFixTree after
4–4
3–4(3)
14 ()LLsingle right at 43(1, 4)
6–3(1, 4(–, 6))
74 ()RRsingle left at 43(1, 6(4, 7))
53 (), child 6 has RLdouble left at 34(3(1), 6(5, 7))
23 (), child 1 has LRdouble right at 34(2(1, 3), 6(5, 7))
flowchart TD
    f4((4)) --> f2((2))
    f4 --> f6((6))
    f2 --> f1((1))
    f2 --> f3((3))
    f6 --> f5((5))
    f6 --> f7((7))

⚠️ The slide labels come from French: S.R.D = simple rotation droite (right), S.R.G = simple rotation gauche (left), D.R.D / D.R.G = double right / left.

Deletion in an AVL tree

Same as in a BST, followed by rebalancing. Unlike insertion (at most one single/double rotation), a deletion can cause cascading rebalancing up to the root — the main drawback of AVL trees.


3. Red-Black Trees (RBT)

Definition – Red-black tree (Bayer 1972; Guibas & Sedgewick 1978)

A BST where each node carries a color, red or black. A missing child is an external NIL node, considered a leaf; all real nodes are internal nodes.

Properties

  1. Every node is red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, both its children are black (no two reds in a row).
  5. For each node, all paths from it to descendant leaves contain the same number of black nodes (black-height).

Purpose: keep the tree balanced → all operations . NIL leaves are usually not drawn.

Insertion (bottom-up approach)

Insert as in a BST and color the new node red (black if it is the root). If its parent is also red → double red to fix. Let = new node, = parent, = sibling of (the “uncle”):

CaseSituationFix
1uncle is black (or NIL)restructure: single or double rotation of , , grandparent; the middle value becomes black with two red children
2uncle is redrecolor: parent and uncle → black, grandparent → red (root stays black). The grandparent may now form a double red with its parent → apply the cases again higher up

Worked example – insert e, h, k, n

InsertSituationActionResult (black / red)
erootcolor blacke
hparent e blacknothinge(–, h)
kdouble red h–k, uncle NIL (black)case 1: left rotation, h black, e and k redh(e, k)
ndouble red k–n, uncle e redcase 2: e, k → black; h → red, but h is the root → blackh(e, k(–, n))
flowchart TD
    h((h)) --> e((e))
    h --> k((k))
    k --> nx[ ]
    k --> n((n))
    classDef black fill:#222,color:#fff,stroke:#6b6b6b
    classDef red fill:#c62828,color:#fff,stroke:#7f1414
    class h,e,k black
    class n red
    style nx fill:none,stroke:none

Deletion (bottom-up approach)

  1. Apply the BST deletion.
  2. If the removed node was red → property 5 still holds, done.
  3. If it was black → some paths lose one black node. The node that replaces it (its NIL, or its only child) is considered to receive an extra black: it becomes black if it was red, or doubly black if it was already black.
  4. A doubly black node violates property 1 → removed through rotations and recolorings.

Top-down approach

In bottom-up insertion, case 2 can make the recolored grandparent red under a red parent, so fixes must propagate upwards. The top-down approach avoids this by guaranteeing, on the way down, that the uncle of the inserted node is always black.

Top-down insertion: while descending to the insertion point, whenever a node has two red children, recolor: → red (unless it is the root), its children → black.

flowchart LR
    subgraph Before
    P1((P)) --> L1((Lc))
    P1 --> R1((Rc))
    end
    subgraph After
    P2((P)) --> L2((Lc))
    P2 --> R2((Rc))
    end
    Before -- "color flip" --> After
    classDef black fill:#222,color:#fff,stroke:#6b6b6b
    classDef red fill:#c62828,color:#fff,stroke:#7f1414
    class P1,L2,R2 black
    class L1,R1,P2 red

If ‘s parent is also red, apply a rotation as in the bottom-up case — and ‘s uncle is guaranteed black, so no upward propagation.

Top-down deletion: property 5 is safe if the node removed is red. So while descending towards the node to delete, apply recolorings and (single/double) rotations so that it is red when it is reached.

Exercise – insert 10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55

Final tree (slide 40):

flowchart TD
    a30((30)) --> a15((15))
    a30 --> a70((70))
    a15 --> a10((10))
    a15 --> a20((20))
    a10 --> a5((5))
    a10 --> ax[ ]
    a70 --> a60((60))
    a70 --> a85((85))
    a60 --> a50((50))
    a60 --> a65((65))
    a50 --> a40((40))
    a50 --> a55((55))
    a85 --> a80((80))
    a85 --> a90((90))
    classDef black fill:#222,color:#fff,stroke:#6b6b6b
    classDef red fill:#c62828,color:#fff,stroke:#7f1414
    class a30,a15,a10,a20,a70,a50,a65,a85 black
    class a5,a60,a40,a55,a80,a90 red
    style ax fill:none,stroke:none

Check the properties:

  • Root 30 black ✓; no red node has a red child (60’s children 50, 65 are black) ✓.
  • Black nodes on each root-to-NIL path (excluding NIL): 30–15–10 → 3; 30–15–20 → 3; 30–70–60–50–40 → 30, 70, 50 = 3; 30–70–60–65 → 3; 30–70–85–80 → 3 ✓. Every path has black-height 3.

4. Comparison

TreeSearchInsertDeleteRebalancing cost
BST avg, worstsamesamenone (can degenerate)
AVL≤ 1 (double) rotation on insert; possibly cascading on delete
Red-blackrecolorings + few rotations