Balanced trees: AVL, red-black and B-trees

In short

A balanced tree is a search tree that keeps its height at O(log n) by restructuring itself after every insertion and deletion, so search, insert and delete never degrade to the O(n) worst case of a skewed binary search tree. AVL trees balance by height difference, red-black trees by colour rules that allow looser balance but cheaper updates, and B-trees / B+ trees balance by keeping many keys per node so that a tree over millions of records is only three or four disk blocks deep. This topic is examined in university Data Structures papers (AICTE/CBCS "Trees" unit) and in GATE — AVL rotations and height bounds under Data Structures, B and B+ tree indexing explicitly under DBMS file organisation (exact syllabus wording changes between years, so check the current one). In industry these are the data structures inside std::map, Java's TreeMap, the Linux kernel's rbtree, and every relational index in MySQL InnoDB, PostgreSQL and Oracle — which is why Oracle, Amazon, Microsoft IDC, Zoho, Flipkart and core-banking product teams ask them in technical rounds.

Explained

Why balance at all, and what "balanced" means

• An unbalanced BST built from sorted input (1, 2, 3, …, n) becomes a right-skewed chain: height n−1, search O(n) — a linked list with extra pointers.
• A tree on n nodes has minimum possible height ⌊log₂ n⌋. "Balanced" means height stays Θ(log n) for every input order, guaranteed, not on average.
• Two families of guarantee:
  • Height-balanced / rotation-based (AVL, red-black, splay, treap, scapegoat): binary, one key per node, kept in RAM.
  • Multiway / block-balanced (B-tree, B+ tree, B* tree, 2-3 tree, 2-3-4 tree): many keys per node, node sized to a disk page.
• All of them keep the in-order traversal sorted — they are BSTs, so search logic is unchanged; only the fix-up after update differs.
• Cost model matters: in RAM we count comparisons; on disk we count block (page) reads, which is why B-trees exist.

AVL trees (Adelson-Velsky and Landis, 1962)

• Definition: a BST in which for every node, balance factor BF = height(left) − height(right) ∈ {−1, 0, +1}. Each node stores its height (or BF).
• Height of an empty tree is taken as −1 (some books use 0 — state your convention in the exam).
• Insertion: insert as in a plain BST, then walk back up updating heights; at the first (lowest) unbalanced node z apply one rotation case, based on the path from z to the new key:
  1. LL (left-left): inserted in left subtree of z's left child → single right rotation at z.
  2. RR (right-right): right subtree of right child → single left rotation at z.
  3. LR: right subtree of left child → left rotate the left child, then right rotate z (double).
  4. RL: left subtree of right child → right rotate the right child, then left rotate z (double).
• After the rotation the subtree regains its pre-insertion height, so one insertion needs at most one single or one double rotation — no further fix-up above.
• Deletion: delete as in a BST (for two children, replace with in-order predecessor/successor), then rebalance up the path. Here the subtree may *shrink*, so rebalancing can cascade: up to O(log n) rotations per deletion.
• Rotation itself is O(1) — it only re-links three pointers and updates two heights.
• Advantages: strictest balance of the practical schemes → shortest trees, fastest lookups; height ≤ about 1.44 log₂ n.
• Limitations: stores a height/BF per node; more rotations and more height recomputation on write-heavy workloads than a red-black tree.

// single left rotation (RR case), node z with right child y
y = z.right;  z.right = y.left;  y.left = z;
z.h = 1 + max(h(z.left), h(z.right));
y.h = 1 + max(h(y.left), h(y.right));
return y;            // y is the new subtree root

Red-black trees

• A BST where every node carries one extra bit, RED or BLACK, satisfying:
  1. Every node is red or black.
  2. The root is black.
  3. Every leaf (NIL sentinel) is black.
  4. A red node's children are both black (no two consecutive reds on any path).
  5. For every node, all paths from that node down to a NIL leaf contain the same number of black nodes — this count is the node's black height, bh.
• Properties 4 and 5 force the longest path to be at most twice the shortest, giving h ≤ 2 log₂(n+1).
• Insertion: insert as a BST, colour the new node red, then fix "red-red" violations with the parent P, grandparent G and uncle U:
  • Case 1 — U is red: recolour P and U black, G red; move the problem up to G. (Repeats, so O(log n) recolourings.)
  • Case 2 — U is black, "triangle" (zig-zag): rotate P to convert into Case 3.
  • Case 3 — U is black, "line" (zig-zig): rotate G and swap colours of G and P. Done.
  • Finally force the root black. At most 2 rotations per insertion.
