An AVL tree guarantees O(log n) search even in the worst case chiefly because:

Every node's balance factor is kept within {−1, 0, +1}, bounding the tree's height at O(log n)

It never stores more than one element

It is always a complete binary tree by construction

A B+ tree, compared to a plain B-tree, differs chiefly in that:

All actual records live only at the leaf level, and leaves are linked for fast sequential/range access

It cannot be used for indexing at all

Its leaves are never at the same depth

A B* tree, compared to a plain B-tree, requires nodes to be at least:

Exactly half full, same as a B-tree

B-trees are preferred over binary search trees for disk-backed database indexes chiefly because:

Their high branching factor minimises the number of disk-block reads needed

They use less memory per key than any other structure

Binary search trees cannot store more than 100 elements

B-trees require no comparisons at all

A threaded binary tree's threads are used chiefly to:

Enable inorder traversal without a stack or recursion, by reusing otherwise-null pointers

Store a second copy of every key

Prevent the tree from ever being searched

Make the tree unbalanced on purpose

Which of the following are true of the standard 'left child, right sibling' transform for converting a forest into a single binary tree? (More than one option may be correct.)

A node's first child becomes its binary-tree left child

A node's next sibling becomes its binary-tree right child

It lets general (non-binary) tree algorithms be expressed as binary-tree algorithms

A node's first child becomes its binary-tree left child

A node's next sibling becomes its binary-tree right child

It only works if the forest has exactly one tree

It lets general (non-binary) tree algorithms be expressed as binary-tree algorithms

Choosing an AVL tree over a B+ tree for a given system's index structure is most justified when:

The data and index live entirely in memory, with frequent lookups relative to updates

The data lives on disk and minimising block reads is the priority

There is no need for ordered/comparison-based search at all

The system has no memory available at all

Advanced Trees: AVL, B-Tree, B+/B* Tree and Threaded Binary Trees

The course's Programming and Data Structures chapters cover binary search trees and heaps. NET's Unit 7 names several tree structures beyond them — AVL trees, B, B+ and B* trees and threaded binary trees. This chapter covers all of them, plus forests, which complete the tree vocabulary this unit names.

AVL Trees: Self-Balancing via Rotations

A plain binary search tree's height, and hence its search/insert/delete time, is O(n) in the worst case (a degenerate, list-like tree from inserting already-sorted data). An AVL tree (Adelson-Velsky and Landis) maintains the BALANCE FACTOR of every node — height(left subtree) − height(right subtree) — within {−1, 0, +1} at all times, which provably keeps the tree's height at O(log n), guaranteeing O(log n) search/insert/delete even in the worst case. Balance is restored after an insertion or deletion by ROTATIONS: a single rotation (LL or RR case) fixes an imbalance on one side, and a double rotation (LR or RL case) fixes a zig-zag imbalance by first rotating the child, then the node itself.

🧠 Name the case by which side is 'heavy' and where the new node lands

LL means the imbalance is on the LEFT subtree's LEFT subtree — a single right rotation at the unbalanced node fixes it. RR is the mirror, fixed by a single left rotation. LR means the imbalance is on the LEFT subtree's RIGHT subtree (a zig-zag) — first rotate the left child left, THEN rotate the node right. RL is the mirror. Reading off which two directions are named tells you directly whether one or two rotations are needed and in which order — no need to memorise four separate procedures from scratch.

B-Trees, B+ Trees and B* Trees

