Next Chapter Return to Table of Contents Previous Chapter


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.

Figure P.1

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.

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


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)


InCount  0

p  NextNode

while p  NIL do

InCount  InCount + 1


p  NextNode



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



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


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


Height  OneRoot

while Height > 0 do

r  Root[Height]

if r  .Right  NIL

then Height  Height - 1

else p  r .Left

Hunt  Height - 1


p  p  .Right

Hunt  Hunt = 1

until p = NIL OR p  Root[Hunt]

r  .Right  Root[Hunt]

Height  Hunt



end {0neTree




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