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.
Search
current = root
while not found and current != NULL
if current = searched → found
else if searched < current → follow the left child
else → follow the right childWorked 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
| Case | Action |
|---|---|
| 1. Node is a leaf | remove it directly |
| 2. Node has one child | the child takes the node’s place |
| 3. Node has two children | replace 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 operation | Best | Worst |
|---|---|---|
| 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 :
- the heights of its left and right subtrees differ by at most one;
- 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))
| Node | h(left) | h(right) | |
|---|---|---|---|
| 1, 4, 6, 11 | −1 | −1 | 0 |
| 7 | 0 | −1 | +1 |
| 3 | 0 | 0 | 0 |
| 8 | 1 | 0 | +1 |
| 5 | 1 | 2 | −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 | Shape | Fix |
|---|---|---|
| left subtree of the left child | LL | single right rotation |
| right subtree of the right child | RR | single left rotation |
| right subtree of the left child | LR | double right rotation |
| left subtree of the right child | RL | double 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->hdirectly, which crashes when a child isNULL. Use a helperheight(p)that returns −1 forNULL(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
| Insert | Unbalanced node | Case | Fix | Tree after |
|---|---|---|---|---|
| 4 | – | 4 | ||
| 3 | – | 4(3) | ||
| 1 | 4 () | LL | single right at 4 | 3(1, 4) |
| 6 | – | 3(1, 4(–, 6)) | ||
| 7 | 4 () | RR | single left at 4 | 3(1, 6(4, 7)) |
| 5 | 3 (), child 6 has | RL | double left at 3 | 4(3(1), 6(5, 7)) |
| 2 | 3 (), child 1 has | LR | double right at 3 | 4(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
- Every node is red or black.
- The root is black.
- Every leaf (NIL) is black.
- If a node is red, both its children are black (no two reds in a row).
- 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”):
| Case | Situation | Fix |
|---|---|---|
| 1 | uncle is black (or NIL) | restructure: single or double rotation of , , grandparent; the middle value becomes black with two red children |
| 2 | uncle is red | recolor: 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
| Insert | Situation | Action | Result (black / red) |
|---|---|---|---|
| e | root | color black | e |
| h | parent e black | nothing | e(–, h) |
| k | double red h–k, uncle NIL (black) | case 1: left rotation, h black, e and k red | h(e, k) |
| n | double red k–n, uncle e red | case 2: e, k → black; h → red, but h is the root → black | h(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)
- Apply the BST deletion.
- If the removed node was red → property 5 still holds, done.
- 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.
- 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
| Tree | Search | Insert | Delete | Rebalancing cost |
|---|---|---|---|---|
| BST | avg, worst | same | same | none (can degenerate) |
| AVL | ≤ 1 (double) rotation on insert; possibly cascading on delete | |||
| Red-black | recolorings + few rotations |