Knuth's Algorithm for AVL tree insertion

[Joe Luquette]

In Donald Knuth's "The Art of Computer Programming," vol. 3, second
edition, the author outlines an algorithm to facilitate the insertion
of a new node into a tree governed by the Adelson-Velsky and Landis
theorem.

The algorithm is arranged such that a node `s' points to the last node
on the path to the node to be inserted that has a non-zero balance
factor (B(x)). If no such node exists on the path to the new node,
then `s' points to the root of the tree.

As the last step of the insertion code, the pointer `s' is evaluated
to decide what action should be taken to balance the tree. If B(s) is
equal to zero, then we know that the subtree rooted at `s' was
balanced within a height of 1 (which defines the AVL tree, or as a
special case of the HB(x) tree, where x = 1) prior to the insertion of
the new node, and we now set B(s) appropriately depending on whether
the new node lay in the left subtree of `s' or the right. After
setting B(s) to its appropriate value, Knuth says:

LLINK(head) <-- LLINK(head) + 1 (theoretically)

or, in the MIXAL code that follows:

LDX HEAD(LLINK)
INCX 1
STX HEAD(LLINK)

I'm absolutely baffled as to why the left link of the head (which is
defined as 2 MIXAL words, or 12 bytes on a binary machine) should be
incremented by one.

I. Knuth never states anything about sequential memory alignment of
nodes,

II. This could not theoretically mean another node, because the size
of each node is defined by Knuth to be 10 words plus 2 bits, and thus
the addition of 1 would simply perturb the head's (root's) KEY field
(awful consequences pending) or the RLINK field by 1, in a
non-sequential memory stack.

So does anyone have any idea as to why Knuth adds 1 to the head node's
LLINK?

Joe

[Ben Pfaff]

anu...@hotmail.com (Joe Luquette) writes:

> I'm absolutely baffled as to why the left link of the head (which is
> defined as 2 MIXAL words, or 12 bytes on a binary machine) should be
> incremented by one.

Knuth uses the left link of the root of the tree to store the
number of nodes in the tree.
--
"In the PARTIES partition there is a small section called the BEER.
Prior to turning control over to the PARTIES partition,
the BIOS must measure the BEER area into PCR[5]."
--TCPA PC Specific Implementation Specification

[Joe Luquette]

Ben Pfaff <b...@cs.stanford.edu> wrote in message news:<87y8y5x...@pfaff.Stanford.EDU>...

> anu...@hotmail.com (Joe Luquette) writes:
>
> > I'm absolutely baffled as to why the left link of the head (which is
> > defined as 2 MIXAL words, or 12 bytes on a binary machine) should be
> > incremented by one.
>
> Knuth uses the left link of the root of the tree to store the
> number of nodes in the tree.

I feel absolutely retarded. Thank you very much.

Joe