AlgoVerse

Splitting and joining binary search trees

Split a search tree at a key k into two trees (keys below and above k), then join the two again; both O(h). A split followed by a join deletes k.

SPLIT(t, k) cuts a search tree into three parts: a tree small with the keys below k, the node k (if present), and a tree big with the keys above k. Only k's search path is walked:

Read the full explanation ↓
Input:
A 1×10 · k=40PDF export

A tree of 10 keys with k = 40; the search path for 40 cuts the tree in two, then small's largest key, 35, becomes the joined tree's root.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def split_join(A, k):
  9. root = build(A[0])
  10. small, mid, big = split(root, k)
  11. found = mid is not None
  12. root = None
  13. root = join(small, big)
  14. small = None
  15. big = None
  16. keys = []
  17. inorder(root, keys)
  18. return keys
  21. def split(t, k):
  22. # Returns the keys < k, the node with key k (or None), and the keys > k, as three search trees.
  23. if t is None:
  24. return None, None, None
  25. if k < t.key:
  26. s, m, b = split(t.left, k)
  27. t.left = b
  28. return s, m, t
  29. if k > t.key:
  30. s, m, b = split(t.right, k)
  31. t.right = s
  32. return t, m, b
  33. s, b = t.left, t.right
  34. t.left = None
  35. t.right = None
  36. return s, t, b
  39. def join(small, big):
  40. # Every key in small is below every key in big. The largest key of small becomes the new root.
  41. if small is None:
  42. return big
  43. parent = None
  44. m = small
  45. while m.right is not None:
  46. parent = m
  47. m = m.right
  48. if parent is None:
  49. small = m.left
  50. else:
  51. parent.right = m.left
  52. m.left = small
  53. m.right = big
  54. return m
  57. def inorder(t, keys):
  58. if t is not None:
  59. inorder(t.left, keys)
  60. keys.append(t.key)
  61. inorder(t.right, keys)
  64. def build(keys):
  65. root = None
  66. for key in keys:
  67. node = Node(key)
  68. if root is None:
  69. root = node
  70. continue
  71. p = root
  72. while True:
  73. if key < p.key:
  74. if p.left is None:
  75. p.left = node
  76. break
  77. p = p.left
  78. else:
  79. if p.right is None:
  80. p.right = node
  81. break
  82. p = p.right
  83. return root

Invariant: In a split, each node on k's search path goes to small or big with one of its subtrees intact; every key in small is below k and every key in big above it.

Start

root

∅

small

∅

big

∅

Recursion tree

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

Local variables

k40

Orange = changed in this step

A list

[50, 30, 70, 20, 40, 60, 80, 35, 45, 65]

Call stack

  1. split_join()line 8
Step 1 of 280
Black = split_done, joined · Orange = key stepbuilt: 0/1 · found: 0/1 · keep_left: 0/1 · keep_right: 0/1 · split_done: 0/1 · find_max: 0/1 · unlink_max: 0/1 · new_root: 0/1 · joined: 0/1
    Explanation

    Splitting

    SPLIT(t, k) cuts a search tree into three parts: a tree small with the keys below k, the node k (if present), and a tree big with the keys above k. Only k's search path is walked:

    • if k < t.key, node t goes to big with its right subtree, and the split goes on in the left subtree;
    • if k > t.key, the other way round: t goes to small with its left subtree.

    Joining

    JOIN(small, big) merges two trees where every key of the first is below every key of the second: take out small's largest node and make it the new root, with small on its left and big on its right. With a middle key m in hand (a three-way join) it is simpler still: m becomes the root.

    Cost

    Both walk a single path from the root down: O(h). These two operations underlie treaps, splay trees, and sets with union and intersection.

    The input

    A is the insertion order of the keys and k the key to split at.