home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume35 / m2-splay22 / part01 / README next >
Text File  |  1993-01-20  |  4KB  |  138 lines
  1. SPLAY TREE LIBRARY Version 2.2 930119
  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.  
  15. For a full introduction to splay trees see 
  16.  
  17.                     Sleator D. and Tarjan R. "Self adjusting
  18.             binary trees", JACM Vol 32. No 3, 1985, pp 652-
  19.             686.
  20.  
  21.  
  22.  
  23. Changes since version 2.1
  24. =========================
  25.  
  26. Changed updating of weight information so the basic operations
  27. now remain in O(lgn) instead of O(n).
  28.  
  29.  
  30. Introduction
  31. ============
  32.  
  33. In short, splay trees are a form of balanced binary trees which
  34. moves every accessed node to the root. This means that the tree
  35. will behave very well when there is some form of locality in the
  36. data processed. Furthermore it can be shown that the amortized
  37. access cost is O(lgn) for the basic operations (insert, delete and
  38. find).
  39.  
  40. The splay tree also has the nice property that an item accessed
  41. t operations ago can be located in O(lgt) time.
  42.  
  43. All in all practical tests have shown splay trees to be an excellent
  44. substitution for the more well known r-b-trees or some other variations
  45. on balanced trees.
  46.  
  47. Since modula2 lacks possibilities to create generic modules my
  48. approach is to provide a separate module which gives the operations
  49. and type of the element stored in the tree. This module
  50. (here called splayItem) must support operations to create, destroy
  51. and compare elements. This scheme provides for a fairly generic
  52. implementation, (see the test program and splayItem.[mod,def])
  53. In the test program supplied the create and destroy routines
  54. are empty since the objects doesn't use any dynamic memory. The
  55. prize to pay for the generic structure is a little overhead for
  56. each comparison.
  57.  
  58. If speed is essential (as always) you may hard code the comparison
  59. between elements in the implementation if you are only working
  60. with simple types like integers or something like that. Or you
  61. might want to rewrite the code to handle the more classic
  62. variation with a key and a generic pointer stored in each
  63. node. These changes are trivial and shouldn't take long
  64. time to do.
  65.  
  66.  
  67. Rank
  68. ====
  69.  
  70. This implementation includes management of the rank of elements, i.e
  71. their ordering in an in-order tree traversal. To maintain the rank operation
  72. in O(lgn) time for an element it's necessary to do some extra work
  73. after each basic operation. If you are not interested in maintaining
  74. rank of the elements you may delete the code for maintaining the weight
  75. (number of nodes in subtrees for each node) of each node. 
  76.  
  77. This is basically a matter of deleting most of the code at the end of
  78. each basic operation.
  79.  
  80. Since maintaining the rank requires an explicit stack whos size
  81. must be decided at run time it's possible to get a checked run time
  82. error if the tree grows to large for the stack. This shouldn't pose
  83. a problem since the required stack size is in order O(lgn) where
  84. n is the number of elements in the tree, and the default stack quite
  85. big.
  86.  
  87. Portability
  88. ===========
  89.  
  90. There are basically two things you may want to change.
  91.  
  92. 1. The first are the routines used for I/O to
  93. print a string, cardinal, int and so on. I have used
  94. our local library routines. Change these to your own
  95. favorites.
  96.  
  97. 2. Error handling are done by a call to error.raise() which
  98. again is a local library function. It calls the topmost
  99. function in an error stack with the string supplied as 
  100. argument. You probably want to change this to your own
  101. favorite way of handling errors.
  102.  
  103. Todo
  104. ====
  105.  
  106. * Make two versions one with and one without rank operations.
  107. * Dynamic stack to avoid any run time errors
  108.  
  109.  
  110. Test program
  111. ============
  112.  
  113. Supplied with this distribution is a test program called
  114. splayTest (what else?) it performs some basic tests at first
  115. and then starts an exhaustive test until any errors have been
  116. encountered or stopped by a CTRL-C. 
  117.  
  118. Bugs
  119. ====
  120. To the best of my knowledge this code is bug free. But if you
  121. do discover some irregularities please drop me a note. 
  122.  
  123. Standard disclaimer: This code is put in public domain and 
  124. distributed as is. You may use this code commercially or 
  125. otherwise but I won't take any responsibility whatsoever.
  126.  
  127.  
  128.     Johan Persson (ljp@sm.luth.se)
  129.  
  130.  
  131. ----
  132.  
  133. Johan Persson                E-mail: ljp@sm.luth.se
  134. Dept. of Computer Science
  135. Technical University of Lulea
  136. S-951 87 Lulea
  137.             
  138.