TAOCP 6.2.3: Balanced Trees

Section 6.2.3 exercises: 33/33 solved.

33 items

Section 6.2.3. Balanced Trees

Exercises from TAOCP Volume 3 Section 6.2.3: 33/33 solved.

#	Rating	Category	Status	Time
1	[01]	simple	verified	49s
2	[16]	medium	verified	2m35s
3	[M25]	math-medium	solved	1m33s
4	[M22]	math-medium	verified	56s
5	[M25]	math-medium	solved	2m33s
6	[M21]	math-medium	verified	58s
7	[**]		solved	1m18s
8	[M24]	math-medium	solved	5m06s
9	[HM44]	hm-project	solved	4m58s
10	[27]	hard	solved	4m54s
11	[M24]	math-medium	solved	4m35s
12	[24]	medium	solved	1m27s
13	[05]	simple	verified	1m31s
14	[11]	simple	solved	2m21s
15	[18]	medium	solved	1m12s
16	[20]	medium	solved	4m17s
17	[21]	medium	solved	1m13s
18	[22]	medium	solved	3m53s
19	[26]	hard	verified	3m33s
20	[40]	project	solved	4m27s
21	[30]	hard	solved	5m46s
22	[M20]	math-medium	solved	1m06s
23	[M20]	math-medium	solved	2m05s
24	[M22]	math-medium	solved	4m37s
25	[27]	hard	solved	1m14s
26	[40]	project	solved	1m36s
27	[M23]	math-medium	solved	58s
28	[41]	project	verified	1m27s
29	[M47]	math-research	solved	3m50s
30	[26]	hard	verified	1m07s
31	[34]	hard	solved	5m17s
32	[M27]	math-hard	solved	5m19s
33	[25]	medium	solved	1m15s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 1

In Case 2 the symmetric order of the keys is determined by the in-order sequence of the subtrees: all keys in the left subtree of $A$ precede $\text{KEY}(A)$, all keys in the left subtree of $B$ that...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 2

Let the search path for the insertion end at the new node $Q$, and let the path from the root $R$ to $Q$ be R = v_0, v_1, \dots, v_k = Q.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 3

Let $T$ be a balanced tree in the sense of Section 6.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 4

Let $I(T)$ denote the internal path length of a tree $T$, defined as the sum of the depths of all internal nodes of $T$, where the root has depth $0$ and each child increases depth by $1$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 5

Let the keys be $K_y, K_0, K_1, \dots, K_n$ with $K_y < K_0 < K_1 < \cdots < K_n.$ At every stage, Algorithm A inserts the new key as a leaf in the rightmost position of the current tree, since each n...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 6

Let $B_h(z)$ denote the ordinary generating function in which the coefficient of $z^n$ equals the number of balanced binary trees with $n$ internal nodes and height exactly $h$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 7

Let $B_h$ denote the number of balanced trees of height $h$, and define $C_h = B_h + B_{h-1}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 8

Let B_h := B_h(1), \qquad h \ge 0, and assume the standard recurrence for height-balanced binary trees:

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 9

Let $B_{n,h}$ denote the number of AVL (balanced) binary trees with $n$ internal nodes and height exactly $h$, and B_n=\sum_{h\ge 0} B_{n,h}.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 10

The flaw in the previous argument is that it tried to _compute_ subtree validity and heights from the balance-factor sequence before establishing that a subtree actually exists.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 11

Let $T$ be a random AVL tree produced by Algorithm A from a uniformly random permutation of $\{1,\dots,n\}$, $n>6$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 12

Let $T_7$ denote a balanced binary tree with $7$ internal nodes.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 13

Storing the index of each node as its key forces the keys to represent a global linear order.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 14

Algorithms 6.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 15

Let $T$ be the binary search tree representing an ordered linear list, with fields $\text{KEY}(P)$ and $\text{RANK}(P)$ in each node $P$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 16

The previous submission fails for one precise reason: it never instantiates the actual tree of Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 17

Let $T$ denote the balanced tree of Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 18

Unusual activity has been detected from your device.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 19

Let $S$ be the root of a balanced binary tree in the sense of Section 6.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 20

We consider binary trees in which every node $P$ satisfies the constraint B(P) = h(R(P)) - h(L(P)) \in \{0,1\}, that is,

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 21

The previous solution fails because it introduces unnecessary hierarchical structure that does not preserve the global constraint from Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 22

Let a weight-balanced tree be a binary tree in which there exists a fixed constant $0 < \alpha \le \tfrac{1}{2}$ such that for every internal node $v$ with subtree size $n(v)$, its left and right subt...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 23

Let height-balanced mean: for every node $v$, |h(L_v)-h(R_v)|\le 1, where $h(T)$ is the height of a tree $T$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 24

Let $W(x)$ denote the number of internal nodes in the subtree rooted at $x$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 25

Let $T$ be a binary search tree in which every node $x$ stores a key and a weight $w(x) = 1 + w(\mathrm{LLINK}(x)) + w(\mathrm{RLINK}(x)),$ where missing subtrees have weight $0$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 26

A $t$-ary tree is a rooted ordered tree in which each internal node has at most $t$ children.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 27

Let a 2-3 tree be defined as in Section 6.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 28

A 2-3 tree is a rooted ordered tree in which every internal node has either two or three children and contains respectively one or two keys, and in which all external nodes occur at the same level.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 29

We analyze a 2–3 tree built by inserting a random permutation of $n$ distinct keys, using the standard top-down insertion algorithm with node splitting.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 30

Let each available area be represented by a node $P$ with fields $\text{LOW}(P), \text{HIGH}(P), \text{SIZE}(P)=\text{HIGH}(P)-\text{LOW}(P)+1,$ and let all free areas be stored in a balanced binary t...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 31

The previous construction fails because it relies on a representation (a forest of perfect trees) that is not closed under splitting.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 32

We correct the proof by replacing the invalid greedy lemma with a precise structural argument based on inorder intervals.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.2.3: Balanced Trees ›

TAOCP 6.2.3 Exercise 33

Let $T$ be an AVL tree in the sense of Section 6.