# what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?

in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows:

the algorithm below uses a data structure containing $P$ nodes to represent the selection tree; the $jth$ node $X[j]$ is assumed to contain $c$ words beginning in $LOC(X[j]) = L_0 + cj$, for $0$ $\le$ $j < P$, and it represents both internal node number $j$ and external node number $P + j$ in Fig.63. There are several named fields in each node:

$KEY$ = the key stored in this external node;

$RECORD$ = the record stored in this external node (including $KEY$ as a subfield)

$LOSER$ = pointer to the "loser" stored in this internal node;

$RN$ = run number of the record pointed to by $LOSER$;

$PE$ = pointer to internal node above this external node in the tree;

$PI$ = pointer to internal node above this internal node in the tree.

For example, when P = 12, internal node number 5 and external node number 17 of Fig.63 would both be represented in $X[5]$, by the fields $KEY = 170, LOSER = L_0 + 9c$ (the address of external node number 21), $PE = L_0 + 8c, PI = L_0 + 2c$

for $LOC(X[j]) = L_0 + cj$, 4 questions:

1. I need TAOCP's $MIX$ machine knowledge for understand this formula?

2. it seems that $LOC(X[j])$ is not meaning of the array or pointer, its goal is to find $X[j]$'s beginning addrss?

3. $cj$ is equal to $c * j$?

4. what's the meaning of $L_0$ ?

5. $LOC(X[5] = L_0 + 5c, LOSER = L_0 + 9c = LOC(X[9]), PE = L_0 + 8c = LOC(X[8]), PI = L_0 + 2c = LOC(X[2])$,
what's the meanings about them $LOC(X[9]),LOC(X[8]), LOC(X[2])$?

6. according to $LOSER = L_0 + 9c$ indicates that the address of external node number $21$, so that $PE = L_0 + 8c$ indicates the address of external node number $20$, and $PI$'s address of external node number $14$, but int this case of internal number 5 and external number $17$, $20$ and $14$ are unrelated to them?

## 1 Answer

The key observation may be each array element of X (regrettably called node by DEK, just as the nodes of fig. 63) representing one internal (round) and one external (rectangular) node of figure 63 with no discernible relation.
1&2) Don't think so, for this formula it should suffice to take LOC(X(j)) as the location in MIX's linear memory of (the first word of) the jth element of array X of records of c words each (see 2nd paragraph above), a natural number from 0 to 3999. (Then, there is en.wikipedia.org/wiki/MIX)
3) yes, $cj$ is consise for $c * j$
4) $L_0$ seems to be the location of the first word of all the consecutive words representing Algoritm R's data structure
5) Those LOC()-expressions denote the locations of X's elements 9, 8, and 2, resp.
6) no relation I can see: $17$ happens to be $5 + P = 5 + 12$, the parent (external, PE) of which is (internal) node 8, coincidentally represented by the same element as (external) node 20, parent (internal, PI, used to be FI(/FE) in 1st ed.) of node 5 is 2, $14 = 2 + P$ happens to share the same element of X.