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 rotationImplementations
// single rotations: right/clockwise
AVL_Node* rightRotation(AVL_Node* node) {
AVL_Node* left = node->left;
node->left = left->right;
left->right = node;
node->height = height(node);
left->height = height(left);
return left;
}
// single rotations: left/counter-clockwise
AVL_Node* leftRotation(AVL_Node* node) {
AVL_Node* right = node->right;
node->right = right->left;
right->left = node;
node->height = height(node);
right->height = height(right);
return right;
}
// double rotation: right/clockwise then left/counter-clockwise
AVL_Node* rightLeftRotation(AVL_Node* node) {
node->right = rightRotation(node->right);
return leftRotation(node);
}
// double rotation: left/counter-clockwise then right/clockwise
AVL_Node* leftRightRotation(AVL_Node* node) {
node->left = leftRotation(node->left);
return rightRotation(node);
}