avl-flashcards

Question 1

If node A has balance factor 2 and its left child B has balance factor 1, what case is this and what rotation do we perform?

Answer 1

This is a Left-Left (LL) case. Perform a single right rotation at node A.

Question 2

If node A has balance factor -2 and its right child B has balance factor -1, what case is this and what rotation do we perform?

Answer 2

This is a Right-Right (RR) case. Perform a single left rotation at node A.

Question 3

If node A has balance factor 2 and its left child B has balance factor -1, what case is this and what rotation do we perform?

Answer 3

This is a Left-Right (LR) case. Perform two rotations: 1) single left rotation at B, 2) single right rotation at A.

Question 4

If node A has balance factor -2 and its right child B has balance factor 1, what case is this and what rotation do we perform?

Answer 4

This is a Right-Left (RL) case. Perform two rotations: 1) single right rotation at B, 2) single left rotation at A.

Question 5

How do you calculate the balance factor of a node?

Answer 5

Balance Factor = height(left subtree) - height(right subtree). Valid values are -1, 0, and 1.

Question 6

When do we need to rebalance an AVL tree?

Answer 6

When the balance factor of any node becomes less than -1 or greater than 1 (i.e., when the heights of a node’s two subtrees differ by more than 1).

Question 7

After removing a node from an AVL tree, how many rotations might be needed to rebalance?

Answer 7

Several rotations might be needed. Always choose rotation based on balance factor of the node. If child’s balance factor is 0, either single or double rotation works (single rotation will always rebalance).

Question 8

When performing rotations, what do we do with orphaned children (subtrees)?

Answer 8

If a node C is rotated to replace its parent N, and C already has a child in the direction of rotation, that child becomes the child of N in the opposite direction of rotation.

Question 9

How do we identify which rotation case we’re dealing with?

Answer 9

1) Find smallest unbalanced subtree
2) Let a be root of this subtree
3) Let b be root of a’s taller subtree
4) Let c be root of b’s taller subtree
5) Based on positions of b and c relative to a, determine case (LL, RR, LR, or RL).

Question 10

What is the time complexity of rebalancing operations (put and remove) in an AVL tree?

Answer 10

Both put and remove operations are O(log n), which includes the time to perform the actual operation and any necessary rotations.