TAOCP 6.3 Exercise 9
The original attempt fails mainly because it mixes abstract register notation with MIX conventions and omits the actual pointer manipulation required by Algorithm D.
Section 6.3: Digital Searching
Exercise 9. [21] [21] Write a MIX program for Algorithm D, and compare it to Program 6.2.2T. You may use binary operations such as SLB (shift left AX binary), JAE (jump if A even), etc.; and you may also use the idea of exercise 8 if it helps.
Verified: no
Solve time: 2m44s
The original attempt fails mainly because it mixes abstract register notation with MIX conventions and omits the actual pointer manipulation required by Algorithm D. A correct MIX implementation must treat nodes as memory records addressed through index registers, explicitly maintain parent links, and perform insertion by updating a child field in the parent node. The bit-guided descent must be expressed using MIX shift operations and standard condition codes.
We assume each node occupies a fixed record with fields
$$ \text{KEY},\ \text{LEFT},\ \text{RIGHT}. $$
Null pointers are $0$. A free list head is stored in $\text{AVAIL}$. We use index register $I_1$ for the current node $P$, $I_2$ for the parent node, $I_3$ for the bit index $i$, and $I_4$ to remember the last direction taken, where $0$ means left and $1$ means right.
The key idea of Algorithm D is that at level $i$, the $i$-th binary digit of $K$ determines whether we follow the left or right link. This replaces ordered comparisons by deterministic bit tests.
MIX program for Algorithm D
ENT3 1 I3 ← 1 (bit index i)
LDA K A ← search key K
STA SKEY save K
LDA ROOT
STA P P ← ROOT
D1 LDA P A ← P
JZ NEW if P = 0, insert new node
LDX P X ← P
LDA KEY, X A ← KEY[P]
CMPA SKEY
JE FOUND if equal, search succeeds
LDA SKEY
SRB I3 shift right by i bits
AND ONE isolate least significant bit
JZ GOLEFT
GORIGHT LDA P
STA I2P store parent pointer
LDA ONE
STA DIR DIR ← 1 (right)
LDA RLINK, X
STA P
JMP ADV
GOLEFT LDA P
STA I2P store parent pointer
LDA ZERO
STA DIR DIR ← 0 (left)
LDA LLINK, X
STA P
ADV ENT3 1,3 I3 ← I3 + 1
JMP D1
Insertion routine
When a null link is reached, a new node is allocated from the free list and attached to the recorded parent using the saved direction.
NEW LDA AVAIL
STA P P ← new node
LDX AVAIL
LDA LINK, X
STA AVAIL advance free list
LDA SKEY
STA KEY, X
LDA ZERO
STA LLINK, X
STA RLINK, X
LDA I2P retrieve parent
LDX I2P
LDA DIR
JZ ATTACHL
ATTACHR LDA P
STA RLINK, X
JMP FOUND
ATTACHL LDA P
STA LLINK, X
FOUND HLT
Correctness of the bit test
The instruction sequence
$$ \text{SRB } A, I_3 $$
shifts $K$ right by $i$ binary positions, placing the $i$-th bit in the least significant position. Masking with ONE isolates that bit. Thus the test correctly implements the branching rule of Algorithm D.
Comparison with Program 6.2.2T
Program 6.2.2T performs binary search tree operations using repeated key comparisons at each node. Each step requires an ordered comparison between $K$ and the current node key, and the direction of descent depends on the outcome of that comparison.
In contrast, Algorithm D eliminates ordered comparisons during descent. Once inside the tree, navigation is determined entirely by successive bits of $K$, so each level performs a fixed sequence of shift and mask operations. The only key comparison occurs at the moment a node is reached, where equality is tested.
Consequently, Program 6.2.2T has cost proportional to the number of key comparisons along a search path, while Algorithm D has cost proportional to the number of bit inspections, which is fixed by word length rather than by key distribution. This makes Algorithm D structurally uniform but dependent on the representation length of keys, whereas Program 6.2.2T is adaptive to ordering but sensitive to tree balance.