Search trees and bubble memories

Philippe Flajolet; Thomas Ottmann; Derick Wood

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

  • Volume: 19, Issue: 2, page 137-164
  • ISSN: 0988-3754

How to cite

top

Flajolet, Philippe, Ottmann, Thomas, and Wood, Derick. "Search trees and bubble memories." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 19.2 (1985): 137-164. <http://eudml.org/doc/92227>.

@article{Flajolet1985,
author = {Flajolet, Philippe, Ottmann, Thomas, Wood, Derick},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {storage of binary search trees; major-minor loop configurations; cost measures; average case behaviour; minimal cost trees},
language = {eng},
number = {2},
pages = {137-164},
publisher = {EDP-Sciences},
title = {Search trees and bubble memories},
url = {http://eudml.org/doc/92227},
volume = {19},
year = {1985},
}

TY - JOUR
AU - Flajolet, Philippe
AU - Ottmann, Thomas
AU - Wood, Derick
TI - Search trees and bubble memories
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1985
PB - EDP-Sciences
VL - 19
IS - 2
SP - 137
EP - 164
LA - eng
KW - storage of binary search trees; major-minor loop configurations; cost measures; average case behaviour; minimal cost trees
UR - http://eudml.org/doc/92227
ER -

References

top
  1. W. F. BEAUSOLEIL, D. T. BROWN and B. E. PHELPS, Magnetic Bubble Memory Organization, IBM Journal of Research and Development, vol. 16, 1972, pp. 587-591. 
  2. G. BONGIOVANNI and C. K. WONG, Tree Search in Major/Minor Loop Magnetic Bubble Memories IEEE Transactions on Computers, C-30, 1981, pp. 537-545. Zbl0461.68067MR635988
  3. P. I. BONYHARD and T. J. NELSON, Dynamic Data Reallocation in Bubble Memories, The Bell System Technical Journal, Vol. 52, 1973, pp. 307-317. 
  4. A. K. CHANDRA and C. K. WONG, The Movement and Permutation of Columns in Magnetic Bubble Lattice Files, IEEE Transactions on Computers, C-27, 1979, pp. 8-15. Zbl0388.68023
  5. K. M. CHUNG, F. LUCCIO and C. K. WONG, A Tree Storage Scheme for Magnetic Bubble Memories, IEEE Transactions on Computers, C-29, 1980, pp. 553-562. MR581617
  6. K. M. CHUNG, F. LUCCIO and C. K. WONG, A New Permutation Algorithm for Bubble Memories, Information Processing Letters, Vol. 10, 1980. pp. 226-230. Zbl0443.68050MR585388
  7. R. E. FAIRLEY, Random Entry Searching of Binary Trees, University of Colorado, Boulder, Computer Science Report CU-CS-035-73, 1973. 
  8. P. FLAJOLET, Analyse d'Algorithms de Manipulation d'Arbres et de Fichiers, Cahiers du B.U.R.O., Nos. 34-35, Paris, 1981. 
  9. P. FLAJOLET and A. ODLYZKO, The Average Height of Binary Trees and Other Simple Trees, Journal of Computer and System Sciences, Vol. 25, 1982, pp. 171-213. Zbl0499.68027MR680517
  10. J. FRANCON, Combinatoire des Structures de Données, Doctoral dissertation, Université de Strasbourg, 1979. 
  11. D. E. KNUTH, The Art of Computer Programming, Vol. I: Fundamental Algorithms, Addison-Wesley Publishing Co., Reading, Mass., 1968. Zbl0191.17903MR378456
  12. J. MÜHLBACHER, Private communication, 1982. 
  13. A. L. ROSENBERG, Data Encoding and Their Costs, Acta Informatica, Vol. 9, 1978, pp. 273-292. Zbl0434.68048MR502168
  14. A. L. ROSENBERG and L. SNYDER, Bounds on the Costs of Data Encodings, Mathematical Systems Theory, Vol. 12, 1978, pp. 9-39. Zbl0403.68018MR510619
  15. T. A. STANDISH, Data Structure Techniques, Addison-Wesley Publishing Co., Reading, Mass., 1980. 
  16. V. K. VAISHNAVI and D. WOOD, Encoding Search Trees in Lists, International Journal of Computer Mathematics, Vol. 10, 1982, pp. 237-246. Zbl0481.68030MR647042
  17. J. VUILLEMIN, A Unifying Look at Data Structures, Communications of the ACM, 28, 1980, pp. 229-239. Zbl0434.68047MR567151
  18. C. K. WONG, Algorithmic Studies in Mass Storage Systems, Springer-Verlag, Berlin, Heidelberg; New York, 1983. Zbl0537.68102MR708721

NotesEmbed ?

top

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.