• Deletion: the hard case is removing a black node, which breaks property 5; it is repaired with a "double-black" fix-up of four cases (red sibling, black sibling with two black children, and the two near/far-nephew cases). At most 3 rotations per deletion, O(log n) recolourings.
• Equivalence: a red-black tree is a binary encoding of a 2-3-4 tree — a black node with its red children collapses into one multiway node (2, 3 or 4 children). Insert fix-up Case 1 corresponds to a node split.
• Why industry prefers it: fewer structural changes per update and only one colour bit of overhead; used in C++ std::map/std::set, Java TreeMap/TreeSet, the Linux CFS scheduler and epoll, and as the base for augmented structures (order-statistic trees, interval trees).

B-trees

• Designed by Bayer and McCreight for disk-resident indexes: make each node one disk page so that one page read brings in hundreds of keys, and height — hence the number of I/Os — collapses.
• Two conventions, both examined; say which you are using:
  • Order m (most Indian textbooks): a node has at most m children and m−1 keys.
  • Minimum degree t (CLRS): at least t and at most 2t children; so m = 2t.
• Structural rules (order m):
  • Every node holds k keys in sorted order with k+1 child pointers; a leaf has none.
  • Non-root nodes: at least ⌈m/2⌉−1 keys (so at least ⌈m/2⌉ children if internal); at most m−1 keys.
  • The root has at least 1 key (2 children) unless it is the only node.
  • All leaves are at the same level — the tree is perfectly height-balanced by construction.
  • Keys in child i lie between key i−1 and key i of the parent (multiway BST ordering).
• Search: at each node, binary-search the keys; follow one child pointer. O(log_⌈m/2⌉ n) page reads, O(log₂ m) comparisons inside each page.
• Insertion (grows upward, never downward):
  1. Find the correct leaf and insert the key in sorted position.
  2. If the leaf now has m keys (overflow), split it: the median key moves up to the parent, the remaining keys form two nodes.
  3. If the parent overflows, split again, recursively. If the root splits, a new root is created and the height increases by one — the only way a B-tree gets taller.
• Deletion:
  1. If the key is in an internal node, replace it with its in-order predecessor/successor from a leaf, then delete from the leaf.
  2. If the leaf falls below ⌈m/2⌉−1 keys (underflow), first borrow (rotate) a key from an adjacent sibling that has a spare, routing it through the parent.
  3. If no sibling can spare one, merge the node with a sibling plus the separating parent key. If the parent underflows, repeat; if the root is left with no keys, the height decreases by one.
• B+ tree (the form actually used in databases):
  • All keys and record pointers live in the leaves; internal nodes hold only separator keys as a routing index, so fanout is higher.
  • Leaves are chained in a doubly linked list → range scans, ORDER BY, BETWEEN and sequential reads cost one descent plus a sideways walk.
  • Every search travels the full height (predictable I/O); duplicated separator keys cost a little space.
  • B\* tree: delays splits by redistributing keys between siblings, keeping nodes ≥ 2/3 full.
• Clustered vs secondary index: in MySQL InnoDB the table itself *is* a B+ tree on the primary key (clustered); secondary indexes are B+ trees whose leaves store the primary key, so a lookup may need a second descent ("bookmark lookup"). InnoDB's default page size is 16 KB.
• Limitations: nodes are typically only ~69% full on random inserts; random-insert workloads cause page splits and fragmentation; write-heavy stores sometimes prefer LSM trees instead.

Comparison and choosing one

• All three give O(log n) search, insert and delete in the worst case; a hash table beats them at single-key lookup (O(1) average) but cannot do ordered traversal, predecessor/successor or range queries.
• Splay trees and treaps are alternatives with amortised/expected O(log n) rather than worst-case guarantees.

Key points

• Balance factor - height(left) − height(right); must be −1, 0 or +1 at every node of an AVL tree.
• Rotation - O(1) pointer re-link that reduces height on one side; the only structural primitive in AVL and red-black trees.
• Four AVL cases - LL and RR need one single rotation; LR and RL need a double rotation (two single rotations).
• AVL insertion - at most one rebalance; AVL deletion - may rebalance at every level up to the root.
• Minimum-node recurrence - N(h) = N(h−1) + N(h−2) + 1, giving the worst-case (tallest) AVL tree of a given height.
• Red-black property 4 - no red node has a red child; property 5 - equal black height on all paths.
• New red-black node is always red - inserting black would immediately break the black-height property.
• Black height - number of black nodes from a node down to any NIL leaf, excluding the node itself.
• Red-black height bound - h ≤ 2 log₂(n+1), so it can be up to ~39% taller than an AVL tree on the same n.
• 2-3-4 equivalence - a red-black tree is a 2-3-4 tree in binary clothing; red links are "glue" inside a multiway node.
• B-tree order m - max m children, max m−1 keys, min ⌈m/2⌉ children for non-root internal nodes.
• All B-tree leaves are at the same depth - balance is maintained by splitting and merging, never by rotation.
• B-trees grow at the root - the height increases only when the root splits.
• B+ tree - data only in linked leaves; internal nodes are a pure index, enabling fast range scans.
• Fanout beats depth - with order 256, a million keys sit 3 levels deep; an AVL tree needs about 20.
• Space-time trade-off - AVL: shorter tree, costlier writes; red-black: slightly taller, cheaper writes.
• Augmentation - storing subtree sizes or max endpoints turns a red-black tree into an order-statistic or interval tree.

