TAOCP 6.2.4: Multiway Trees

Section 6.2.4 exercises: 9/9 solved.

9 items

Section 6.2.4. Multiway Trees

Exercises from TAOCP Volume 3 Section 6.2.4: 9/9 solved.

#	Rating	Category	Status	Time
1	[10]	simple	solved	1m
2	[15]	simple	verified	2m30s
3	[23]	medium	solved	5m02s
4	[21]	medium	solved	4m05s
5	[21]	medium	solved	5m26s
6	[23]	medium	solved	4m44s
7	[28]	hard	solved	1m27s
8	[**]		solved	4m26s
9	[22]	medium	verified	1m14s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 1

The search for $613$ proceeds from the root by repeated comparison with the keys in each visited node, following the rightmost pointer at each step since $613$ exceeds every key encountered in Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 2

Let $m=7$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 3

Let $m=101$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 4

We restart from the standard Bayer–McCreight B-tree model and make explicit the structural object being modified.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 5

We correct the analysis by rebuilding the argument from the actual insertion model and then performing a genuine worst-case optimization over all valid full nodes and all valid splits.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 6

We restart the construction in a fully TAOCP-consistent form by defining a single recursive deletion procedure in which every descent step is preceded by an invariant-preserving repair.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 7

Let $T$ and $T'$ be B-trees of order $m > 3$ such that every key in $T$ is strictly less than every key in $T'$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

TAOCP 6.2.4 Exercise 8

Working

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.4: Multiway Trees ›

A B-tree can be adapted to support retrieval by position in a linear list by augmenting each node with information about subtree sizes, so that navigation is driven by rank rather than key comparison.

TAOCP 6.2.4: Multiway Trees

Section 6.2.4. Multiway Trees

TAOCP 6.2.4 Exercise 1

TAOCP 6.2.4 Exercise 2

TAOCP 6.2.4 Exercise 3

TAOCP 6.2.4 Exercise 4

TAOCP 6.2.4 Exercise 5

TAOCP 6.2.4 Exercise 6

TAOCP 6.2.4 Exercise 7

TAOCP 6.2.4 Exercise 8

TAOCP 6.2.4 Exercise 9