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 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)
FH0
while NOT ODD(k) do
k
FH
endwhile
return FH
end {FinalHeightNodes 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
p
while pNIL do
InCount
Insert(p)
p
endwhile
OneTree(OneRoot)
end {StaticBalanceThe 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]
next k
The insertion procedure is:
procedure Insert(p)
Height
p.Right
p
Root[Height]
r
if r
then if r
then r
endif
endif
end {InsertTo 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
while Root[OneRoot] = NIL AND OneRoot > 1 do
OneRoot
endwhile
From the height of OneRoot, the subtrees can be systematically connected together:
procedure OneTree(OneRoot)
OneRoot
while Root[OneRoot] = NIL AND OneRoot > 1 do
OneRoot
endwhile
Height
while Height > 0 do
r
if r
then Height
else p
Hunt
repeat
p
Hunt
until p = NIL OR p
r
Height
endif
endwhile
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.
Program