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. enter image description here 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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.