A TIGHT UPPER BOUND FOR THE PATH-LENGTH OF AVL TREES

被引：7
|
作者：
KLEIN, R [1 ]
WOOD, D [1 ]
机构：
[1] UNIV WATERLOO,DEPT COMP SCI,DATA STRUCTURING GRP,WATERLOO N2L 3G1,ONTARIO,CANADA
来源：
THEORETICAL COMPUTER SCIENCE | 1990年 / 72卷 / 2-3期
关键词：
D O I：
10.1016/0304-3975(90)90037-I
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We prove that the internal path length of an AVL tree of size N is bounded from above by 1.4404N(log2 N-log2log2N)+O(N) and show that this bound is achieved by an infinite family of AVL trees, each tree of which is not of maximal height. These results carry over to the comparison cost of brother trees. © 1990.
引用
收藏
页码：251 / 264
页数：14
相关论文
共 50 条
  • [1] ON THE MAXIMUM PATH-LENGTH OF AVL TREES
    KLEIN, R
    WOOD, D
    LECTURE NOTES IN COMPUTER SCIENCE, 1988, 299 : 16 - 27
  • [2] TIGHT UPPER AND LOWER BOUNDS ON THE PATH-LENGTH OF BINARY-TREES
    DESANTIS, A
    PERSIANO, G
    SIAM JOURNAL ON COMPUTING, 1994, 23 (01) : 12 - 23
  • [3] TIGHT BOUNDS ON THE PATH-LENGTH OF BINARY-TREES
    DESANTIS, A
    PERSIANO, G
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 480 : 478 - 487
  • [4] ON THE DEGREE PATH-LENGTH OF TREES
    WANG, ZY
    ACTA MATHEMATICA SCIENTIA, 1985, 5 (03) : 289 - 293
  • [5] ON THE DEGREE PATH-LENGTH OF TREES
    WANG, ZY
    KEXUE TONGBAO, 1984, 29 (02): : 277 - 277
  • [6] THE PATH-LENGTH OF BINARY-TREES
    KLEIN, R
    WOOD, D
    LECTURE NOTES IN COMPUTER SCIENCE, 1989, 367 : 128 - 136
  • [7] ON THE PATH-LENGTH OF BINARY-TREES
    KLEIN, R
    WOOD, D
    JOURNAL OF THE ACM, 1989, 36 (02) : 280 - 289
  • [8] DELETING VERTICES TO BOUND PATH-LENGTH
    PAIK, DW
    REDDY, S
    SAHNI, S
    IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (09) : 1091 - 1096
  • [9] MAXIMAL PATH-LENGTH OF BINARY-TREES
    CAMERON, H
    WOOD, D
    DISCRETE APPLIED MATHEMATICS, 1994, 55 (01) : 15 - 35
  • [10] A NOTE ON THE PATH-LENGTH OF RED BLACK TREES
    CAMERON, H
    WOOD, D
    INFORMATION PROCESSING LETTERS, 1992, 42 (05) : 287 - 292
12345