Unit 2: Advanced trees

An AVL tree (Adelson-Velsky and Landis) is a BST in which, for every node, the heights of the left and right subtrees differ by at most 1.

• Balance factor (BF) = height(left subtree) − height(right subtree); it must be −1, 0 or +1.
• After an insertion or deletion makes some BF equal to ±2, the tree is rebalanced with rotations.

An M-way search tree lets a node hold up to M − 1 keys and have up to M children, so the tree is much shorter — ideal for data stored on disk. A B-tree of order m is a balanced M-way search tree in which:

• Every node has at most m children and m − 1 keys.
• Every node except the root has at least ⌈m/2⌉ children.
• The root has at least 2 children (unless it is a leaf).
• All leaves are at the same level.
• Keys within a node are sorted.

When a node overflows during insertion, it splits and the middle key moves up to the parent.

A B+ tree is a variation of the B-tree used in databases and file systems:

• All data records (keys with data) are stored in the leaves; internal nodes hold only keys for navigation.
• Leaves are linked together, so range queries and sequential access are fast.

A red-black tree is a self-balancing BST in which each node is coloured red or black, following these rules:

• The root is black, and every leaf (NULL) is black.
• A red node cannot have a red child (no two reds in a row).
• Every path from a node to its descendant leaves has the same number of black nodes.

These rules keep the tree approximately balanced (height at most 2 log(n + 1)), so operations take O(log n). It needs fewer rotations than an AVL tree on insertions and deletions.

A heap is a complete binary tree that satisfies the heap property:

• Max-heap: every parent ≥ its children; the largest value is at the root.
• Min-heap: every parent ≤ its children; the smallest value is at the root.

Heaps are stored in arrays and are used for priority queues and heap sort.

Heap sort runs in O(n log n) time in all cases.