1
0

bintree_splay.c 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130
  1. /*********************** -*- Mode: C -*- ***********************
  2. * File : bintree_splay.c
  3. *---------------------------------------------------------------
  4. * Description
  5. * ===========
  6. * An implementation of top-down splaying
  7. * D. Sleator <sleator@cs.cmu.edu>
  8. * March 1992
  9. *
  10. * "Splay trees", or "self-adjusting search trees" are a simple and
  11. * efficient data structure for storing an ordered set. The data
  12. * structure consists of a binary tree, without parent pointers, and
  13. * no additional fields. It allows searching, insertion, deletion,
  14. * deletemin, deletemax, splitting, joining, and many other
  15. * operations, all with amortized logarithmic performance. Since the
  16. * trees adapt to the sequence of requests, their performance on real
  17. * access patterns is typically even better. Splay trees are
  18. * described in a number of texts and papers [1,2,3,4,5].
  19. *
  20. * The code here is adapted from simple top-down splay, at the bottom
  21. * of page 669 of [3]. It can be obtained via anonymous ftp from
  22. * spade.pc.cs.cmu.edu in directory /usr/sleator/public.
  23. *
  24. * The chief modification here is that the splay operation works even
  25. * if the item being splayed is not in the tree, and even if the tree
  26. * root of the tree is NULL. So the line:
  27. *
  28. * t = splay(i, t);
  29. *
  30. * causes it to search for item with key i in the tree rooted at t.
  31. * If it's there, it is splayed to the root. If it isn't there,
  32. * then the node put at the root is the last one before NULL that
  33. * would have been reached in a normal binary search for i. (It's a
  34. * neighbor of i in the tree.) This allows many other operations to
  35. * be easily implemented, as shown below.
  36. *
  37. * [1] "Fundamentals of data structures in C", Horowitz, Sahni,
  38. * and Anderson-Freed, Computer Science Press, pp 542-547.
  39. * [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
  40. * Harper Collins, 1991, pp 243-251.
  41. * [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
  42. * JACM Volume 32, No 3, July 1985, pp 652-686.
  43. * [4] "Data Structure and Algorithm Analysis", Mark Weiss,
  44. * Benjamin Cummins, 1992, pp 119-130.
  45. * [5] "Data Structures, Algorithms, and Performance", Derick Wood,
  46. * Addison-Wesley, 1993, pp 367-375.
  47. *
  48. * The following code was written by Daniel Sleator, and is released
  49. * in the public domain.
  50. *
  51. *---------------------------------------------------------------
  52. * Author : Graeme McKerrell
  53. * Created On : Wed Jan 28 16:29:28 2004
  54. * Status : TESTED
  55. *---------------------------------------------------------------
  56. * HISTORY
  57. * 7-Dec-2004 Graeme McKerrell
  58. * Renamed to the "lub_" namespace
  59. * 5-May-2004 Graeme McKerrell
  60. * updates following review
  61. * 2-Mar-2004 Graeme McKerrell
  62. * Fixed to account for comparision logic being (node - key)
  63. * original algorithm expected (key - node)
  64. * 9-Feb-2004 Graeme McKerrell
  65. * updated to use new node,key comparison ordering
  66. * 28-Jan-2004 Graeme McKerrell
  67. * Adapted from original public domain code
  68. *---------------------------------------------------------------
  69. * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
  70. **************************************************************** */
  71. #include "private.h"
  72. /*--------------------------------------------------------- */
  73. lub_bintree_node_t *lub_bintree_splay(const lub_bintree_t * this,
  74. lub_bintree_node_t * t, const void *key)
  75. {
  76. /* Simple top down splay, not requiring "key" to be in the tree t. */
  77. /* What it does is described above. */
  78. lub_bintree_node_t N, *leftTreeMax, *rightTreeMin, *y;
  79. int comp;
  80. if (t == NULL)
  81. return t;
  82. N.left = N.right = NULL;
  83. leftTreeMax = rightTreeMin = &N;
  84. for (;;) {
  85. comp = lub_bintree_compare(this, t, key);
  86. if (comp > 0) {
  87. if (t->left == NULL)
  88. break;
  89. if (lub_bintree_compare(this, t->left, key) > 0) {
  90. y = t->left; /* rotate right */
  91. t->left = y->right;
  92. y->right = t;
  93. t = y;
  94. if (t->left == NULL)
  95. break;
  96. }
  97. rightTreeMin->left = t; /* link right */
  98. rightTreeMin = t;
  99. t = t->left;
  100. } else if (comp < 0) {
  101. if (t->right == NULL)
  102. break;
  103. if (lub_bintree_compare(this, t->right, key) < 0) {
  104. y = t->right; /* rotate left */
  105. t->right = y->left;
  106. y->left = t;
  107. t = y;
  108. if (t->right == NULL)
  109. break;
  110. }
  111. leftTreeMax->right = t; /* link left */
  112. leftTreeMax = t;
  113. t = t->right;
  114. } else {
  115. break;
  116. }
  117. }
  118. leftTreeMax->right = t->left; /* assemble */
  119. rightTreeMin->left = t->right;
  120. t->left = N.right;
  121. t->right = N.left;
  122. /* return the new root */
  123. return t;
  124. }
  125. /*--------------------------------------------------------- */