FAST MERGING ALGORITHM

被引：55

作者：

BROWN, MR ^{[1
]}

TARJAN, RE ^{[1
]}

机构：

[1] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305

来源：

JOURNAL OF THE ACM | 1979年 / 26卷 / 02期

关键词：

2-3; tree; AVL tree; height-balanced tree; linear list; merging;

D O I：

10.1145/322123.322127

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

An algonthm that merges sorted hsts represented as height-balanced binary trees 1s given If the hsts have lengths m and n [formula omitted] then the merging procedure runs m O(m log(n/m)) steps, which is the same order as the lower bound on all companson-based algorithms for this problem. © 1979, ACM. All rights reserved.

引用

页码：211 / 226

页数：16

共 12 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

BROWN MR, 1978, 10TH P STOC SAN DIEG, P19

[3]

BROWN MR, 1977, STANCS77625 STANF U

[4]

CRANE CA, 1972, THESIS STANFORD U

[5]

Hwang FK., 1972, SIAM J COMPUT, V1, P31, DOI 10.1137/0201004

[6]

Knuth D. E., 1974, Computing Surveys, V6, P261, DOI 10.1145/356635.356640

[7]

Knuth D. E., 1976, SIGACT News, V8, P18, DOI 10.1145/1008328.1008329

[8]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[9]

REISER JF, 1976, STANCS76575 STANF U

[10]

TARJAN RE, 1977, 9TH P ANN ACM S THEO, P19

← 1 2 →