A static BST that is quite well balanced can be formed from a set of nodes by first sorting them and then arranging them in a tree according to their sorted order. The first 11 nodes can be placed in trees like those of Figure P.1 as they arrive.

If node 10 is made the right child of node 8, the result is a BST. If node 12 had arrived before the final connection, node 10 would be its left child and node 12 would be the right child of node 8. After arrival of node 13 and after final connection, the tree would look like the one in 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 *k*th 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 *k*th 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 *k*th 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

Program

## Problem

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

**PP.1** Trace the action on *OneTree* when a total of *k* nodes are entered into *StaticBalance* for *k* values 11, 12, and 13.

Program for trying it yourself

**PGP.1** Incorporate the algorithm *StaticBalance* into a program (with a tree display) and experiment with it.

Go to Section Q Return to Table of Contents