Updating approximately complete trees. (English) Zbl 0884.68094

Summary: We define a \(k\)-incomplete binary search tree to be a tree in which any two external nodes are no more than \(k\) levels apart; we say that it is approximately complete. Whereas we show that 1-incomplete binary search trees have an amortized cost of \(\Theta(n)\), we demonstrate that 2-incomplete binary search trees have an amortized update cost of \(O(\log^2n)\). Thus, they are an attractive alternative for those situations that require fast retrieval (that is, \(\log n+O(1)\) comparisons) and have few updates.


68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI EuDML


[1] 1. G. M. ADEL’SON-VEL’SKII and E. M. LANDIS, An algorithm for the organization of information, Sov. Math. Dokl., 19623, pp. 1259-1262.
[2] 2. A. ANDERSSON, Improving partial rebuilding by using simple balance criteria, In Proceedings of the 1989 Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 1989, 447, Springer-Verlag, pp. 393-402. Zbl0767.68016 · Zbl 0767.68016
[3] 3. A. ANDERSSON, Efficient Search Trees, PhD thesis, Lund University, Sweden, 1990.
[4] 4. A. ANDERSSON and T. W. LAI, Comparison-efficient and write-optimal searching and sorting, In Proceedings of the 2nd Annual International Symposium on Algorithms, Lecture Notes in Computer Science, 1991, 557, Springer-Verlag, pp. 273-282. MR1236261
[5] 5. T. E. GERASCH, An insertion algorithm for a minimal internal path length binary search tree, Communications of the ACM, 1988, 31, pp. 579-585.
[6] 6. L. C. GUIBAS and R. SEDGEWICKA dichromatic framework for balanced trees, In Proceedings of the 19th Annual IEEE Sympossium on Foundations of Computer Science, 1978, pp. 8-21. MR539826
[7] 7. T. W. H. LAI, Efficient Maintenance of Binary Search Trees, Ph. D thesis, University of Waterloo, 1990.
[8] 8. T. W. H. LAI and D. WOOD, Updating approximately complete trees, Technical Report CS-89-57, University of Waterloo, 1989. · Zbl 0884.68094
[9] 9. T. W. H. LAI and D. WOOD, Updating almost complete trees or one level makes all the difference, In Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 1990, 415, Springer-Verlag, pp. 188-194. Zbl0729.68013 MR1063313 · Zbl 0729.68013
[10] 10. J. I. MUNRO, Private communication.
[11] 11. J. NIEVERGELT and E. M. REINGOLD, Binary search trees of bounded balance, SIAM Journal on Computing, 1973, 2, pp. 33-43. Zbl0262.68012 MR331903 · Zbl 0262.68012 · doi:10.1137/0202005
[12] 12. M. H. OVERMARS, The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science, 1983, Springer-Verlag. Zbl0545.68009 MR710832 · Zbl 0545.68009
[13] 13. M. H. OVERMARS and J. VAN LEEUWEN, Dynamic multi-dimensional datta structures based on quad- and k-d trees, Acta Informatica, 1982, 17, pp. 267-285. Zbl0489.68055 MR673628 · Zbl 0489.68055 · doi:10.1007/BF00264354
[14] 14. E. M. REINGOLD and W. J. HANSEN, Data Structures in Pascal, Little, Brown and Company, 1986.
[15] 15. Q. F. STOUT and B. L. WARREN, Tree rebalancing in optimal time and space, Communications of the ACM, 1986, 29, pp. 902-908.
[16] 16. J. VAN LEEUWEN and D. WOOD, Dynamization of decomposable searching problem, Information Processing Letters, 1980, 10, pp.51-56. MR564499
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.