AVL Trees: Balance, Rotations, Updates, and Set Operations

All flashcards

What is the AVL balance invariant?

At every node, the heights of the left and right subtrees differ by at most one.

How is a node’s AVL balance factor calculated?

Subtract the left-subtree height from the right-subtree height: $\mathrm{BF}=H_R-H_L$.

What is the worst-case time complexity of AVL search, insertion, and deletion?

$O(\log n)$ for each operation, because AVL height is logarithmic.

When does an AVL imbalance require a double rotation?

When the heavy path turns through the inner child of the taller child.

What is the precondition for joining two AVL trees around key $k$?

Every key in the left tree is less than $k$, and every key in the right tree is greater than $k$.

Quiz questions

1. What happens to the inorder sequence of keys when an AVL rotation rearranges the tree?Answer: The sequence stays the same, preserving the binary search tree ordering.
2. How does AVL retracing after insertion differ from retracing after deletion?Answer: Insertion needs at most one rebalancing point; deletion may need repairs at several levels.
3. How does the cost of one successor step compare with a complete ordered walk through an AVL tree?Answer: One step can take $O(\log n)$, while a complete walk has amortized constant cost per step.
4. Which ordering condition must hold when joining two AVL trees around key $k$?Answer: All keys in the first tree are below $k$, and all keys in the second are above $k.
5. Which comparison between AVL trees and red–black trees is accurate?Answer: Both have logarithmic basic operations, but AVL trees enforce stricter height balance.