# Knuth says it is obvious!

Windows Research Kernel @ HPI

I 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! // ... ```