Published by Dimitris Kougioumtzis · Updated
Maintain subtree heights and repair left-left, left-right, right-right and right-left imbalance with rotations. Duplicate keys are ignored.
After inserting a leaf, recompute heights toward the root. Rotate an imbalanced subtree once for an outside-heavy case, or twice for an inside-heavy case. Rotations preserve the BST ordering.
When to use AVL tree insertion and rotations
Ordered sets requiring logarithmic worst-case search and insertion.
Choosing an alternative
Ordinary BST insertion can produce a chain. Red-black trees control balance through colors rather than exact subtree heights.
Worked example: input and state changes
Example input
30,10,20,40,50,5 | 20
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Attach leaf 30; update heights toward the root.
State at this checkpoint
{ "values": [ 30 ], "active": [ 0 ], "kind": "graph", "tree": true, "visited": [], "chosen": [], "heights": [ 1 ] }Step 5: Key 30: height 3, balance 2.
State at this checkpoint
{ "values": [ 30, 10, null, null, 20 ], "active": [ 0 ], "kind": "graph", "tree": true, "visited": [], "chosen": [], "heights": [ 3, 2, 0, 0, 1 ] }Step 10: Key 20: height 3, balance -1.
State at this checkpoint
{ "values": [ 20, 10, 30, null, null, null, 40 ], "active": [ 0 ], "kind": "graph", "tree": true, "visited": [], "chosen": [], "heights": [ 3, 1, 2, 0, 0, 0, 1 ] }Step 14: Left rotation at 30; promote 40.
State at this checkpoint
{ "values": [ 20, 10, 40, null, null, 30, 50 ], "active": [ 5, 2 ], "kind": "graph", "tree": true, "visited": [], "chosen": [], "heights": [ 3, 1, 2, 0, 0, 1, 1 ] }Step 19: 20 found; AVL height 3.
State at this checkpoint
{ "values": [ 20, 10, 40, 5, null, 30, 50 ], "active": [ 0 ], "kind": "graph", "tree": true, "visited": [], "chosen": [], "heights": [ 3, 2, 2, 1, 0, 1, 1 ], "result": 1, "ordered": [ 5, 10, 20, 30, 40, 50 ], "height": 3 }
Expected final state
20 found; AVL height 3.
Complexity and input bounds
Family: Trees. Time complexity: O(log n) per insertion.
Implementation detail: This view implements insertion, all four rotation cases, and search; it does not implement AVL deletion. Inputs contain at most twelve keys. Downloads return membership and serialize inorder keys, tree height, heap-position keys and node heights for structural testing.
Space complexity: O(n) auxiliary storage for node records and serialized output; saved visualization frames use additional space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..12 keys (0..99) | search key (0..99). Insert keys in order, then search.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Height of an empty subtree is zero. Update the demoted node before the promoted node after a rotation. Duplicate keys do not create extra nodes.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | // AVL insertion/search, n 0..12 keys and target 0..99; duplicate keys ignored. Returns target membership. Output capacity at least 79: [0] unique count; [1..count] inorder keys; [16] root height; [17..47] 31 heap-position keys (-1 absent); [48..78] corresponding node heights (0 absent). Empty tree height 0. All four insertion rotation cases are implemented. O(log n) per operation, O(n log n) total insertion work, O(n) auxiliary space. This view does not implement AVL deletion. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, target, output) { let key = Array(256).fill(0); let left = Array(256).fill(0); let right = Array(256).fill(0); let parent = Array(256).fill(0); let height = Array(256).fill(0); let stack = Array(256).fill(0); let position = Array(256).fill(0); let root = 0; let count = 0; let u = 0; let p = 0; let value = 0; let balance = 0; let first = 0; let last = 0; let firstRight = 0; let lastRight = 0; let x = 0; let y = 0; let beta = 0; let direction = 0; let top = 0; let length = 0; let head = 0; let tail = 0; let found = 0; for (let i = 0; i < n; i++) { value = a[i]; u = root; p = 0; while (u != 0 && key[u] != value) { p = u; if (value < key[u]) { u = left[u]; } else { u = right[u]; } } if (u != 0) { continue; } u = ++count; key[u] = value; height[u] = 1; parent[u] = p; if (p == 0) { root = u; } else if (value < key[p]) { left[p] = u; } else { right[p] = u; } u = p; while (u != 0) { height[u] = height[left[u]]; if (height[right[u]] > height[u]) { height[u] = height[right[u]]; } height[u]++; balance = height[left[u]] - height[right[u]]; first = 0; last = 0; firstRight = 0; lastRight = 0; if (balance > 1) { last = u; lastRight = 1; if (height[left[left[u]]] < height[right[left[u]]]) { first = left[u]; firstRight = 0; } } else if (balance < -1) { last = u; lastRight = 0; if (height[right[right[u]]] < height[left[right[u]]]) { first = right[u]; firstRight = 1; } } if (last != 0) { for (let turn = 0; turn < 2; turn++) { if (turn == 0 && first == 0) { continue; } x = last; direction = lastRight; if (turn == 0) { x = first; direction = firstRight; } y = right[x]; if (direction != 0) { y = left[x]; } beta = left[y]; if (direction != 0) { beta = right[y]; } p = parent[x]; if (direction != 0) { left[x] = beta; right[y] = x; } else { right[x] = beta; left[y] = x; } parent[y] = p; parent[x] = y; if (beta != 0) { parent[beta] = x; } if (p == 0) { root = y; } else if (left[p] == x) { left[p] = y; } else { right[p] = y; } height[x] = height[left[x]]; if (height[right[x]] > height[x]) { height[x] = height[right[x]]; } height[x]++; height[y] = height[left[y]]; if (height[right[y]] > height[y]) { height[y] = height[right[y]]; } height[y]++; u = y; } } u = parent[u]; } } u = root; while (u != 0 && key[u] != target) { if (target < key[u]) { u = left[u]; } else { u = right[u]; } } if (u != 0) { found = 1; } for (let i = 0; i < 79; i++) { output[i] = 0; } for (let i = 0; i < 31; i++) { output[17 + i] = -1; } output[0] = count; output[16] = height[root]; u = root; while (u != 0 || top > 0) { while (u != 0) { stack[top++] = u; u = left[u]; } u = stack[--top]; output[++length] = key[u]; u = right[u]; } if (root != 0) { stack[tail] = root; position[tail++] = 0; } while (head < tail) { u = stack[head]; p = position[head++]; output[17 + p] = key[u]; output[48 + p] = height[u]; if (left[u] != 0) { stack[tail] = left[u]; position[tail++] = 2 * p + 1; } if (right[u] != 0) { stack[tail] = right[u]; position[tail++] = 2 * p + 2; } } return found; } |
Source
Original AVL research. The playground demonstrates insertion and all four balancing cases, not a complete container library or AVL deletion.
- An algorithm for organization of information
G. M. Adel'son-Vel'skii; E. M. Landis (1962). Original research paper (Russian).