AlgoVerse

Splay tree

A search tree with no balance information: every key that is accessed is brought to the root by rotations, two levels at a time. Each operation costs O(log n) amortized.

A splay tree (Sleator and Tarjan) keeps no balance information. Instead, after every access the key is splayed to the root, two levels at a time:

Read the full explanation ↓
Input:
n=7 · insert 0PDF export

A left chain of seven (depth 7). Inserting 0 brings the deepest node to the root with zig-zig rotations, and the tree's depth roughly halves.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def splay_tree(root, ops):
  9. for op, key in ops:
  10. if op == "insert":
  11. root = insert(root, key)
  12. else:
  13. root = delete(root, key)
  14. return root
  17. def splay(root, key):
  18. # Brings key (or the last node on its search path) to the root, two levels at a time.
  19. if root is None or root.key == key:
  20. return root
  21. if key < root.key:
  22. if root.left is None:
  23. return root
  24. if key < root.left.key:
  25. kind = "zig-zig"
  26. root.left.left = splay(root.left.left, key)
  27. root = rotate_right(root)
  28. elif key > root.left.key:
  29. kind = "zig-zag"
  30. root.left.right = splay(root.left.right, key)
  31. if root.left.right is not None:
  32. root.left = rotate_left(root.left)
  33. if root.left is None:
  34. return root
  35. return rotate_right(root)
  36. if root.right is None:
  37. return root
  38. if key > root.right.key:
  39. kind = "zig-zig"
  40. root.right.right = splay(root.right.right, key)
  41. root = rotate_left(root)
  42. elif key < root.right.key:
  43. kind = "zig-zag"
  44. root.right.left = splay(root.right.left, key)
  45. if root.right.left is not None:
  46. root.right = rotate_right(root.right)
  47. if root.right is None:
  48. return root
  49. return rotate_left(root)
  52. def rotate_right(y):
  53. x = y.left
  54. y.left = x.right
  55. x.right = y
  56. return x
  59. def rotate_left(x):
  60. y = x.right
  61. x.right = y.left
  62. y.left = x
  63. return y
  66. def insert(root, key):
  67. root = splay(root, key)
  68. if root is not None and root.key == key:
  69. return root
  70. node = Node(key)
  71. if root is None:
  72. return node
  73. if key < root.key:
  74. node.left = root.left
  75. node.right = root
  76. root.left = None
  77. else:
  78. node.right = root.right
  79. node.left = root
  80. root.right = None
  81. return node
  84. def delete(root, key):
  85. root = splay(root, key)
  86. if root is None or root.key != key:
  87. return root
  88. if root.left is None:
  89. return root.right
  90. right = root.right
  91. root = splay(root.left, key)
  92. root.right = right
  93. return root

Invariant: The tree is always a binary search tree; after each operation the key just accessed (or its neighbour) is at the root.

Start

1234567

Recursion tree

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

Local variables

Orange = changed in this step

root object

  • key = 7
  • left = Node(key=6, left=Node(key=5, left=Node(key=4, left=…, right=None), right=None), right=None)
  • right = None

ops list

('insert', 0)

Call stack

  1. splay_tree()line 8
Step 1 of 85
Black = inserted, deleted · Orange = key stepcase: 0/3 · rotate_right: 0/6 · new_root: 0/1 · inserted: 0/1
    Explanation

    The idea

    A splay tree (Sleator and Tarjan) keeps no balance information. Instead, after every access the key is splayed to the root, two levels at a time:

    • zig-zig: the key and its parent are both left (or both right) children: rotate the grandparent first, then the parent;
    • zig-zag: one left, one right: rotate the parent first, then the grandparent;
    • zig: one level left: a single rotation.

    Why it works

    One operation can take O(n), but the amortized cost of each is O(log n) (with a potential equal to the sum of the logs of the subtree sizes). A zig-zig roughly halves the depth of the path, which is what sets splaying apart from simply rotating a node up to the root. Popular keys stay near the root.

    Insertion and deletion

    • Insert: splay k's place to the top; k becomes the root and the old tree is split in two under it.
    • Delete: splay k to the root, cut it out, and splay the left subtree's largest key to its top, so the right subtree can hang from it.

    The input

    The keys first build an ordinary search tree (possibly unbalanced), then the operations run.