Guest User

Untitled

a guest
Dec 10th, 2019
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // add 60 80 30 90 70 100 40 20 50 10
  2. //seach for 30 100 60
  3.  
  4. #ifndef SPLAYING
  5. #define SPLAYING
  6.  
  7. template<class T> class SplayTree;
  8.  
  9. template<class T>
  10. class SplayingNode
  11. {
  12. public:
  13.  
  14. SplayingNode()
  15. {
  16. left = right = parent = 0;
  17. }
  18.  
  19. SplayingNode(const T& el, SplayingNode *l = 0, SplayingNode *r = 0,
  20. SplayingNode *p = 0)
  21. {
  22. info = el;
  23. left = l;
  24. right = r;
  25. parent = p;
  26. }
  27.  
  28. T info;
  29. SplayingNode *left, *right, *parent;
  30. };
  31.  
  32.  
  33.  
  34.  
  35. template<class T>
  36. class SplayTree
  37. {
  38.  
  39. public:
  40. SplayTree()
  41. {
  42. root = 0;
  43. }
  44. void inorder()
  45. {
  46. inorder(root);
  47. }
  48. T* search(const T&);
  49. void insert(const T&);
  50.  
  51. protected:
  52. SplayingNode<T> *root;
  53. void rotateR(SplayingNode<T>*);
  54. void rotateL(SplayingNode<T>*);
  55. void continueRotation(SplayingNode<T>* gr, SplayingNode<T>* par,
  56. SplayingNode<T>* ch, SplayingNode<T>* desc);
  57. void semisplay(SplayingNode<T>*);
  58. void fullsplay(SplayingNode<T>*);
  59. void inorder(SplayingNode<T>*);
  60. //void virtual visit(SplayingNode<T>*) { }
  61. };
  62.  
  63.  
  64. template<class T>
  65. void SplayTree<T>::continueRotation(SplayingNode<T>* gr, SplayingNode<T>* par,
  66. SplayingNode<T>* ch, SplayingNode<T>* desc)
  67. {
  68. if (gr != 0) // if p has a grandparent;
  69. {
  70. if (gr->right == ch->parent)
  71. gr->right = ch;
  72. else gr->left = ch;
  73. }
  74. else root = ch;
  75. if (desc != 0)
  76. desc->parent = par;
  77. par->parent = ch;
  78. ch->parent = gr;
  79. }
  80.  
  81. template<class T>
  82. void SplayTree<T>::rotateR(SplayingNode<T>* p)
  83. {
  84. p->parent->left = p->right;
  85. p->right = p->parent;
  86. continueRotation(p->parent->parent,p->right,p,p->right->left);
  87. }
  88.  
  89. template<class T>
  90. void SplayTree<T>::rotateL(SplayingNode<T>* p)
  91. {
  92. p->parent->right = p->left;
  93. p->left = p->parent;
  94. continueRotation(p->parent->parent,p->left,p,p->left->right);
  95. }
  96.  
  97. template<class T>
  98. void SplayTree<T>::semisplay(SplayingNode<T>* p)
  99. {
  100. while (p != root)
  101. {
  102. if (p->parent->parent == 0) // if p's parent is the root;
  103. if (p->parent->left == p)
  104. rotateR(p);
  105. else rotateL(p);
  106. else if (p->parent->left == p) // if p is a left child;
  107. if (p->parent->parent->left == p->parent)
  108. {
  109. rotateR(p->parent);
  110. p = p->parent;
  111. }
  112. else
  113. {
  114. rotateR(p); // rotate p and its parent;
  115. rotateL(p); // rotate p and its new parent;
  116. }
  117. else // if p is a rigth child;
  118. if (p->parent->parent->right == p->parent)
  119. {
  120. rotateL(p->parent);
  121. p = p->parent;
  122. }
  123. else
  124. {
  125. rotateL(p); // rotate p and its parent;
  126. rotateR(p); // rotate p and its new parent;
  127. }
  128. if (root == 0) // update the root;
  129. root = p;
  130. }
  131. }
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139. template<class T>
  140. void SplayTree<T>::fullsplay(SplayingNode<T>* p)
  141. {
  142. while (p != root)
  143. {
  144. if (p->parent->parent == 0) // if p's parent is the root;
  145. if (p->parent->left == p)
  146. rotateR(p);
  147. else rotateL(p);
  148. else if (p->parent->left == p) // if p is a left child;
  149. if (p->parent->parent->left == p->parent)
  150. {
  151. rotateR(p->parent);
  152. rotateR(p); //added by Chambers and Avelli 2016 spring
  153. // p = p->parent; //removed by Chambers Avelli 2016 spring
  154. }
  155. else
  156. {
  157. rotateR(p); // rotate p and its parent;
  158. rotateL(p); // rotate p and its new parent;
  159. }
  160. else // if p is a rigth child;
  161. if (p->parent->parent->right == p->parent)
  162. {
  163. rotateL(p->parent);
  164. rotateL(p); //added by Chambers and Avelli 2016 spring
  165. // p = p->parent; //removed by Chambers Avelli 2016 spring
  166. }
  167. else
  168. {
  169. rotateL(p); // rotate p and its parent;
  170. rotateR(p); // rotate p and its new parent;
  171. }
  172. if (root == 0) // update the root;
  173. root = p;
  174. }
  175. }
  176.  
  177.  
  178.  
  179.  
  180. template<class T>
  181. T* SplayTree<T>::search(const T& el)
  182. {
  183. SplayingNode<T> *p = root;
  184. while (p != 0)
  185. if (p->info == el) // if el is in the tree,
  186. {
  187. semisplay(p); // move it upward;
  188. return &p->info;
  189. }
  190. else if (el < p->info)
  191. p = p->left;
  192. else p = p->right;
  193. return 0;
  194. }
  195.  
  196. template<class T>
  197. void SplayTree<T>::insert(const T& el)
  198. {
  199. SplayingNode<T> *p = root, *prev = 0, *newNode;
  200. while (p != 0) // find a place for inserting a new node;
  201. {
  202. prev = p;
  203. if (el < p->info)
  204. p = p->left;
  205. else p = p->right;
  206. }
  207. if ((newNode = new SplayingNode<T>(el,0,0,prev)) == 0)
  208. {
  209. cerr << "No room for new nodes\n";
  210. exit(1);
  211. }
  212. if (root == 0) // the tree is empty;
  213. root = newNode;
  214. else if (el < prev->info)
  215. prev->left = newNode;
  216. else
  217. prev->right = newNode;
  218. fullsplay(newNode); //added by Chambers and Avelli 2016 spring
  219. }
  220.  
  221. template<class T>
  222. void SplayTree<T>::inorder(SplayingNode<T> *p)
  223. {
  224. if (p != 0)
  225. {
  226. inorder(p->left);
  227. visit(p);
  228. inorder(p->right);
  229. }
  230. }
  231.  
  232. #endif
RAW Paste Data