Scribd
Upload
76 views7 pages

Types of AVL Tree Rotations Explained

AVL rotations are used in AVL trees to maintain balance after insertions or deletions, ensuring the height difference between left and right subtrees is at most 1. There are four types of rotations: right rotation, left rotation, left-right rotation, and right-left rotation, each addressing specific imbalance cases. The document outlines the conditions for each rotation type and provides examples of when to apply them.

Uploaded by

sadiqsofia23
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
76 views7 pages

Types of AVL Tree Rotations Explained

AVL rotations are used in AVL trees to maintain balance after insertions or deletions, ensuring the height difference between left and right subtrees is at most 1. There are four types of rotations: right rotation, left rotation, left-right rotation, and right-left rotation, each addressing specific imbalance cases. The document outlines the conditions for each rotation type and provides examples of when to apply them.

Uploaded by

sadiqsofia23
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

AVL ROTATION

AVL ROTATIONS ARE OPERATIONS USED IN AVL TREES (A TYPE OF SELF-BALANCING BINARY SEARCH TREE) TO
MAINTAIN BALANCE AFTER INSERTION OR DELETION. AVL TREES MAINTAIN A STRICT BALANCE: FOR ANY
NODE, THE HEIGHTS OF THE LEFT AND RIGHT SUBTREES CAN DIFFER BY AT MOST 1.

BALANCE FACTOR

WHEN AN OPERATION (INSERTION/DELETION) CAUSES THIS

BALANCE FACTOR= (HEIGHT(LEFT SUBTREE) - HEIGHT(RIGHT SUBTREE))

TO BECOME LESS THAN -1 OR GREATER THAN +1, THE TREE MUST BE REBALANCED USING ROTATIONS.
TYPES OF AVL ROTATION

• THERE ARE FOUR TYPES OF AVL ROTATIONS:


• 1. RIGHT ROTATION (SINGLE ROTATION)
• 2. LEFT ROTATION (SINGLE ROTATION)
• 3. LEFT-RIGHT ROTATION (DOUBLE ROTATION)
• 4. RIGHT-LEFT ROTATION (DOUBLE ROTATION)
1. RIGHT ROTATION (SINGLE ROTATION)
• USED WHEN: LEFT-HEAVY → IMBALANCE CAUSED IN THE LEFT CHILD’S LEFT SUBTREE (LL CASE)

• INSERTIONS: 10 → 20 → 30

• BEFORE:
• INSERTING 30 INTO THE RIGHT OF 20 MAKES 10 UNBALANCED.

• BALANCE FACTOR AT 10 IS -2 (RIGHT-HEAVY).

• RIGHT-RIGHT CASE → PERFORM LEFT ROTATION ON 10 .


AFTER:
2. LEFT ROTATION (SINGLE ROTATION)

• USED WHEN: RIGHT-HEAVY → IMBALANCE CAUSED IN THE RIGHT CHILD’S


RIGHT SUBTREE (RR CASE)
• INSERTION 30 20 10
• BEFORE:
• INSERTING 10 INTO THE LEFT OF 20 MAKES 30 UNBALANCED.
• · BALANCE FACTOR AT 30 IS 2 (LEFT-HEAVY).
• · LEFT-LEFT CASE → PERFORM RIGHT ROTATION ON 30.
AFTER
3. LEFT-RIGHT ROTATION (DOUBLE ROTATION)

• USED WHEN: LEFT-HEAVY → IMBALANCE CAUSED IN THE LEFT CHILD’S


RIGHT SUBTREE (LR CASE)
• INSERTIONS: 30 → 10 → 20
• BEFORE:
• INSERTING 20 INTO RIGHT OF 10 MAKES 30 UNBALANCED.
• BALANCE FACTOR AT 30 IS 2 (LEFT-HEAVY), BUT 10'S RIGHT CHILD CAUSES IT
→ LEFT-RIGHT CASE.
• FIX:
• LEFT ROTATION ON 10
• RIGHT ROTATION ON 30
AFTER:
4. RIGHT-LEFT ROTATION (DOUBLE ROTATION)
• USED WHEN: RIGHT-HEAVY → IMBALANCE CAUSED IN THE RIGHT CHILD’S
LEFT SUBTREE (RL CASE)
• INSERTIONS: 10 → 30 → 20
• BEFORE:
• INSERTING 20 INTO LEFT OF 30 MAKES 10 UNBALANCED.
• BALANCE FACTOR AT 10 IS -2 (RIGHT-HEAVY), BUT 30'S LEFT CHILD CAUSES IT
→ RIGHT-LEFT CASE.
• FIX:
• RIGHT ROTATION ON 30
• LEFT ROTATION ON 10
AFTER:
SUMMARY TABLE:

Case Tree Skewed Rotation(s) Needed

LL Left-Left Right Rotation

RR Right-Right Left Rotation

LR Left-Right Left + Right

RL Right-Left Right + Left

You might also like