# 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$$, 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 = L_0 + 5c, LOSER = L_0 + 9c = LOC(X), PE = L_0 + 8c = LOC(X), PI = L_0 + 2c = LOC(X)$$,
what's the meanings about them $$LOC(X),LOC(X), LOC(X)$$?

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?

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
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.