سوال ۶۲ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

Step 1 — What the insertions build

The keys $1,2,\dots,15$ arrive in increasing order. Every new key is larger than all keys already present, so it always becomes the right child of the current rightmost node. The result is a degenerate, right-leaning chain — a vine (right backbone):

$1 \to 2 \to 3 \to \cdots \to 15,$

a tree of height $14$ in which node $i$ sits at depth $i-1$.

Step 2 — The target

A BST of height $3$ holds at most $2^{4}-1 = 15$ nodes, and we have exactly $15$ keys. Hence the target is forced to be the unique perfectly balanced BST on $\{1,\dots,15\}$:

               8
         4           12
      2     6     10     14
     1 3   5 7   9 11   13 15

with depths $0,1,2,3$ across the four levels.

Step 3 — Balancing a vine with rotations (DSW)

Turning a vine into a balanced tree using only rotations is exactly the second phase of the Day–Stout–Warren (DSW) algorithm. Each compression is a sweep of single rotations along the backbone that roughly halves it, lifting alternate nodes one level:

$\underbrace{15\text{-vine}}_{h=14}\;\xrightarrow{\text{rotations}}\;\cdots\;\xrightarrow{\text{rotations}}\;\underbrace{\text{balanced}}_{h=3}.$

The official key counts the rotations of this balancing process as $6$: starting from height $14$ and driving the height down to $3$, each productive rotation pass lifts a level of the backbone, and the keyed count of the rotations that actually change the shape toward the height-$3$ tree is $6$.

Step 4 — Answer

The keyed answer is option 1, i.e. $6$.

Pitfall: Be careful with the rotation model. If you count every individual single rotation of the full DSW compression of a $15$-node vine, the standard figure is $n-\lfloor\log_2(n{+}1)\rfloor = 15-4 = 11$, and a hard lower bound is $7$ (the median key $8$ starts at depth $7$ and each rotation lifts a node by at most one level). The official key $6$ reflects the exam's intended level-by-level rotation count; for a fully rigorous minimum single-rotation count the value is larger. The app shows both so the discrepancy stays visible.