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 | |||
| order | alphabetic L | minus Huffman | minus H |
| sorted by share | 6.406 | 0.000 | 0.034 |
| hot in the middle | 6.416 | 0.010 | 0.044 |
| random order 1 | 6.518 | 0.112 | 0.146 |
| random order 2 | 6.466 | 0.060 | 0.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
- Chapter 1 · The Linear Bill: Context Cost of Loading Everything and the Entropy Bound
- Chapter 2 · Building Huffman Trees: Many-Way Merging, Dummy Leaves and the Price of a Menu
- Chapter 4 · The Branching Factor: Depth against Width, and Hanging Popular Tools on the Root
- Chapter 5 · Queueing with Cold Starts: the Delay Bill of Lazy Loading and How Long to Stay Warm
- Chapter 6 · Frequency Drift: the Cost of Wrong Frequencies and When to Rebuild the Routing Tree
- Chapter 7 · Classical Sources East and West: Offices and Duties in the Rites of Zhou and Dewey's Decimal Scheme
- Chapter 8 · Closing the Loop: a Monthly Report on Catalogue Layering and Call Frequency