Self-Balancing Tree • AVL Tree

AVL Tree Visualization

A height-balanced Binary Search Tree (BST) named after inventors Adelson-Velsky and Landis. The difference between subtree heights (Balance Factor) for any node cannot exceed ±1.

Abstract Data Type Properties

Standard BSTs can degenerate into O(n) skewed lines. AVL Trees prevent skewing by calculating the Balance Factor (BF = Height(Left) - Height(Right)) on every mutation and executing rotations (LL, RR, LR, RL) to maintain guaranteed O(log n) search, insertion, and deletion.

Invariant
|BF| ≤ 1 for all nodes
Search / Insert / Delete
O(log n) Guaranteed
Rebalancing
4 Rotation Types (LL, RR, LR, RL)

Operations Panel

1. Insertions, Deletions & Rebalancing
2. Tree Queries & Node Inspection
Self-Balancing Binary Search Tree Canvas
Perform an operation to inspect tree state and balance factors

Educational Reference: Rotations & Balancing

Left-Left (LL) Rotation → Right Rotation

Triggered when a node is inserted into the left subtree of the left child (BF = +2, Child BF = +1). Resolved with a single Right Rotation around the unbalanced node.

Right-Right (RR) Rotation → Left Rotation

Triggered when a node is inserted into the right subtree of the right child (BF = -2, Child BF = -1). Resolved with a single Left Rotation around the unbalanced node.

Left-Right (LR) Double Rotation

Triggered when a node is inserted into the right subtree of the left child (BF = +2, Child BF = -1). Resolved via a Left Rotation on Child followed by a Right Rotation on Parent.

Right-Left (RL) Double Rotation

Triggered when a node is inserted into the left subtree of the right child (BF = -2, Child BF = +1). Resolved via a Right Rotation on Child followed by a Left Rotation on Parent.