home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / sources / 2600 / README next >
Encoding:
Text File  |  1992-11-21  |  3.4 KB  |  90 lines
  1. SPLAY TREE LIBRARY
  2. ==================
  3.  
  4. This library contains the following files:
  5.  
  6.     splay.def    Definition module for the splay tree library
  7.     splay.mod     Implementation of splay tree
  8.     splayItem.def     Definition module for data stored in the tree
  9.     splayItem.mod    Implementation module for data stored in
  10.             the tree
  11.     splayTest.mod    A short test program
  12.  
  13.  
  14. For a full introduction to splay trees see
  15.  
  16.                     Sleator D. and Tarjan R. "Self adjusting
  17.             binary trees", JACM Vol 32. No 3, 1985, pp 652-
  18.             686.
  19.  
  20.  
  21. In short, splay trees are a form of balanced binary trees which
  22. moves every accessed node to the root. This means that the tree
  23. will behave very well when there is some form of locality in the
  24. data processed. Furthermore it can be shown that the amortized
  25. access cost is O(lgn) for the basic operations (insert, delete and
  26. find).
  27.  
  28. The splay tree also has the nice property that an item accessed
  29. t operations ago can be located in O(lgt) time.
  30.  
  31. All in all practical tests have shown splay trees to be an excellent
  32. substitution for the more well known r-b-trees or some other variations
  33. on balanced trees.
  34.  
  35. Since modula2 lacks possibilities to create generic modules my
  36. approach is to provide a separate module which gives the operations
  37. and type of the element stored in the tree. This module
  38. (here called splayItem) must support operations to create, destroy
  39. and compare elements. This scheme provides for a fairly generic
  40. implementation, (see the test program and splayItem.[mod,def])
  41. In the test program supplied the create and destroy routines
  42. are empty since the objects doesn't use any dynamic memory. The
  43. prize to pay for the generic structure is a little overhead for
  44. each comparison.
  45.  
  46. If speed is essential (as always) you may hard code the comparison
  47. beetween elements in the implementation if you are only working
  48. with simple types like integers or something like that. Or you
  49. might want to rewrite the code to handle the more classic
  50. variation with a key and a generic pointer stored in each
  51. node. These changes are trivial and shouldn't take long
  52. time to do.
  53.  
  54. To the best of my knowledge this code is bug free. But if you
  55. do discover som irregularities please drop me a note.
  56.  
  57.     Johan Persson (ljp@sm.luth.se)
  58.  
  59.  
  60. ----
  61.  
  62. Note0: You may encounter some difficulties when trying to
  63. compile the 'splayTest.mod' due to the lack of standard between
  64. different compilers in their I/O libraries. Though it should be
  65. fairly simpel just to change the name to your own routines which
  66. prints a string, a cardinal and so on.
  67.  
  68. Note1: This code implements the more efficient top-down splaying as
  69. described in section 4 of original paper (see above).
  70.  
  71. Note2: This implementation has been augumented with operations
  72. to retrive the rank of the element stored in the tree, (i.e their
  73. position when making an inorder tree walk). This operations take time
  74. O(lgn), but to achive this we have to pay a prize when making
  75. the basic operations (insert,delete,find), this means that these
  76. operations now take O(n) time instead. If you find this unexceptable
  77. you may modify the source by simply removing the calls to 'fixRank' at
  78. the end of (insert,delete,find). NOTE: this will make the rank operations
  79. unusable! The basic problem is that we must maintain the weight of
  80. each element, and each basic operations restructure the tree so we
  81. must recalculate the weights for each node bottom up.
  82.  
  83.  
  84. ---
  85. Johan Persson                E-mail: ljp@sm.luth.se
  86. Dept. of Computer Science
  87. Technical University of Lulea
  88. S-951 87 Lulea
  89.             
  90.