API tools faq
paste
Advertisement
Singasking

Untitled

Singasking
Nov 20th, 2022
688
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.48 KB | None | 0 0
raw download clone embed print report
  1. //Splay tree implementation in C++
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class Node {
  6.     public:
  7.         int data;
  8.         Node* parent;
  9.         Node* left;
  10.         Node* right;
  11.  
  12.     Node(int d) {
  13.         data = d;
  14.         parent=NULL;
  15.         left=NULL;
  16.         right=NULL;
  17.  
  18.     }
  19.  
  20.  
  21.  
  22. };
  23.  
  24. class SplayTree {
  25.     public:
  26.         Node* root=NULL;
  27.  
  28.         void LR(Node* x) {
  29.             //Left rotate the node
  30.          
  31.             Node* y = x->right;
  32.             y->parent = x->parent;
  33.          
  34.            if(x->parent!=NULL && x->parent->right==x) { x->parent->right=y;}
  35.             if(x->parent!=NULL && x->parent->left==x) { x->parent->left = y; }
  36.             x->right = y->left;
  37.            if(y->left!=NULL) { y->left->parent=x; }
  38.          
  39.             y->left=x;
  40.        
  41.            x->parent=y;
  42.            
  43.            if(y->parent==NULL) { root=y; }
  44.                  //cout<<"i cri";
  45.         }
  46.        
  47.         void RR(Node* x) {
  48.             Node* y = x->left;
  49.             y->parent = x->parent;
  50.             if(x->parent!=NULL && x->parent->right==x) { x->parent->right=y;}
  51.             if(x->parent!=NULL && x->parent->left==x) { x->parent->left=y;}
  52.             x->left = y->right;
  53.             if(y->right!=NULL) { y->right->parent=x; }
  54.             y->right = x;
  55.             x->parent = y;
  56.            
  57.              if(y->parent==NULL) { root=y; }
  58.         }
  59.         void Splay(Node* node) {
  60.            cout<<"in";
  61.            if(node->parent==NULL) { return; }
  62.            cout<<"Ok";
  63.             while(node->parent!=NULL) {
  64.  
  65.                
  66.                 if(node->parent==root) {
  67.                    cout<<"into this alive "<<endl;
  68.                     if(node->parent->right==node) {
  69.                         //Perform left rotation on root
  70.                       //  cout<<"hello i cri";
  71.                         LR(root);
  72.                        // cout<<"god please help me";
  73.  
  74.                     } else if(node->parent->left==node) {
  75.                         //Perform right rotation on root
  76.                         RR(root);
  77.                     }
  78.                 } else {
  79.                     //At least at height = 2
  80.                    
  81.                     if(node->parent->right == node && node->parent->parent->right ==node->parent) {
  82.                        
  83.                         //Perform left rotation on node's parent parent first then on node-sp parent
  84.                         LR(node->parent->parent);
  85.                       //cout<<"new root is: "<<root->data<<"and "<<node->parent->data<<endl;
  86.                         LR(node->parent);
  87.                     }
  88.                     else if(node->parent->left!=NULL && node->parent->left==node && node->parent->parent->left==node->parent) {
  89.                         //perform right rotation on node's grandparent then note's parent
  90.                         RR(node->parent->parent);
  91.                         RR(node->parent);
  92.  
  93.                     }
  94.  
  95.                     else if(node->parent->left ==node && node->parent->parent->right == node->parent) {
  96.                         //perform right rotation on node's parent followed by left rotation on node's grandparent
  97.                       Node *grandparent = node->parent->parent;
  98.                         RR(node->parent);
  99.                        // cout<<node->parent->parent->data;
  100.                         LR(grandparent);
  101.                          
  102.                     }
  103.                
  104.                     else if(node->parent->right==node && node->parent->parent->left==node->parent) {
  105.                         //left rotation on node's parent followed by right rotation on node's grandparent
  106.                          Node *grandparent = node->parent->parent;
  107.                         LR(node->parent);
  108.        
  109.                         RR(grandparent);
  110.                     }
  111.                 }
  112.             }
  113.             //Inorder(root);
  114.            
  115.         }
  116.        
  117.         void Inorder(Node* root) {
  118.             if(root==NULL) { return; }
  119.             Inorder(root->left);
  120.             cout<<root->data<<" ";
  121.             Inorder(root->right);
  122.         }
  123.         void Insert(int value) {
  124.             Node* temp = root;
  125.             if(temp!=NULL) { cout<<"root is : "<<temp->data<<endl; }
  126.             Node* temp_parent = NULL;
  127.              
  128.             while(temp!=NULL) {
  129.                 temp_parent = temp;
  130.               //  cout<<"temp is :"<<temp->data<<endl;
  131.                 int data = temp->data;
  132.                 if((data)<value) {temp = temp->right; }
  133.                 if((data)>value) { temp = temp->left; }
  134.                 //cout<<"ok"<<endl;
  135.                 //cout<<"new temp is "<<temp<<endl;
  136.                 if(temp==NULL) {break; }
  137.                
  138.             }
  139.          
  140.          
  141.             if(temp_parent==NULL) { root = new Node(value); return; }
  142.              
  143.             if(temp_parent!=NULL) {
  144.                 Node *x = new Node(value);
  145.                 int data = temp_parent->data;
  146.                 if(value<data) {x->parent=temp_parent; temp_parent->left=x;  }
  147.                 if(value>data) {x->parent=temp_parent; temp_parent->right=x;  }
  148.                
  149.                 Splay(x);
  150.                  
  151.             }
  152.          
  153.         }
  154.     Node* FindSuccessor(Node* node) {
  155.         //cout<<"called"<<node->data<<endl;
  156.         while(node->left!=NULL) { node=node->left;}
  157.         return node;
  158.     }
  159.     void Delete(int value) {
  160.         Node *temp = root;
  161.         Node* temp_node = NULL;
  162.         if(value==20) {
  163.             //15 17 10 7 13
  164.             cout<<root->right->parent->data;
  165.             cout<<root->data<<" "<<root->right->data<<" "<<root->left->data<<" "<<root->left->left->data<<" "<<root->left->right->data<<endl;
  166.         }
  167.         //To implement delete function
  168.         while(1) {
  169.             temp_node = temp;
  170.            
  171.           cout<<temp_node->data<<endl;
  172.         //  cout<<"temp ebfore"<<temp->data<<endl;
  173.             if(temp->data<value) { temp = temp->right;}
  174.             else if(temp->data>value) { temp = temp->left; }
  175.            // cout<<temp<<endl;
  176.              //cout<<"temp after "<<temp->data<<endl;
  177.             if(temp==NULL) { break; }
  178.             if(temp->data==value) { break; }
  179.          
  180.          
  181.         }
  182.         cout<<"finally"<<temp_node->data<<endl;
  183.         if(temp==NULL) { cout<<"yes";Splay(temp_node); return; }
  184.      
  185.         //CASE 1: Node has no child
  186.         if(temp->left==NULL and temp->right==NULL) {
  187.             //if its root node;
  188.             if(temp->parent==NULL) {
  189.                 delete temp;
  190.                 root = NULL;
  191.  
  192.             } else if(temp->parent!=NULL) {
  193.                 //Leaf node
  194.                 cout<<"17 is a leaf node"<<endl;
  195.                 Node *tempnode = temp;
  196.                 Node *temp_parent = temp->parent;
  197.                  cout<<tempnode->parent->data<<endl;
  198.                 if(temp->parent->right==temp) { temp->parent->right=NULL;}
  199.                 if(temp->parent->left==temp) { temp->parent->left=NULL; }
  200.                 delete temp;
  201.                 //Splay the parent
  202.                 cout<<temp_parent->data<<endl;
  203.                 Splay(temp_parent);
  204.             }
  205.         //CASE 2: LEFT CHILD BUT NO RIGHT CHILD
  206.         } else if(temp->left!=NULL && temp->right==NULL) {
  207.                 Node *tempnode = temp;
  208.                 if(temp->parent->left==temp) { temp->parent->left = temp->left; temp->left->parent=temp->parent;}
  209.                 else if(temp->parent->right==temp) { temp->parent->right = temp->left;temp->left->parent=temp->parent; }
  210.            
  211.                 Splay(tempnode->parent);
  212.         //CASE 3: RIGHT CHILD BUT NO LEFT CHILD
  213.         } else if(temp->right!=NULL && temp->left==NULL) {
  214.                 Node *tempnode = temp;
  215.                 if(temp->parent->right==temp) { temp->parent->right = temp->right;temp->right->parent = temp->parent;}
  216.                 else if(temp->parent->left==temp) { temp->parent->left = temp->right;temp->right->parent = temp->parent; }
  217.                 Splay(tempnode->parent);
  218.         //CASE 4: BOTH CHILD
  219.         } else if(temp->right!=NULL && temp->left!=NULL) {
  220.             cout<<"both child"<<endl;
  221.             Node* parent = temp->parent;
  222.            
  223.             Node* tempnode = FindSuccessor(temp->right);//Find successor
  224.             cout<<tempnode->data<<endl;
  225.             cout<<tempnode->parent<<endl;
  226.             temp->data = tempnode->data;
  227.            
  228.             if(tempnode->parent->right==tempnode) { cout<<"right";tempnode->parent->right = NULL;}
  229.             if(tempnode->parent->left==tempnode) { tempnode->parent->left = NULL; }
  230.             Node* tempnode_parent = tempnode->parent;
  231.             delete tempnode;
  232.            
  233.             if(parent!=NULL) { Splay(parent);}
  234.             cout<<"ok"<<endl;
  235.         }
  236.        
  237.         }
  238.        
  239.    
  240.        
  241. };
  242.  
  243.  
  244.  
  245. int main() {
  246.     SplayTree tree;
  247.     int n;
  248.     /**cout<<"Enter number of nodes: ";
  249.     cin>>n;
  250.     while(n--) {
  251.         cout<<"\n Enter node: ";
  252.         int x;
  253.         cin>>x;
  254.         tree.Insert(x);
  255.         cout<<"\n Inorder: ";
  256.         tree.Inorder(tree.root);
  257.         cout<<"new root is : "<<tree.root->data<<endl;
  258.         cout<<endl;
  259.        
  260.     }**/
  261.     tree.root = new Node(14);
  262.     tree.root->left = new Node(13);
  263.     tree.root->left->parent = tree.root;
  264.     tree.root->left->left = new Node(7);
  265.     tree.root->left->left->parent = tree.root->left;
  266.     tree.root->left->left->right = new Node(10);
  267.     tree.root->left->left->right->right = new Node(12);
  268.     tree.root->left->left->right->right->parent = tree.root->left->left->right;
  269.     tree.root->left->left->right->parent = tree.root->left->left;
  270.     tree.root->right = new Node(16);
  271.     tree.root->right->parent = tree.root;
  272.     tree.root->right->right = new Node(17);
  273.     tree.root->right->right->parent = tree.root->right;
  274.     tree.root->right->left = new Node(15);
  275.     tree.root->right->left->parent = tree.root->right;
  276.  
  277.  
  278.    cout<<"Enter number of nodes to delete: ";
  279.     cin>>n;
  280.     while(n--) {
  281.         cout<<"\n Enter node: ";
  282.         int x;
  283.         cin>>x;
  284.         tree.Delete(x);
  285.         cout<<"\n Inorder: ";
  286.         tree.Inorder(tree.root);
  287.         cout<<"new root is : "<<tree.root->data<<endl;
  288.         cout<<endl;
  289.        
  290.     }
  291. //    cout<<tree.root->data<<" "<<tree.root->right->data<<" "<<tree.root->right->left->data<<" "<<tree.root->right->left->right->data<<" ";
  292.    
  293.     //tree.Insert(10);
  294.     //tree.Insert(17);
  295.     //tree.Insert(7);
  296.     //tree.Insert(13);
  297.     //tree.Insert(16);
  298. }
  299.  
  300.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!