What does Lazy Tool Hubs conclude, in numbers, about “Navigable Trees: the Price of Alphabetic Order and the Accumulation of Wrong Turns”?

Answer: A navigable tree must keep a semantic order. In theory this costs at most about one decision more than a Huffman tree; under a Zipf distribution, program p31 finds the real cost to be only about a tenth of a decision, 0.112 in a random order. The real uncertainty lies in wrong turns: whether a routing tree raises accuracy depends on how errors change with menu length, and that law has not yet been reliably measured in public. The next chapter sets accuracy aside for the moment and returns to tokens and round trips to ask a more practical question: given three hundred tools, how many levels should there be, how wide should each be, and which tools deserve to hang directly on the root?

Scope of the numbers: Selection accuracy lacks reliable peer-reviewed primary evidence and is demoted to an author's hypothesis. Marked boxes separate published evidence, runnable Python calculations (17 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.112

H = 6.372 bits; Huffman L = 6.406
orderalphabetic Lminus Huffmanminus H
sorted by share6.4060.0000.034
hot in the middle6.4160.0100.044
random order 16.5180.1120.146
random order 26.4660.0600.094
Gilbert-Moore bound: alphabetic L < H + 2 = 8.372
Show the full program
# Chapter 3. p31: the price of a tree that can be navigated by meaning.
# A Huffman tree groups tools by frequency, so its inner nodes have no
# meaning a router could read. A navigable tree must keep tools in a
# fixed semantic order (adjacent tools share a parent): an alphabetic
# tree (Gilbert and Moore 1959; Hu and Tucker 1971). The optimal one is
# found here by interval dynamic programming. N = 300 tools; Zipf(1)
# shares placed in four orders (seeded shuffles are illustrative).
import heapq
import math
import random

rng = random.Random(20261113)
N = 300


def zipf(n, a):
    w = [1.0 / (i ** a) for i in range(1, n + 1)]
    t = math.fsum(w)
    return [x / t for x in w]


def entropy(p):
    return -math.fsum(x * math.log2(x) for x in p if x > 0)


def huff_l(p):
    items = [(x, i) for i, x in enumerate(p)]
    heapq.heapify(items)
    seq, terms = len(p), []
    while len(items) > 1:
        a, b = heapq.heappop(items), heapq.heappop(items)
        w = a[0] + b[0]
        terms.append(w)
        heapq.heappush(items, (w, seq))
        seq += 1
    return math.fsum(terms)


def alpha_l(p):
    n = len(p)
    pre = [0.0]
    for i in range(n):
        pre.append(math.fsum(p[:i + 1]))
    cost = [[0.0] * n for _ in range(n)]
    root = [[i] * n for i in range(n)]
    for span in range(2, n + 1):
        for i in range(n - span + 1):
            j = i + span - 1
            lo = root[i][j - 1]
            hi = root[i + 1][j] if i + 1 <= j else j - 1
            best, arg = None, lo
            for m in range(lo, min(hi, j - 1) + 1):
                c = cost[i][m] + cost[m + 1][j]
                if best is None or c < best:
                    best, arg = c, m
            cost[i][j] = best + (pre[j + 1] - pre[i])
            root[i][j] = arg
    return cost[0][n - 1]


base = zipf(N, 1.0)
orders = [("sorted by share", list(base))]
mid = sorted(base)
orders.append(("hot in the middle", mid[0::2] + mid[1::2][::-1]))
for s in range(2):
    q = list(base)
    rng.shuffle(q)
    orders.append(("random order %d" % (s + 1), q))
h = entropy(base)
print("H = %.3f bits; Huffman L = %.3f" % (h, huff_l(base)))
print("order               alphabetic L  minus Huffman  minus H")
for name, q in orders:
    a = alpha_l(q)
    print("%-19s %12.3f %13.3f %9.3f"
          % (name, a, a - huff_l(base), a - h))
print("Gilbert-Moore bound: alphabetic L < H + 2 = %.3f" % (h + 2))

Single source and citation

Fan, Y. (2026). A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees (Version 1.0.0), Chapter 3: Navigable Trees: the Price of Alphabetic Order and the Accumulation of Wrong Turns. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-257 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026257,
  author    = {Fan, Yafu},
  title     = {A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book