Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Nearly Optimal Binary Search Trees

MPG-Autoren
/persons/resource/persons45021

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-AFD5-2
Zusammenfassung
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.