AVL tree rotations in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of rotations in an AVL tree?

Rotations in an AVL tree are used to restore balance after insertions or deletions, ensuring the tree remains height-balanced for efficient operations.

intermediate

Describe a single right rotation in an AVL tree.

A single right rotation is performed when a left-heavy subtree causes imbalance. The left child becomes the new root of the subtree, and the original root becomes the right child of the new root.

intermediate

When is a double rotation (left-right or right-left) needed in an AVL tree?

A double rotation is needed when the subtree is unbalanced in a zig-zag pattern, such as a left-right or right-left case. It combines two single rotations to restore balance.

beginner

What is the difference between a left rotation and a right rotation in AVL trees?

A left rotation moves the right child up to become the subtree root, fixing right-heavy imbalances. A right rotation moves the left child up, fixing left-heavy imbalances.

beginner

Explain the balance factor in AVL trees and how it relates to rotations.

The balance factor is the height difference between the left and right subtrees of a node. If it becomes less than -1 or greater than 1, rotations are needed to restore balance.

What does a balance factor of +2 indicate in an AVL tree node?

A Right subtree is heavier by 2 levels

B Left subtree is heavier by 2 levels

C Tree is perfectly balanced

D Node has no children

A balance factor of +2 means the left subtree is taller by 2 levels, indicating a left-heavy imbalance.

Which rotation fixes a right-right imbalance in an AVL tree?

A Single right rotation

B Double right-left rotation

C Double left-right rotation

D Single left rotation

A right-right imbalance is fixed by a single left rotation.

What type of rotation is used to fix a left-right imbalance?

A Double left-right rotation

B Single left rotation

C Single right rotation

D Double right-left rotation

A left-right imbalance requires a double rotation: first left rotation on left child, then right rotation on the node.

After which operation do AVL tree rotations typically occur?

A Searching for a value

B Traversing the tree

C Inserting or deleting a node

D Printing the tree

Rotations occur after insertions or deletions to maintain balance.

What is the maximum allowed balance factor in an AVL tree node before rotation is needed?

A 1

B 3

C 2

D 0

The balance factor must be -1, 0, or 1. If it goes beyond ±1, rotations are needed.

Explain the four types of rotations used in AVL trees and when each is applied.

Think about left-heavy and right-heavy imbalances and zig-zag patterns.

Describe how the balance factor guides the decision to perform rotations in an AVL tree.

Focus on height differences between subtrees.

Practice

1. What is the main purpose of rotations in an AVL tree?

easy

A. To keep the tree balanced for faster search and update operations

B. To delete nodes from the tree

C. To increase the height of the tree

D. To sort the nodes in ascending order

Solution

1. Step 1: Understand AVL tree balance

   AVL trees maintain balance by ensuring the height difference between left and right subtrees is at most 1.

2. Step 2: Role of rotations

   Rotations adjust the tree structure to restore balance after insertions or deletions, improving operation speed.

3. Final Answer:

   To keep the tree balanced for faster search and update operations -> Option A

4. Quick Check:

   AVL rotations = balance tree = faster operations [OK]

Hint: Rotations fix balance to keep operations fast [OK]

Common Mistakes:

• Thinking rotations delete nodes
• Believing rotations sort nodes
• Assuming rotations increase tree height

2. Which of the following is the correct syntax to perform a right rotation on a node x in an AVL tree?

easy

A. rightRotate(x)

B. x.rightRotate()

C. rotateRight(x)

D. rotate(x, 'right')

Solution

1. Step 1: Identify common function naming

   In AVL tree implementations, the function to rotate right is commonly named rotateRight(node).

2. Step 2: Check options

   rotateRight(x) matches the common syntax. rightRotate(x) and x.rightRotate() are less standard, and rotate(x, 'right') is a generic call not typical in AVL code.

3. Final Answer:

   rotateRight(x) -> Option C

4. Quick Check:

   Right rotation function = rotateRight(node) [OK]

Hint: Look for 'rotateRight' as standard right rotation function name [OK]

Common Mistakes:

• Using method calls on node objects incorrectly
• Confusing rightRotate with rotateRight
• Using generic rotate function without direction

3. Given the following AVL tree insertion sequence: Insert 10, then 20, then 30. Which rotation will be performed to balance the tree?

medium

A. Left rotation

B. Right rotation

C. Left-Right rotation

D. Right-Left rotation

Solution

1. Step 1: Analyze insertion order and imbalance

   Inserting 10, then 20, then 30 creates a right-heavy chain (10 -> 20 -> 30), causing imbalance at 10.

2. Step 2: Determine rotation type

   This is a Right-Right case, fixed by a single left rotation at node 10.

3. Final Answer:

   Left rotation -> Option A

4. Quick Check:

   Right-heavy imbalance = left rotation [OK]

Hint: Right-heavy chain = left rotation to balance [OK]

Common Mistakes:

• Choosing right rotation for right-heavy imbalance
• Confusing Left-Right with Right-Right cases
• Ignoring the order of insertions

4. You implemented a left-right rotation but the AVL tree remains unbalanced after insertion. What is the most likely error?

medium

A. Performed rotations in wrong order

B. Used right rotation instead of left rotation

C. Inserted duplicate keys

D. Forgot to update node heights after rotation

Solution

1. Step 1: Understand rotation steps

   Left-right rotation requires two rotations and updating node heights to maintain AVL properties.

2. Step 2: Identify common mistake

   Not updating heights after rotations causes incorrect balance checks, leaving tree unbalanced.

3. Final Answer:

   Forgot to update node heights after rotation -> Option D

4. Quick Check:

   Update heights after rotations to keep balance [OK]

Hint: Always update heights after rotations [OK]

Common Mistakes:

• Doing rotations in wrong order
• Mixing up left and right rotations
• Ignoring height updates

5. After inserting nodes 30, 20, 25 into an empty AVL tree, which rotation(s) will balance the tree?

hard

A. Single left rotation at 20

B. Left-Right rotation at 30

C. Single right rotation at 30

D. Right-Left rotation at 20

Solution

1. Step 1: Analyze insertion sequence and imbalance

   Inserting 30, then 20, then 25 creates a left-right case: 30 has left child 20, which has right child 25.

2. Step 2: Identify correct rotation

   Left-right imbalance requires a left rotation on 20 followed by a right rotation on 30, called a left-right rotation.

3. Final Answer:

   Left-Right rotation at 30 -> Option B

4. Quick Check:

   Left-right case = left-right rotation [OK]

Hint: Left child with right-heavy subtree = left-right rotation [OK]

Common Mistakes:

• Choosing single rotations instead of double
• Confusing left-right with right-left cases
• Rotating wrong nodes