Knuth says it is obvious!
Windows Research Kernel @ HPII recently scanned through the sources, looking at virtual memory management, when I found another example of good programming style: comment your code!
In file base/ntos/mm/addrsup.c one of the
responsible developers cited parts of Donald Knuth's book "The Art
of Computer Programming", Volume 3, dealing with searching and
sorting. Among others, Knuth describes AVL trees and their
implementation that are implemented in that file. When inserting a
node into an AVL tree, in some cases a re-ordering of the tree may
be necessary. The re-ordering is somewhat tricky and manifests in
three different cases.
First, have a look on case 2, according to Knuth:
// // Otherwise, we have to promote the appropriate child of R twice (Case 2 // in Knuth). (Step A9, A10) // // Here is a diagram of the Case 2 transformation, for a == +1 (a mirror // image transformation occurs when a == -1), and where the subtree // heights are h and h-1 as shown. There are actually two minor subcases, // differing only in the original balance of P (++ indicates the node out // of balance). // // | | // S++ P // / \ / \ // / \ / \ // / \ / \ // (h) R- ==> S- R // / \ / \ / \ // P+ (h) (h)(h-1)(h) (h) // / \ // (h-1) (h) // // // | | // S++ P // / \ / \ // / \ / \ // / \ / \ // (h) R- ==> S R+ // / \ / \ / \ // P- (h) (h) (h)(h-1)(h) // / \ // (h) (h-1) // // Note that on an insert we can hit this case by inserting an item in the // left subtree of R. The original height of the subtree before the insert // was h+2, and it is still h+2 after the rebalance, so insert rebalancing // may terminate. // // On a delete we can hit this case by deleting a node from the left subtree // of S. The height of the subtree before the delete was h+3, and after the // rebalance it is h+2, so rebalancing must continue up the tree. //
And finally, let's have a lesson on programming principles: the AVL tree. (Note the last sentence 🙂
/*++
Routine Description:
This routine performs a rebalance around the input node S, for which the
Balance factor has just effectively become +2 or -2. When called, the
Balance factor still has a value of +1 or -1, but the respective longer
side has just become one longer as the result of an insert or delete
operation.
This routine effectively implements steps A7.iii (test for Case 1 or
Case 2) and steps A8 and A9 of Knuth's balanced insertion algorithm,
plus it handles Case 3 identified in the delete section, which can
only happen on deletes.
The trick is, to convince yourself that while traveling from the
insertion point at the bottom of the tree up, that there are only
these two cases, and that when traveling up from the deletion point,
that there are just these three cases. Knuth says it is obvious!
// ...
Comments
Comments are closed.