The B-tree family, ordered by how much they differ from a plain B-tree
Structure	Key property
B-tree of order m	Every node has between ⌈m/2⌉ and m children (except the root); all leaves sit at the SAME depth; both keys and data/records may live at internal nodes as well as leaves.
B+ tree	ALL actual data/records live only at the leaf level; internal nodes hold only keys used purely to guide the search; leaves are additionally linked in a sequential chain, which is what makes a range query (or a full ordered scan) fast without repeatedly walking back up the tree.
B* tree	A stricter B-tree variant requiring nodes to be at least 2/3 FULL (rather than B-tree's ½ full) before splitting — achieved by first attempting to redistribute keys with a sibling and splitting only when both are full, giving denser nodes and shallower trees at the cost of more complex insertion logic.

🎯 Why B-trees (not binary search trees) are the standard for disk-backed indexes

A disk access is orders of magnitude slower than an in-memory comparison, so the metric that matters is the NUMBER OF DISK BLOCKS READ, not the number of comparisons. A B-tree's high branching factor (each node holds many keys, sized to fill one disk block) means even a huge number of records needs only a few LEVELS to reach — three or four levels can index millions of records — whereas a binary search tree's branching factor of 2 would need many more levels and hence many more disk reads for the same number of records. This is exactly why the course's Databases chapter's own B+ tree indexing material and this chapter's B-tree/B*-tree material are speaking about the same family from two different angles: the DBMS chapter treats B+ trees as an INDEXING structure, and this chapter treats the whole family as a DATA STRUCTURE in its own right.

Threaded Binary Trees and Forests

In an ordinary binary tree, most nodes' left/right pointers that would otherwise be NULL (leaves have two, and most internal nodes have at least one) are simply wasted space. A threaded binary tree reuses these NULL pointers as THREADS pointing to the node's inorder PREDECESSOR (for an otherwise-null left pointer) or SUCCESSOR (for an otherwise-null right pointer) — a boolean flag per side records whether that pointer is a real child link or a thread, so the tree can be traversed in inorder sequence WITHOUT a stack or recursion, trading a small amount of per-node bookkeeping for genuinely O(1) extra space traversal.

A forest is simply a set (usually ordered) of disjoint trees — no single root ties them together. Any forest can be converted into a single binary tree by a standard transform ('left child, right sibling'): a node's first child becomes its binary-tree LEFT child, and its next sibling becomes its binary-tree RIGHT child — which is exactly why forest and general (non-binary) tree algorithms are so often reduced to binary-tree algorithms rather than treated as a separate case.

Sets as Data Structures, and Choosing Among the Tree Family

A set as a data structure is typically implemented as a hash table (O(1) average membership/insert/delete, no ordering), a balanced BST such as an AVL or red-black tree (O(log n) for all three, but sorted order maintained and range queries supported), or a bit-vector when the universe of possible elements is small and known (O(1) with very low constant factor, but wasteful when the universe is large and the set itself is sparse).
Choosing among the tree family is a trade-off question, not a 'which is best' question: AVL trees suit an IN-MEMORY, comparison-heavy workload with frequent lookups relative to updates (their strict balancing costs more per update but pays off in guaranteed O(log n) lookups); B/B+ trees suit a DISK-BACKED workload where minimising the NUMBER OF BLOCK READS dominates; threaded trees suit a memory-constrained setting needing repeated inorder traversal without recursion/stack overhead.

Key takeaways

An AVL tree keeps every node's balance factor in {−1, 0, +1}, guaranteeing O(log n) height and hence O(log n) operations even in the worst case, restored by single (LL/RR) or double (LR/RL) rotations.
A B-tree keeps all leaves at the same depth; a B+ tree pushes all records to the leaf level with linked leaves for fast range scans; a B* tree requires nodes at least 2/3 full before splitting.
B-trees are the standard for disk-backed indexes because their high branching factor minimises block reads, which matters far more than comparison count once disk I/O dominates.
A threaded binary tree reuses null pointers as inorder predecessor/successor threads, enabling O(1)-extra-space traversal with no stack or recursion.
A forest converts to a single binary tree via the left-child/right-sibling transform, reducing forest algorithms to binary-tree algorithms.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

An AVL tree guarantees O(log n) search even in the worst case chiefly because:
1. Every node's balance factor is kept within {−1, 0, +1}, bounding the tree's height at O(log n)
2. It never stores more than one element
3. It is always a complete binary tree by construction
4. It uses no comparisons at all
Show answer
Answer: A — Every node's balance factor is kept within {−1, 0, +1}, bounding the tree's height at O(log n)
Bounding the balance factor at every node provably bounds the overall height at O(log n), which is what a plain (unbalanced) binary search tree cannot guarantee — its worst case degenerates to O(n).
A B+ tree, compared to a plain B-tree, differs chiefly in that:
1. All actual records live only at the leaf level, and leaves are linked for fast sequential/range access
2. It cannot be used for indexing at all
3. It has no internal nodes
4. Its leaves are never at the same depth
Show answer
Answer: A — All actual records live only at the leaf level, and leaves are linked for fast sequential/range access
By keeping data only at the leaves and chaining leaves together, a B+ tree makes range queries and full ordered scans fast without repeatedly climbing back up the tree, which is exactly why it, rather than a plain B-tree, is the standard DBMS indexing structure.
A B* tree, compared to a plain B-tree, requires nodes to be at least:
1. 2/3 full before splitting
2. Completely empty
3. Exactly half full, same as a B-tree
4. Full only at the root
Show answer
Answer: A — 2/3 full before splitting
A B* tree first attempts to redistribute keys with a sibling and splits only when both are full, achieving the stricter 2/3-full requirement and denser, shallower trees than a plain B-tree's ½-full minimum.
B-trees are preferred over binary search trees for disk-backed database indexes chiefly because:
1. Their high branching factor minimises the number of disk-block reads needed
2. They use less memory per key than any other structure
3. Binary search trees cannot store more than 100 elements
4. B-trees require no comparisons at all
Show answer
Answer: A — Their high branching factor minimises the number of disk-block reads needed
Since disk access is far slower than an in-memory comparison, the metric that matters is the number of blocks read, and a B-tree's high branching factor (sized to fill one block per node) needs far fewer levels — hence far fewer reads — than a binary tree's branching factor of 2 for the same number of records.
A threaded binary tree's threads are used chiefly to:
1. Enable inorder traversal without a stack or recursion, by reusing otherwise-null pointers
2. Store a second copy of every key
3. Prevent the tree from ever being searched
4. Make the tree unbalanced on purpose
Show answer
Answer: A — Enable inorder traversal without a stack or recursion, by reusing otherwise-null pointers
Otherwise-null child pointers are repurposed to point directly to the inorder predecessor/successor, which is what lets a traversal move through the tree without an explicit stack or recursive call stack.
Which of the following are true of the standard 'left child, right sibling' transform for converting a forest into a single binary tree? (More than one option may be correct.)
1. A node's first child becomes its binary-tree left child
2. A node's next sibling becomes its binary-tree right child
3. It only works if the forest has exactly one tree
4. It lets general (non-binary) tree algorithms be expressed as binary-tree algorithms
Show answer
Answer: A — A node's first child becomes its binary-tree left child; B — A node's next sibling becomes its binary-tree right child; D — It lets general (non-binary) tree algorithms be expressed as binary-tree algorithms
The transform works for any forest, including several separate trees — the first tree's root becomes the binary tree's root, and subsequent trees' roots chain along the right-sibling pointers, which is exactly what makes the reduction general.
In an AVL tree, an imbalance located on a node's left subtree's right subtree (a zig-zag imbalance) requires which named rotation case?
Numerical answer — type the value.
Show answer
Answer: LR
The LR case is fixed by first rotating the left child left, then rotating the unbalanced node right — a double rotation, unlike the single rotation that fixes the pure LL or RR cases.
Choosing an AVL tree over a B+ tree for a given system's index structure is most justified when:
1. The data and index live entirely in memory, with frequent lookups relative to updates
2. The data lives on disk and minimising block reads is the priority
3. There is no need for ordered/comparison-based search at all
4. The system has no memory available at all
Show answer
Answer: A — The data and index live entirely in memory, with frequent lookups relative to updates
An AVL tree's strict, comparison-based balancing is well suited to an in-memory workload where guaranteed O(log n) lookups matter; once data lives on disk, minimising block reads dominates and a B/B+ tree's high branching factor is the better fit.