A operation on an AVL tree that fixes rotations.
Rotation Types
Drawing 2026-02-01 15.52.27.excalidraw
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠
Text Elements
5
2
7
6
9
5
2
7
6
9
Left Rotation
5
2
7
6
9
5
2
7
6
9
Right Rotation
Link to original
Left Rotation
Done if AVL Balance Factor
Right Rotation
Done if AVL Balance Factor
Left-Right Rotation
Done if AVL Balance Factor and the left subtree AVL Balance Factor
Right-Left Rotation
Done if AVL Balance Factor and right subtree AVL Balance Factor
Code
if height(v.left) - height(v.right) > 1:
let x = v.left
if height(x.left) >= height(x.right):
single left rotation: clockwise
else:
double left-right rotation: counter-clockwise then clockwise
else if height(v.right) - height(v.left) > 1:
let x = v.right
if height(x.left) <= height(x.right):
single right rotation: counter-clockwise
else:
double right-left rotation: clockwise then counter-clockwise
else:
no rotation