SECTION P: A BALANCED STATIC BST

Figure P.2

The general idea is to place each node at the position where it would be in a complete binary tree. This creates a forest of binary trees, and the trees of the forest are connected together into one tree after the last node has been acquired. (The dashed links in the example are created at that time.) Note that the twelfth node cannot arrive until after the eighth. In general there is only one node on each level that is not the child of a higher node. There is never more than one unattached subtree per level.

An incoming kth node is a leaf if k is odd, on the next level up if it is twice an odd number, another level up if it is divisible by 4 but not 8, and so on. (Note that 4, 12, and 20 all contain factors of 4, multiplied by an odd number.) In general, the height of the kth node, counting from the leaves, is determined by the power of the multiples of 2 that k contains. The height determination is:

`function FinalHeight(k)`

`FH  0`

`while NOT ODD(k) do`

`k  k DIV 2`

`FH  FH + 1`

`endwhile`

`return FH`

`end {FinalHeight`

Nodes are accessed by function NextNode, which is assumed to take them from a sorted file of nodes or create them from a sorted file of keys (of records perhaps). The node acquired by NextNode is inserted into a subtree. For example, the eleventh node is inserted into the subtree rooted at the tenth node and already containing the ninth node, but not yet connected as the right child of the eighth node (if the final node count is less than 12) or the left child of the twelfth node. After the last node is received, the root of the final tree is located as OneRoot, and all the subtrees are connected together by OneTree. The logic of this scheme is:

`procedure StaticBalance(OneRoot)`

`Setup`

`InCount  0`

`p  NextNode`

`while p  NIL do`

`InCount  InCount + 1`

`Insert(p)`

`p  NextNode`

`endwhile`

`OneTree(OneRoot)`

`end  {StaticBalance`

The crucial piece of the puzzle is the linking of p into some subtree. Building a complete tree one node at a time quickly shows that the kth node is not only a child of a node at the next higher level: it is a child of the last node entered at that next level that is not yet linked to both of its children. If there is no such node, the entry node becomes the root of a new tree of the forest; otherwise, it becomes the root of a subtree of a tree that is already in the forest. A structure is needed to keep track of the one subtree root per level; and an array of pointers, Root, is chosen to provide fast access to them. A maximum height of 20 allows up to 1,048,576 nodes in the forest. The initialization of Setup is then:

`for k = -1 to MaxHeight do`

`Root[k]  NIL`

`next k`

The insertion procedure is:

`procedure Insert(p)`

`Height  FinalHeight(InCount)`

`p  .Right  NIL`

`p  .Left  Root[Height - 1]`

`Root[Height]  p`

`r  Root[Height + 1]`

`if r  NIL`

`then if r  .Right = NIL`

`then r  .Right  p`

`endif`

`endif`

`end {Insert`

To find the final root of the combined tree, it suffices to search through Root for the node of greatest height that is not NIL:

`OneRoot  MaxHeight`

`while Root[OneRoot] = NIL AND OneRoot > 1 do`

`OneRoot  OneRoot -1`

`endwhile`

From the height of OneRoot, the subtrees can be systematically connected together:

`procedure OneTree(OneRoot)`

`OneRoot  MaxHeight`

`while Root[OneRoot] = NIL AND OneRoot > 1 do`

`OneRoot  OneRoot - 1`

`endwhile`

`Height  OneRoot`

`while Height > 0 do`

`r  Root[Height]`

`if r  .Right  NIL`

`then Height  Height - 1`

`else p  r .Left`

`Hunt  Height - 1`

`repeat`

`p  p  .Right`

`Hunt  Hunt = 1`

`until p = NIL OR p  Root[Hunt]`

`r  .Right  Root[Hunt]`

`Height  Hunt`

`endif`

`endwhile`

`end {0neTree`

Problem

Problem not immediate, but requiring no major extensions of the text

Program

Program for trying it yourself