Constructing optimal search trees in optimal time

被引：2
作者：
Zheng, SQ [1 ]
Sun, M
机构：
[1] Univ Texas, Dept Comp Sci, Richardson, TX 75083 USA
[2] Covance Inc, Princeton, NJ 08540 USA
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1999年 / 48卷 / 07期
关键词：
2-3; trees; 2-3-4; algorithms; (a; b)-trees; B-trees; databases; data structures; indexing; search trees; tree construction;
D O I：
10.1109/12.780881
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
(a, b)-trees are an important class of search trees. They include 2-3 trees, 2-3-4 trees, and B-trees as subclasses. We show that a space-minimum (a, b)-tree is also height-minimum and present an optimal algorithm for constructing (a, b)-trees that are height-minimum and space-minimum. Given n keys, our algorithm constructs an (a, b)-tree with minimum height and fewest possible nodes. Our algorithm takes Theta(n) time if the keys in S are sorted and Theta(n log n) time if the keys are not sorted. We also discuss possible applications of our algorithm.
引用
收藏
页码：738 / 743
页数：6
相关论文
共 15 条
  • [1] BAYER R, 1972, ACTA INFORMATICA, V1
  • [2] BECKER P, 1994, LECT NOTES COMPUTER, V824, P49
  • [3] CORMEN TH, 1992, INTRO ALGORITHMS
  • [4] A UNIFIED APPROACH TO THE PARALLEL CONSTRUCTION OF SEARCH-TREES
    DAS, SK
    MIN, KB
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 27 (01) : 71 - 78
  • [5] DATE CJ, 1990, INTRO DATABASE SYSTE
  • [6] DEO N, 1992, P 1992 INT C PAR PRO, V3, P297
  • [7] OPTIMAL MULTI-WAY SEARCH-TREES
    GOTLIEB, L
    [J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (03) : 422 - 433
  • [8] Horowitz E., 1983, FUNDAMENTALS DATA ST
  • [9] Knuth D. E., 1973, The Art of Computer Programming Volume 3, Sorting and Searching, VIII
  • [10] Knuth Donald E., 1973, ART COMPUTER PROGRAM, V1
12