TAOCP 6.2.3 Exercise 17
Let $T$ denote the balanced tree of Fig.
Exercise 17. [21] [21] Draw the balanced trees that are obtained after the Fibonacci tree (12) is concatenated (a) to the right, (b) to the left, of the tree in Fig. 20, using the concatenation algorithm suggested in the text.
480 SEARCHING 6.2.3
Verified: no
Solve time: 1m13s
Solution
Let $T$ denote the balanced tree of Fig. 20 and let $F$ denote the Fibonacci tree of order $6$, the tree in Fig. 8 (Section 6.2.1), which has $12$ internal nodes and height $5$. Both $T$ and $F$ are balanced trees of equal height.
Assume all keys in $T$ are less than all keys in $F$ for part (a), and all keys in $F$ are less than all keys in $T$ for part (b). This ordering condition determines the in-order concatenation.
The concatenation method described in Section 6.2.3 constructs a new balanced tree by linking the two trees through a node whose left and right subtrees are themselves balanced, followed by possible local rotations only when the height difference exceeds $1$. In the present case, no such imbalance arises because both input trees have identical height.
(a) Concatenation of $F$ to the right of $T$
Let $R$ be a new node whose KEY is chosen so that every key in $T$ is less than KEY$(R)$ and every key in $F$ is greater than KEY$(R)$. Define
$$ \operatorname{LLINK}(R) = \text{root}(T), \qquad \operatorname{RLINK}(R) = \text{root}(F). $$
The height of both subtrees of $R$ is $5$, so the balance factor
$$ B(R) = 5 - 5 = 0. $$
Both children already satisfy the AVL condition since they are unchanged copies of balanced trees. No node on either side experiences a change in subtree height, so no propagation of balance-factor updates occurs and no rotation of the form in cases A8 or A9 of Algorithm A is triggered.
The resulting tree has root $R$, left subtree $T$, and right subtree $F$, and is balanced.
(b) Concatenation of $F$ to the left of $T$
Let $R'$ be a new node whose KEY lies strictly between all keys of $F$ and all keys of $T$, with ordering such that every key in $F$ is less than KEY$(R')$ and every key in $T$ is greater than KEY$(R')$. Define
$$ \operatorname{LLINK}(R') = \text{root}(F), \qquad \operatorname{RLINK}(R') = \text{root}(T). $$
Again both subtrees have height $5$, hence
$$ B(R') = 5 - 5 = 0. $$
Since both subtrees are already balanced and their heights differ by $0$, the AVL balance condition is satisfied at $R'$. No structural modification beyond pointer assignment is required, and no rotations occur anywhere in the tree.
Conclusion
In both directions, the concatenation of the Fibonacci tree of order $6$ with the balanced tree of Fig. 20 reduces to the creation of a single new root whose left and right subtrees are the given trees, since their heights coincide. The AVL balance condition is preserved at the new root and unchanged elsewhere, so the resulting trees are balanced without further adjustment. ∎