AlgoVerse

AVL tree (insert)

A binary search tree that, after each insert, keeps the heights of every node's two subtrees within 1 of each other using one or two rotations.

A plain binary search tree can become a chain (height n). An AVL tree (Adelson-Velsky and Landis, 1962) requires that at every node the heights of the two subtrees differ by at most 1; so the height is always O(log n).

Read the full explanation ↓
Input:
n=0 · insert 10, insert 20, insert 30, insert 40, insert 50, insert 25PDF export

Insert 10, 20, 30, 40, 50, 25; both single and double rotations show up.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  6. self.height = 1
  9. def avl(root, ops):
  10. for op, key in ops:
  11. root = insert(root, key)
  12. return root
  15. def height(node):
  16. if node is None:
  17. return 0
  18. return node.height
  21. def insert(node, key):
  22. if node is None:
  23. return Node(key)
  24. if key < node.key:
  25. node.left = insert(node.left, key)
  26. else:
  27. node.right = insert(node.right, key)
  28. node.height = 1 + max(height(node.left), height(node.right))
  29. balance = height(node.left) - height(node.right)
  30. if balance > 1:
  31. if key > node.left.key:
  32. node.left = rotate_left(node.left)
  33. return rotate_right(node)
  34. if balance < -1:
  35. if key < node.right.key:
  36. node.right = rotate_right(node.right)
  37. return rotate_left(node)
  38. return node
  41. def rotate_right(y):
  42. x = y.left
  43. y.left = x.right
  44. x.right = y
  45. y.height = 1 + max(height(y.left), height(y.right))
  46. x.height = 1 + max(height(x.left), height(x.right))
  47. return x
  50. def rotate_left(x):
  51. y = x.right
  52. x.right = y.left
  53. y.left = x
  54. x.height = 1 + max(height(x.left), height(x.right))
  55. y.height = 1 + max(height(y.left), height(y.right))
  56. return y

Invariant: After every finished insert, each node has |left height − right height| ≤ 1, so the tree's height is O(log n).

Start

∅

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

rootNone

Orange = changed in this step

ops list

('insert', 10)('insert', 20)('insert', 30)('insert', 40)('insert', 50)('insert', 25)

Call stack

  1. avl()line 9
Step 1 of 374
Black = inserted · Orange = key stepcompare: 0/11 · create: 0/6 · inserted: 0/6 · balance: 0/11 · rotate_left: 0/3 · rotate_right: 0/1 · right_left: 0/1

    How the work grows with input size

    Average of 8 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • rotate_left
    • rotate_right
    • current input (n=6)
    02040603579111315n = number of keyscomparisonsrotate_leftrotate_right
    Show as a table
    ncomparisonsrotate_leftrotate_right
    32.80.30.6
    570.80.8
    712.91.62
    919.12.51.8
    11252.11.9
    13343.94.5
    1542.54.54.5
    Explanation

    The idea

    A plain binary search tree can become a chain (height n). An AVL tree (Adelson-Velsky and Landis, 1962) requires that at every node the heights of the two subtrees differ by at most 1; so the height is always O(log n).

    Insert

    1. Insert as in a plain tree.
    2. On the way back up to the root, update each node's height and compute its balance (left height − right height).
    3. If the balance becomes 2 or −2, fix it with rotations:
      • left–left or right–right: one single rotation.
      • left–right or right–left: two rotations (first on the child, then on the node itself).

    A rotation does not change the order of the keys (the inorder sequence), only the shape of the tree.

    What to watch in the trace

    • After each insert, the balance of the nodes on the way back up is computed; each node's height is in the memory panel.
    • Compare "sorted keys" with the same input in the plain binary search tree algorithm.