Formulas and examples

Example 1 — AVL insertions with rotations. Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree.

1. 10, 20 → fine. Insert 30: node 10 has BF = −1 − 1 = −2, path right-right → RR, left rotate at 10 → root 20, children 10 and 30.
2. Insert 40: BF(20) = 0 − 1 = −1 → still AVL, no rotation.
3. Insert 50: node 30 has BF = −1 − 1 = −2, right-right → left rotate at 30 → subtree 40 (30, 50). Tree: 20 (10, 40 (30, 50)).
4. Insert 25: it goes 20 → 40 → 30 → left. Now BF(30) = +1, BF(40) = 1−0 = +1, BF(20) = 0 − 2 = −2; the new key went into the left subtree of the right child → RL case: right-rotate at 40, then left-rotate at 20.
5. Final tree: 30 (20 (10, 25), 40 (−, 50)) — height 2 edges; BF(30) = 0, BF(20) = 0, BF(40) = −1, leaves 0. One double rotation, i.e. two single rotations.

Example 2 — worst-case AVL height for n = 1000. Build N(h):

• N(13) = 609 + 376 + 1 = 986 ≤ 1000, but N(14) = 986 + 609 + 1 = 1596 > 1000.
• Maximum height = 13 edges (14 levels). Cross-check with the bound: 1.4404 × log₂(1002) − 1.328 = 1.4404 × 9.969 − 1.328 = 13.03, so h ≤ 13 — exactly the figure the recurrence gives.
• Minimum height = ⌈log₂ 1001⌉ − 1 = 10 − 1 = 9.

Example 3 — red-black bounds. A red-black tree stores n = 15 keys.

• Maximum height = 2 log₂(15 + 1) = 2 × 4 = 8 edges.
• Black height: n ≥ 2^bh − 1 ⇒ 2^bh ≤ 16 ⇒ bh ≤ 4.
• For n = 10⁶: red-black h ≤ 2 × 19.93 = 39; AVL h ≤ 1.4404 × 19.93 − 1.328 = 27; perfectly balanced BST h = 19. So the red-black worst case is about twice the ideal and 1.4× the AVL worst case.

Example 4 — B-tree fanout and disk accesses. A disk page is 4096 bytes, each key is 10 bytes and each child pointer 6 bytes. Ignore per-page overhead.

• (m−1)×10 + m×6 ≤ 4096 → 16m ≤ 4106 → m ≤ 256.6 → order m = 256 (255 keys, 256 pointers per node).
• Now take order 100 (min 50 children) with n = 1,000,000 keys: h ≤ log₅₀((10⁶+1)/2) = ln(500000.5)/ln 50 = 13.122/3.912 = 3.35 → h ≤ 3, i.e. at most 4 page reads (root, two internal levels, leaf) — and the root is normally cached, so ~3 physical I/Os.
• Capacity check: a height-3 B-tree of order 100 holds up to 100⁴ − 1 = 99,999,999 keys, comfortably more than 10⁶.
• The same million keys in an AVL tree need up to 28 levels — about 28 random reads if it were on disk. That ratio, 4 against 28, is the whole reason databases use B+ trees.

Example 5 — B-tree insertion with splits (order 3: max 2 keys, min 1 key). Insert 10, 20, 30, 40, 50.

1. [10] → [10, 20].
2. Insert 30 → [10, 20, 30] overflows (3 keys > 2). Median 20 moves up: root [20], children [10] and [30].
3. Insert 40 → right leaf [30, 40]. Insert 50 → [30, 40, 50] overflows; median 40 moves up to the root: root [20, 40], leaves [10], [30], [50].
4. Result: height 1, 3 leaves all at the same level, every node has ≥ 1 key. Inserting 60 then 70 would split again and push 60 up, overflowing the root [20, 40, 60] and creating a new root [40] — height becomes 2.

Where it is used

