FUNCTIONAL PEARL On building trees with minimum height
RICHARD S. BIRD a1
a1 Programming Research Group, University of Oxford,
Wolfson Building, Parks Rd, Oxford OX1 3QD, UK
| |
AbstractA common solution to the problem of handling list indexing efficiently
in a functional
program is to build a binary tree. The tree has the given list as frontier
and is of
minimum height. Each internal node of the tree stores size information
(actually,
the size of its left subtree) to direct the search for an element at a
given position
in the frontier. One application was considered in my previous pearl (Bird,
1997).
There are two complementary methods for building such a tree, both of which
can
be implemented in linear time. One method is ‘recursive’,
or top down, and works
by splitting the list into two equal halves, recursively building a tree
for each half, and then combining the two results. The other method is
‘iterative’, or bottom up,
and works by first creating a list of singleton trees, and then
repeatedly combining
the trees in pairs until just one tree remains. The two methods lead
to different trees,
but in each case the result is a tree with smallest possible height.
|
