Nearly Optimal Binary Search Trees

Mehlhorn, Kurt

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Nearly Optimal Binary Search Trees

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Mehlhorn, K. (1975). Nearly Optimal Binary Search Trees. Acta Informatica, 5, 287-295.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AFD5-2

Abstract

Summary We discuss two simple strategies for constructing binary search trees: Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees and choose the root so as to equalize the total weight of the left and right subtrees as much as possible, then proceed similarly on the subtres. While the former rule may yield extremely inefficient search trees, the latter rule always produces nearly optimal trees.