Updating approximately complete trees

Tony W. Lai; Derick Wood

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1994)

  • Volume: 28, Issue: 5, page 431-446
  • ISSN: 0988-3754

How to cite


Lai, Tony W., and Wood, Derick. "Updating approximately complete trees." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.5 (1994): 431-446. <http://eudml.org/doc/92489>.

author = {Lai, Tony W., Wood, Derick},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {binary search tree},
language = {eng},
number = {5},
pages = {431-446},
publisher = {EDP-Sciences},
title = {Updating approximately complete trees},
url = {http://eudml.org/doc/92489},
volume = {28},
year = {1994},

AU - Lai, Tony W.
AU - Wood, Derick
TI - Updating approximately complete trees
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 5
SP - 431
EP - 446
LA - eng
KW - binary search tree
UR - http://eudml.org/doc/92489
ER -


  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
  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. Zbl0884.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.68013MR1063313
  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.68012MR331903
  12. 12. M. H. OVERMARS, The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science, 1983, Springer-Verlag. Zbl0545.68009MR710832
  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.68055MR673628
  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

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.