ISA [k] trees: A class of binary search trees with minimal or near minimal internal path length

Autor: Roger L. Wainwright, Faris N. Abuali
Rok vydání: 1993
Předmět:
Zdroj: Software: Practice and Experience. 23:1267-1283
ISSN: 1097-024X
0038-0644
DOI: 10.1002/spe.4380231106
Popis: In recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [k] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[k] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[k] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.
Databáze: OpenAIRE
Externí odkaz: