AVL Tree (Self-Balancing)

Self-balancing BST using rotations to maintain O(log n) height.

Status: AVL Tree Empty
Speed

Algorithm Logic

1function insert(node, key):
2 if !node: return newNode(key)
3 if key < node.key: node.left = insert(node.left, key)
4 else: node.right = insert(node.right, key)
5
6 balance = getBalance(node)
7
8 // Left Left
9 if balance > 1 and key < node.left.key:
10 return rotateRight(node)
11 // Right Right
12 if balance < -1 and key > node.right.key:
13 return rotateLeft(node)
14 // Left Right
15 if balance > 1 and key > node.left.key:
16 node.left = rotateLeft(node.left)
17 return rotateRight(node)
18 // Right Left
19 if balance < -1 and key < node.right.key:
20 node.right = rotateRight(node.right)
21 return rotateLeft(node)
22
23 return node