SHARE
TWEET

Untitled

a guest Dec 10th, 2019 89 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top