Insert keys and watch where the balance tips and which rotation (single or double) restores it. With the «Without balancing» switch you see the same sequence in a plain binary search tree.
The principle
Every node has a balance b = height of right subtree − height of left subtree. Allowed values are −1, 0 and +1. After each insertion the path back to the root is checked. Wherever b reaches ±2, a rotation restores the condition.
| Case | Detection | Action |
|---|---|---|
| Left-Left | b = −2, left child b ≤ 0 | Right rotation |
| Right-Right | b = +2, right child b ≥ 0 | Left rotation |
| Left-Right | b = −2, left child b > 0 | Left rotation at the child, then right rotation |
| Right-Left | b = +2, right child b < 0 | Right rotation at the child, then left rotation |
The first two cases are single rotations, the last two are double rotations. In the tree «Without balancing», ascending keys grow a list; with AVL the height stays logarithmic.
Python code
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
self.height = 1
def height(n):
return n.height if n else 0
def balance(n):
return height(n.right) - height(n.left) # b = h(right) - h(left)
def update(n):
n.height = 1 + max(height(n.left), height(n.right))
def rotate_right(y):
x = y.left
y.left, x.right = x.right, y
update(y)
update(x)
return x # x is the new root of this subtree
def rotate_left(x):
y = x.right
x.right, y.left = y.left, x
update(x)
update(y)
return y
def rebalance(n):
update(n)
b = balance(n)
if b < -1: # left side too high
if balance(n.left) > 0: # left-right kink: first turn it into a line
n.left = rotate_left(n.left)
return rotate_right(n)
if b > 1: # right side too high
if balance(n.right) < 0: # right-left kink
n.right = rotate_right(n.right)
return rotate_left(n)
return n
def insert(n, key):
if n is None:
return Node(key)
if key < n.key:
n.left = insert(n.left, key)
elif key > n.key:
n.right = insert(n.right, key)
return rebalance(n) # on the way back up: fix every node on the path
Usage: root = None, then root = insert(root, 10) for each key. To check the height, read root.height.