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

被引:0
|
作者
Abuali, Faris N. [1 ]
Wainwright, Roger L. [1 ]
机构
[1] Univ of Tulsa, Tulsa, United States
关键词
Algorithms - Costs - Software engineering;
D O I
暂无
中图分类号
学科分类号
摘要
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 fields 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.
引用
收藏
页码:1267 / 1283
相关论文
共 50 条
  • [41] Optimal path and minimal spanning trees in random weighted networks
    Braunstein, Lidia A.
    Wu, Zhenhua
    Chen, Yiping
    Buldyrev, Sergey V.
    Kalisky, Tomer
    Sreenivasan, Sameet
    Cohen, Reuven
    Lopez, Eduardo
    Havlin, Shlomo
    Stanley, H. Eugene
    INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS, 2007, 17 (07): : 2215 - 2255
  • [42] ADDITIONAL COMMENTS ON FITCH AND SMITH CONJECTURE FOR MINIMAL LENGTH TREES
    MCMORRIS, FR
    NEUMANN, DA
    SYSTEMATIC ZOOLOGY, 1983, 32 (03): : 278 - 278
  • [43] ESTIMATING THE LENGTH OF MINIMAL SPANNING-TREES IN COMPRESSION OF FILES
    ERNVALL, J
    NEVALAINEN, O
    BIT, 1984, 24 (01): : 19 - 32
  • [44] Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees
    J. H. Rubinstein
    J. Weng
    N. Wormald
    Journal of Global Optimization, 2006, 35 : 573 - 592
  • [45] Approximations and lower bounds for the length of minimal Euclidean Steiner trees
    Rubinstein, J. H.
    Weng, J.
    Wormald, N.
    JOURNAL OF GLOBAL OPTIMIZATION, 2006, 35 (04) : 573 - 592
  • [46] A NEW CLASS OF BALANCED SEARCH-TREES - HALF-BALANCED BINARY SEARCH-TREES
    OLIVIE, HJ
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1982, 16 (01): : 51 - 71
  • [47] ALPHABETIC-EXTENDED BINARY TREES WITH RESTRICTED PATH LENGTH
    ZHU, YJ
    WANG, JF
    SCIENTIA SINICA, 1979, 22 (12): : 1362 - 1371
  • [48] ON ALPHABETIC-EXTENDED BINARY TREES WITH RESTRICTED PATH LENGTH
    朱永津
    王建方
    Science China Mathematics, 1979, (12) : 1362 - 1371
  • [49] TIGHT BOUNDS ON THE PATH-LENGTH OF BINARY-TREES
    DESANTIS, A
    PERSIANO, G
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 480 : 478 - 487
  • [50] Randomized K-dimensional binary search trees
    Duch, A
    Estivill-Castro, V
    Martínez, C
    ALGORITHMS AND COMPUTATIONS, 1998, 1533 : 199 - 208