Threaded trees and B-trees

Learning outcomes

Explain the purpose of threads, state B-tree occupancy rules under a declared convention, and trace a split.

11.1 Threaded binary trees

In an ordinary linked binary tree, many child pointers are null. A threaded tree uses selected otherwise-null pointers to store traversal links, commonly inorder predecessors or successors. Tag fields distinguish a real child from a thread. Treating a thread as a child can create an infinite traversal.

In a right-threaded tree, a node with no right child may point to its inorder successor. To find the successor of node p: follow the right thread if one exists; otherwise enter p's real right subtree and repeatedly follow real left children to its leftmost node. A header sentinel can represent traversal boundaries.

For a BST with keys 10, 20 and 30 and root 20, node 10's missing right child can thread to 20. An inorder traversal visits 10, follows that thread to 20, then visits 30 through the real right subtree. Insertion and deletion must preserve both ordinary child links and thread links. Threads trade update complexity for traversal without a separate recursion stack.

11.2 Why multiway trees are useful

A binary tree makes one left/right decision at each node. A multiway search tree stores several sorted keys in a node, dividing the key range into several child intervals. When nodes correspond to storage pages, greater branching can reduce the number of page visits. CPU comparisons within a node and storage accesses are distinct costs.

A B-tree maintains bounded occupancy and places every leaf at the same depth. This chapter uses minimum degree t, with t ≥ 2, to avoid ambiguity in the word “order”.

An empty tree may use an empty root or a null root, depending on the implementation. Some texts define order m as maximum children; always confirm that convention before translating a question.

11.3 Search and a split trace

For keys [20, 40], the child ranges are values below 20, values between 20 and 40, and values above 40, under a no-duplicates policy. Search first checks the keys in the node; if absent, it descends into the appropriate range.

Take t = 2, so each node holds at most three keys. Insert 10, 20 and 30: the root becomes [10,20,30]. Before descending to insert 40, split the full root. Promote 20 to a new root, with leaf children [10] and [30]. Insert 40 into the right leaf, giving [30,40].

The promoted key belongs to the parent, not both leaves, in this B-tree convention. A B+ tree follows different leaf-storage rules and should not be treated as identical.

11.4 Deletion at concept level

Deletion must preserve minimum occupancy. If a target key is in an internal node, use a suitable predecessor or successor when the corresponding child can spare a key. Otherwise, combine the neighbouring children and separating parent key, then continue. Before descending into a minimally occupied child, borrow through the parent from a sibling with spare keys or merge with a sibling. An empty internal root can be replaced by its only child, decreasing height.

For fixed t, height is O(log n), giving logarithmic search and update paths. The detailed cost also depends on work within each node. This chapter develops the invariants and split reasoning; a production B-tree implementation additionally needs tested merge, borrow, root-change and storage-management paths.

Practice

1. Why must a threaded-tree pointer carry a child/thread tag?
2. For t = 3, state the minimum and maximum keys in a non-root node.
3. Continue the t = 2 insertion example with 50 and 60. Show any split.
4. Explain why a B-tree root may have fewer keys than a non-root node.