Hostname: page-component-7c8c6479df-5xszh Total loading time: 0 Render date: 2024-03-18T08:19:56.828Z Has data issue: false hasContentIssue false

FUNCTIONAL PEARL On building trees with minimum height

Published online by Cambridge University Press:  01 July 1997

RICHARD S. BIRD
Affiliation:
Programming Research Group, University of Oxford, Wolfson Building, Parks Rd, Oxford OX1 3QD, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A 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.

Type
Research Article
Copyright
© 1997 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.