Binary radix routing: choose the longest matching prefix

Operational case

The service table has a fallback route, a four-bit north route, an eight-bit depot route, and a twelve-bit pump route. Service ID A947 in hexadecimal follows the pump prefix and returns pump. A983 follows the depot prefix but diverges before the pump-specific branch, so it returns depot. A key outside the north range returns fallback. Replacing a route at the same prefix changes that node's gateway without removing descendants; more-specific routes still win. A missing default route would return None when no stored prefix matches. The model uses sixteen-bit synthetic service identifiers, not address parsing or network-interface configuration.

Working Python program

class RouteNode:
    def __init__(self):
        self.children = [None, None]
        self.gateway = None


class ServiceRouteTable:
    def __init__(self, width=16):
        if width < 1:
            raise ValueError("width must be positive")
        self.width = width
        self.root = RouteNode()

    def add(self, prefix, length, gateway):
        if not 0 <= length <= self.width or not 0 <= prefix < 1 << self.width:
            raise ValueError("invalid prefix or length")
        if length < self.width and prefix & ((1 << (self.width - length)) - 1):
            raise ValueError("prefix has nonzero host bits")
        node = self.root
        for offset in range(length):
            bit = (prefix >> (self.width - offset - 1)) & 1
            if node.children[bit] is None:
                node.children[bit] = RouteNode()
            node = node.children[bit]
        node.gateway = gateway

    def lookup(self, service_id):
        if not 0 <= service_id < 1 << self.width:
            raise ValueError("service ID outside configured width")
        node = self.root
        best = node.gateway
        for offset in range(self.width):
            bit = (service_id >> (self.width - offset - 1)) & 1
            node = node.children[bit]
            if node is None:
                break
            if node.gateway is not None:
                best = node.gateway
        return best


routes = ServiceRouteTable()
routes.add(0, 0, "fallback")
routes.add(0xA000, 4, "north")
routes.add(0xA900, 8, "depot")
routes.add(0xA940, 12, "pump")
print("pump=", routes.lookup(0xA947), " depot=", routes.lookup(0xA983),
      " default=", routes.lookup(0x3901), sep="")

Output

pump=pump depot=depot default=fallback

Time, space, and tradeoff

For width W, insertion visits L bits for prefix length L and costs O(L) time, allocating at most L nodes. Lookup visits at most W nodes and costs O(W) time with O(1) extra space. Across R routes, a naive upper bound is O(RW) nodes, although shared prefixes reduce the actual count. Neither operation scans all routes. This program does not delete routes, compress one-child paths, or support concurrent updates. Fixed width is part of its contract: accepting out-of-range keys without validation could silently alias distinct integers after truncation.

Common Mistakes

• Do not return the first matching route when a deeper prefix may override it.
• Do not accept a prefix with nonzero bits outside its declared length.
• Do not confuse a longest-prefix route with exact membership in a bitwise trie.
• Do not silently truncate an identifier wider than the configured key width.

Connected lessons

• Trees and Heaps
• Data Structures
• Binary tries: choose a maximum-XOR fingerprint
• Tries: make prefix search distinct from complete-key lookup
• Compressed tries: split shared edge labels at the divergence
• Projects
• Quizzes

Compare lookup and update behavior with Bitmap hash tries: copy paths for immutable alert maps, Ternary search trees: branch by character and continue prefixes, Extendible hashing: split buckets through a shared directory, then run the index audit and contract quiz.

X-fast trie: predecessor and successor in a fixed integer universe adds a related structure with a different operation boundary.

Reduced ordered decision diagrams: share identical rule branches adds a related structure with a different operation boundary.

Patricia binary routing: compress chains without losing prefix matches examines a related structure with a different operation boundary.