X-fast trie: predecessor and successor in a fixed integer universe

Last updated: 5 Oct 20269 min read

tutorial

An X-fast trie indexes fixed-width integer keys by every binary prefix length. Each prefix record stores the smallest and largest key below it, and the leaves retain their immediate predecessor and successor. An exact key is found in the leaf map. For a missing key, binary search over prefix lengths finds the deepest prefix shared with an indexed key. The next bit says whether the target fell into the absent left or right branch; subtree extrema and leaf neighbors then return its floor or ceiling. This implementation freezes the key set and uses ordinary Python dictionaries rather than promising deterministic hash-table probes. Floor and ceiling are inclusive, so a stored target returns itself.

Operational case

A catalog contains case IDs 19, 47, 83, and 149 in an eight-bit universe. The floor and ceiling of 61 are 47 and 83. An exact query for 19 returns 19 as its floor, while one for 149 returns 149 as its ceiling. Below the first ID the floor is absent; above the last ID the ceiling is absent. An out-of-universe request fails instead of silently wrapping to eight bits. Every level must describe the same frozen snapshot: inserting an ID in only the leaf table would leave the longest-prefix search with stale extrema.

Working Python program

class StaticXFastCases:
    def __init__(self, case_ids, bit_width):
        if bit_width < 1:
            raise ValueError("bit width must be positive")
        ordered = sorted(set(case_ids))
        if any(key < 0 or key >= 1 << bit_width for key in ordered):
            raise ValueError("case ID outside universe")
        self.width = bit_width
        self.levels = [dict() for _ in range(bit_width + 1)]
        self.previous = {}
        self.next = {}
        for position, key in enumerate(ordered):
            self.previous[key] = ordered[position - 1] if position else None
            self.next[key] = ordered[position + 1] if position + 1 < len(ordered) else None
            for length in range(bit_width + 1):
                prefix = key >> (bit_width - length)
                low, high = self.levels[length].get(prefix, (key, key))
                self.levels[length][prefix] = min(low, key), max(high, key)

    def floor(self, target):
        if target < 0 or target >= 1 << self.width:
            raise ValueError("target outside universe")
        if not self.previous:
            return None
        if target in self.previous:
            return target
        low, high = 0, self.width
        while low + 1 < high:
            middle = (low + high) // 2
            prefix = target >> (self.width - middle)
            if prefix in self.levels[middle]:
                low = middle
            else:
                high = middle
        prefix = target >> (self.width - low)
        smallest, largest = self.levels[low][prefix]
        missing_bit = (target >> (self.width - low - 1)) & 1
        return largest if missing_bit else self.previous[smallest]

    def ceiling(self, target):
        if target < 0 or target >= 1 << self.width:
            raise ValueError("target outside universe")
        if not self.next:
            return None
        if target in self.next:
            return target
        low, high = 0, self.width
        while low + 1 < high:
            middle = (low + high) // 2
            prefix = target >> (self.width - middle)
            if prefix in self.levels[middle]:
                low = middle
            else:
                high = middle
        prefix = target >> (self.width - low)
        smallest, largest = self.levels[low][prefix]
        missing_bit = (target >> (self.width - low - 1)) & 1
        return self.next[largest] if missing_bit else smallest


if __name__ == "__main__":
    catalog = StaticXFastCases([19, 47, 83, 149], 8)
    print(catalog.floor(61), catalog.ceiling(61))
    print(catalog.floor(19), catalog.ceiling(149))
    print(catalog.floor(7), catalog.ceiling(201))

Output

47 83
19 149
None None

Time, space, and tradeoff

Construction writes at most W+1 prefix records per key, giving O(NW) time and space for N keys of W bits. A predecessor or successor query makes O(log W) expected-time dictionary probes under ordinary hash assumptions and constant-width arithmetic; in Python, big-integer shift and hash costs also matter. A lookup can degrade with pathological hash behavior. This static teaching version omits the O(W) update procedure. A Van Emde Boas tree offers a different bounded-universe tradeoff; a sorted array is often smaller when updates are absent and logarithmic binary search is acceptable.

Common Mistakes

Do not confuse a predecessor with a lower-bound insertion position.
Do not omit the leaf-neighbor link after falling into an absent left branch.
Do not update only one prefix level after changing the key snapshot.
Do not promise a deterministic dictionary lookup bound in this Python implementation.

Connected lessons

Compare its input and update contract with Persistent radix vectors: copy one indexed path per revision, Compressed suffix trees: locate patterns across a frozen text, Disjoint interval unions: maintain covered maintenance time, then complete the structure audit and decision quiz.

data structures

range-query-structures