• Relational databases: every primary-key and secondary index in MySQL/InnoDB, PostgreSQL, Oracle and SQL Server is a B+ tree; InnoDB's clustered index *is* the table. Core banking, IRCTC-style booking systems and ERP deployments in India all rest on these indexes, and DBA/backend interviews probe why a range query uses an index but LIKE '%x' cannot.
• File systems and storage: NTFS, ext4 (HTree directories), XFS, Btrfs and APFS use B-tree variants for directory and extent maps; firmware/storage roles at Samsung, Western Digital and Micron India test this.
• Systems and language libraries: C++ std::map/std::set, Java TreeMap/TreeSet, the Linux kernel rbtree (CFS scheduler, epoll, virtual memory areas) — red-black trees. Product-engineering roles at Oracle, Microsoft IDC, VMware, Nutanix and Arista expect you to know the guarantee behind std::map::find.
• In-memory and NoSQL engines: ordered indexes, secondary indexes and key-range routing in MongoDB (B-tree indexes), Redis sorted sets (skip lists — a comparable balanced structure), and time-series stores.
• Competitive programming and SDE rounds: order-statistic queries, "count of smaller elements", interval scheduling and sweep-line problems use balanced-BST augmentation or a C++ multiset/policy tree.
• Compilers, routers and CAD: symbol tables in compilers, routing/forwarding tables, and spatial indexes (R-trees, a B-tree relative) in GIS products such as those built for survey and land-record digitisation.

Interview questions

• Q: Why is a plain BST not enough? A: Its height depends on insertion order; sorted input makes it a chain of height n−1, so operations degrade from O(log n) to O(n). Balanced trees bound the height at O(log n) for every input.
• Q: How many rotations can a single AVL insertion and a single AVL deletion need? A: Insertion needs at most one rotation (single or double) because the rebalanced subtree returns to its original height; deletion can need O(log n) rotations because the subtree may shrink and propagate imbalance to the root.
• Q: When do you use a double rotation in an AVL tree? A: In the LR and RL cases — when the new key goes into the "inner" subtree of the unbalanced node's child; a single rotation there would just mirror the imbalance.
• Q: Give the minimum number of nodes in an AVL tree of height 5. A: N(h) = N(h−1)+N(h−2)+1 with N(0)=1, N(1)=2 gives 4, 7, 12, 20.
• Q: Why is a newly inserted red-black node coloured red? A: Red preserves the black-height property (property 5) automatically; only the weaker red-red rule can break, and that is repairable in O(log n) recolourings with at most two rotations.
• Q: AVL or red-black — which would you choose and why? A: AVL for lookup-heavy, rarely updated data since it is shorter (≤1.44 log n vs ≤2 log n); red-black for update-heavy data since it does at most 2 rotations per insert and 3 per delete and stores only one colour bit.
• Q: Why do databases use B+ trees instead of AVL or red-black trees? A: Disk/SSD cost is dominated by page reads; a B+ tree node fills one page with hundreds of keys, so a million-key index is 3-4 levels deep instead of ~20-28, and its linked leaves make range scans sequential.
• Q: Difference between a B-tree and a B+ tree? A: A B-tree stores keys with data in every node and can finish a search early at an internal node; a B+ tree keeps all keys and data pointers in the leaves, links the leaves, has higher fanout and uniform search cost.
• Q: How does a B-tree grow in height? A: Only when the root overflows and splits — its median key becomes a new single-key root, so the tree grows upward and all leaves stay at the same level.
• Q: In a B-tree of order m, what are the minimum and maximum keys in a non-root node? A: Minimum ⌈m/2⌉−1 and maximum m−1 keys (children ⌈m/2⌉ to m); the root may have as few as 1 key.
• Q: What happens on B-tree underflow after a deletion? A: Borrow a key from an adjacent sibling through the parent if the sibling has a spare; otherwise merge the node, the separating parent key and the sibling, and propagate the underflow upward.
• Q: Is a red-black tree related to any multiway tree? A: Yes — it is an exact binary encoding of a 2-3-4 tree; a black node with its red children forms one 2-, 3- or 4-node, and the red-uncle insert case corresponds to a node split.
• Q: When would a hash table beat all of these? A: For pure equality lookups, where O(1) average beats O(log n); but hash tables give no order, so predecessor/successor, range queries and sorted traversal need a balanced tree.

Common mistakes

• Computing the balance factor from the number of nodes instead of subtree heights, or mixing the h(empty) = −1 and h(empty) = 0 conventions mid-question.
• Rebalancing at the topmost unbalanced node instead of the lowest one on the insertion path, which yields a different (often invalid) tree.
• Assuming AVL deletion, like insertion, needs only one rotation.
• Confusing B-tree conventions: "order m" (max m children) versus CLRS "minimum degree t" (m = 2t) — answers differ by a factor of two if you mix them.
• In a B-tree split, moving the first or last key up instead of the median, or forgetting that the median leaves the original node.
• Colouring a new red-black node black, or forgetting to re-blacken the root after the fix-up, and miscounting black height by including the node itself.
• Claiming all leaves of an AVL tree are at the same level — only B-trees guarantee that; AVL leaf depths can differ.
• Saying a red-black tree is "always balanced like an AVL tree" — its height bound is twice the ideal, 2 log₂(n+1).

Related topics

Trees and binary search trees · Heaps and priority queues · Hashing and hash tables · Segment trees and Fenwick trees · Tries and string data structures · Database indexing and file organisation