Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Ordered treaps: split, join, and select depot keys

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An ordered treap keeps binary-search order by integer key and max-heap order by an independently assigned priority. Split partitions a tree around a boundary, reattaching only nodes on one search path. Join consumes two trees whose every left key is below every right key; it keeps the higher-priority root and recursively joins one child. Each node caches its subtree size, allowing zero-based select to choose a key by rank. The sample assigns priorities from a fixed seed solely to make the trace repeatable. A deployed randomized treap should draw priorities independently and protect the generator and state according to its concurrency needs. Split and join mutate their input nodes; callers cannot keep treating old roots as intact snapshots. Duplicate keys are ignored, and the integer-key removal uses a key-plus-one boundary.

Operational case

Insert depot keys 61, 19, 83, 47, and 29. Splitting at 47 produces [19,29] and [47,61,83]; joining those two returns the same ordered set. Remove key 61, then selecting zero-based position two returns 47. If the caller reverses the join arguments, the binary-search invariant is broken even though heap priorities may appear plausible. The size cache must be repaired after every changed child pointer or rank results silently drift. A duplicate insertion must not add another node under the same key. The example never accepts arbitrary string keys because removal's successor boundary is defined using integer addition.

Working Python program

python
from dataclasses import dataclass
from random import Random


@dataclass
class DepotNode:
    key: int
    priority: int
    left: "DepotNode | None" = None
    right: "DepotNode | None" = None
    size: int = 1


def count(node):
    return 0 if node is None else node.size


def repair(node):
    if node is not None:
        node.size = 1 + count(node.left) + count(node.right)
    return node


def split(node, boundary):
    """Return keys below boundary and keys at or above it."""
    if node is None:
        return None, None
    if node.key < boundary:
        node.right, upper = split(node.right, boundary)
        return repair(node), upper
    lower, node.left = split(node.left, boundary)
    return lower, repair(node)


def join(lower, upper):
    """Consume two trees whose key ranges do not overlap."""
    if lower is None or upper is None:
        return lower if upper is None else upper
    if lower.priority >= upper.priority:
        lower.right = join(lower.right, upper)
        return repair(lower)
    upper.left = join(lower, upper.left)
    return repair(upper)


def contains(node, key):
    while node is not None:
        if node.key == key:
            return True
        node = node.left if key < node.key else node.right
    return False


def insert(node, key, priority):
    if contains(node, key):
        return node
    lower, upper = split(node, key)
    return join(join(lower, DepotNode(key, priority)), upper)


def remove(node, key):
    lower, rest = split(node, key)
    middle, upper = split(rest, key + 1)
    return join(lower, upper), middle is not None


def select(node, position):
    if position < 0 or position >= count(node):
        raise IndexError(position)
    while node is not None:
        left_count = count(node.left)
        if position < left_count:
            node = node.left
        elif position == left_count:
            return node.key
        else:
            position -= left_count + 1
            node = node.right
    raise AssertionError("unreachable")


def ordered(node):
    return [] if node is None else ordered(node.left) + [node.key] + ordered(node.right)


priority_source = Random(947)
depot_root = None
for depot_key in (61, 19, 83, 47, 29):
    depot_root = insert(depot_root, depot_key, priority_source.getrandbits(48))
left_group, right_group = split(depot_root, 47)
print("split:", ordered(left_group), ordered(right_group))
depot_root = join(left_group, right_group)
depot_root, removed = remove(depot_root, 61)
print("rank two:", select(depot_root, 2), "removed:", removed)
print("ordered:", ordered(depot_root))

Output

Output
split: [19, 29] [47, 61, 83]
rank two: 47 removed: True
ordered: [19, 29, 47, 83]

Time, space, and tradeoff

For independent random priorities, expected tree height is O(log N), so search, split, join, insert, remove, and select take expected O(log N) time and O(log N) recursive stack space. An unlucky priority sequence can make height O(N) and can exceed Python's recursion limit; no deterministic balancing guarantee is claimed. The N nodes and size fields use O(N) space. This is a mutable ordered set, while an implicit treap keys by sequence position and a persistent ordered tree copies paths instead of consuming roots. If a workload needs strict worst-case height, an AVL or red-black tree has a different repair contract.

Common Mistakes

  • Do not join trees whose key ranges overlap or arrive in the wrong order.
  • Do not reuse a consumed split root as an unchanged version.
  • Do not forget to repair subtree sizes after pointer changes.
  • Do not call expected logarithmic height a worst-case guarantee.

Connected lessons

Compare this operation boundary with Span skip lists: rank and select without a full scan, Two-dimensional segment trees: correct sensors and sum rectangles, Range-majority indexes: verify a candidate before returning it, then complete the structure audit and decision quiz.

data structures
range-query-structures
Storage details