Question bank — AVL tree — balance factor, rotations (LL, RR, LR, RL), insert, delete

True. An AVL tree is defined as a Binary Search Tree with the extra $|BF|\le 1$ rule, so it inherits every BST property including in-order sorting.

False. A BST built by inserting $1,2,3,4,5$ in order is a straight line of height $4$; its root has $|BF|=4$, violating the AVL rule.

False. The AVL rule must hold at every node, not just the root; a deep node further down could still have $|BF|=2$.

False. On insert it restores the pre-insert height (net change zero relative to before the insert); on delete a rotation can leave the subtree height unchanged, which is exactly why deletes cascade.

True. Rotations only re-point parent/child links; they never reorder keys, so the sorted sequence — the BST invariant — is preserved.

False. LR is two single rotations: rotateLeft on $z$'s left child, then rotateRight on $z$. It is a name for the pair, not a new operation.

True. An insert lengthens exactly one root-to-leaf path by one; a single fix at the lowest unbalanced node restores that path's height to its original value, so no ancestor stays unbalanced.

False. A delete shortens a subtree, which can unbalance an ancestor after the fix; rebalancing may cascade up to $O(\log n)$ times toward the root.

False. It is $-1$. This makes a leaf's height $0$ and a leaf's $BF$ come out to $0$; using $0$ shifts every $BF$ and breaks imbalance detection.

False. Its height is bounded by about $1.44{\log }_{2}n$, and can be less. It is $O(\log n)$, not a fixed formula.

True. Its node count obeys $N(h)=1+N(h-1)+N(h-2)$, the Fibonacci recurrence shifted, giving $N(h)=F_{h+3}-1$.

False. Both are balanced BSTs but use different rules; AVL keeps stricter height balance (better lookups), red-black allows looser balance (fewer rotations on updates).

False. A binary heap uses sift-up/sift-down swaps along a single path, not BST rotations; heaps aren't search trees and have no balance-factor rule.

The starting convention is wrong: empty height is $-1$, so a leaf has height $0$. The leaf's $BF$ happens to still be $0$ here, but every internal node's height is now off by one, silently mis-detecting imbalance.

Rotation choice is decided by balance factor and insertion path, not by counting nodes. A subtree can hold more nodes yet be shorter; only heights (via $BF$) determine imbalance.

$BF(z)=+2$ only says left-heavy; it doesn't distinguish LL from LR. You must also check whether the new key went into $z$'s left child's left (LL) or right (LR) subtree.

Order is reversed. After the rotation $z$ becomes the lower node, so update the child $z$ first, then the new parent $y$, otherwise $y$'s height is computed from a stale $z$.

The inner rotation (at $y$) straightens the zig-zag into a straight LL/RR line; the outer rotation (at $z$) then fixes it. Doing the outer one first cannot fix a bent path.

Removing a node can shorten a subtree, so an ancestor several levels up may become unbalanced after a lower fix. You must recheck and possibly rotate on the whole path back to the root.

With $BF(z.left)\ge 0$ (including $0$) the case is LL, not LR. The >= 0 boundary belongs to LL; only a strictly negative left-child $BF$ signals LR. The $0$ case appears only in deletes.

No re-sorting is ever needed. A rotation is designed to preserve in-order ordering, so the BST property is intact automatically; re-sorting would be redundant and could corrupt subtree links.

The sparsest tall tree is the worst case; if even the emptiest height-$h$ AVL tree needs many nodes, then $n$ nodes cannot stretch very tall. This directly upper-bounds height in terms of $n$.

Because $N(h)$ follows the Fibonacci recurrence, and Fibonacci numbers grow like ${\varphi }^k/\sqrt{5}$. Inverting that growth gives $h\le {\log }_{\varphi }n\approx 1.44{\log }_{2}n$. See Fibonacci Numbers and Big-O Notation.

A zig-zag (bent) imbalance can't be undone by a single turn; the inner rotation converts the bent LR/RL shape into a straight LL/RR shape that the outer rotation can then resolve.

Insert knows the key path it just took (left-of-left, etc.), so it uses the key. Delete has no such key path, so it reads the taller child's own $BF$ to tell straight (LL/RR) from bent (LR/RL).

Insert restores the affected subtree to its pre-insert height, so ancestors see no change. Delete can leave a subtree one shorter, propagating a height change (and possible imbalance) upward.

Heights and balance factors change only after the leaf-level modification happens. On the unwinding return path each node's updated height is finally known, so that's when we recompute $BF$ and rotate. See Tree Rotations.

A plain BST is $O(\log n)$ only on average; adversarial or sorted input degrades it to $O(n)$. AVL guarantees $O(\log n)$ in the worst case by self-balancing.

AVL keeps a tighter height bound, so searches touch fewer nodes. Red-Black Tree structures allow more slack (taller trees) in exchange for cheaper rebalancing on frequent updates.

The standard code returns the node unchanged (else: return node), so no structural change and no rebalancing occurs — heights and balance factors stay exactly as they were.

Undefined for the tree as a whole since there's no node, but as a subtree its height contributes $-1$ to a parent's $BF$ computation. You never rotate "nothing."

The tree becomes empty (root $=$ null). No rotation applies because there is no remaining node whose $BF$ could be violated.

$BF(z.left)=0$ falls under the >= 0 LL branch, so a single right rotation is used. This exact-zero situation cannot arise from an insert — it's unique to deletes shortening a subtree symmetrically.

Unlike a plain BST (which degenerates to a line of height $n-1$), the AVL keeps rotating (repeated RR/left rotations) so height stays $\approx {\log }_{2}n$ throughout.

Not necessarily. The new leaf may push some ancestor's $BF$ to $\pm 1$, which is still legal. A rotation triggers only when some node reaches $|BF|=2$.

One child is exactly one taller than the other. This maximal-skew-yet-legal shape is precisely what the minimum-node analysis $N(h)=1+N(h-1)+N(h-2)$ describes.