SHARE
TWEET

Untitled

a guest Jun 18th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. class BST
  6. {
  7.     struct node
  8.     {
  9.         int data;
  10.         node* left;
  11.         node* right;
  12.         int height;
  13.     };
  14.  
  15.     node* root;
  16.  
  17.     void makeEmpty(node* t)
  18.     {
  19.         if(t == NULL)
  20.             return;
  21.         makeEmpty(t->left);
  22.         makeEmpty(t->right);
  23.         delete t;
  24.     }
  25.  
  26.     node* insert(int x, node* t)
  27.     {
  28.         if(t == NULL)
  29.         {
  30.             t = new node;
  31.             t->data = x;
  32.             t->height = 0;
  33.             t->left = t->right = NULL;
  34.         }
  35.         else if(x < t->data)
  36.         {
  37.             t->left = insert(x, t->left);
  38.             if(height(t->left) - height(t->right) == 2)
  39.             {
  40.                 if(x < t->left->data)
  41.                     t = singleRightRotate(t);
  42.                 else
  43.                     t = doubleRightRotate(t);
  44.             }
  45.         }
  46.         else if(x > t->data)
  47.         {
  48.             t->right = insert(x, t->right);
  49.             if(height(t->right) - height(t->left) == 2)
  50.             {
  51.                 if(x > t->right->data)
  52.                     t = singleLeftRotate(t);
  53.                 else
  54.                     t = doubleLeftRotate(t);
  55.             }
  56.         }
  57.  
  58.         t->height = max(height(t->left), height(t->right))+1;
  59.         return t;
  60.     }
  61.  
  62.     node* singleRightRotate(node* &t)
  63.     {
  64.         node* u = t->left;
  65.         t->left = u->right;
  66.         u->right = t;
  67.         t->height = max(height(t->left), height(t->right))+1;
  68.         u->height = max(height(u->left), t->height)+1;
  69.         return u;
  70.     }
  71.  
  72.     node* singleLeftRotate(node* &t)
  73.     {
  74.         node* u = t->right;
  75.         t->right = u->left;
  76.         u->left = t;
  77.         t->height = max(height(t->left), height(t->right))+1;
  78.         u->height = max(height(t->right), t->height)+1 ;
  79.         return u;
  80.     }
  81.  
  82.     node* doubleLeftRotate(node* &t)
  83.     {
  84.         t->right = singleRightRotate(t->right);
  85.         return singleLeftRotate(t);
  86.     }
  87.  
  88.     node* doubleRightRotate(node* &t)
  89.     {
  90.         t->left = singleLeftRotate(t->left);
  91.         return singleRightRotate(t);
  92.     }
  93.  
  94.     node* findMin(node* t)
  95.     {
  96.         if(t == NULL)
  97.             return NULL;
  98.         else if(t->left == NULL)
  99.             return t;
  100.         else
  101.             return findMin(t->left);
  102.     }
  103.  
  104.     node* findMax(node* t)
  105.     {
  106.         if(t == NULL)
  107.             return NULL;
  108.         else if(t->right == NULL)
  109.             return t;
  110.         else
  111.             return findMax(t->right);
  112.     }
  113.  
  114.     node* remove(int x, node* t)
  115.     {
  116.         node* temp;
  117.  
  118.  
  119.         if(t == NULL)
  120.             return NULL;
  121.  
  122.  
  123.         else if(x < t->data)
  124.             t->left = remove(x, t->left);
  125.         else if(x > t->data)
  126.             t->right = remove(x, t->right);
  127.  
  128.  
  129.         else if(t->left && t->right)
  130.         {
  131.             temp = findMin(t->right);
  132.             t->data = temp->data;
  133.             t->right = remove(t->data, t->right);
  134.         }
  135.  
  136.         else
  137.         {
  138.             temp = t;
  139.             if(t->left == NULL)
  140.                 t = t->right;
  141.             else if(t->right == NULL)
  142.                 t = t->left;
  143.             delete temp;
  144.         }
  145.         if(t == NULL)
  146.             return t;
  147.  
  148.         t->height = max(height(t->left), height(t->right))+1;
  149.  
  150.  
  151.         if(height(t->left) - height(t->right) == 2)
  152.         {
  153.  
  154.             if(height(t->left->left) - height(t->left->right) == 1)
  155.                 return singleLeftRotate(t);
  156.  
  157.             else
  158.                 return doubleLeftRotate(t);
  159.         }
  160.         else if(height(t->right) - height(t->left) == 2)
  161.         {
  162.             if(height(t->right->right) - height(t->right->left) == 1)
  163.                 return singleRightRotate(t);
  164.             else
  165.                 return doubleRightRotate(t);
  166.         }
  167.         return t;
  168.     }
  169.  
  170.     int height(node* t)
  171.     {
  172.         return (t == NULL ? -1 : t->height);
  173.     }
  174.  
  175.     int getBalance(node* t)
  176.     {
  177.         if(t == NULL)
  178.             return 0;
  179.         else
  180.             return height(t->left) - height(t->right);
  181.     }
  182.  
  183.     void inorder(node* t)
  184.     {
  185.         if(t == NULL)
  186.             return;
  187.         cout << t->data;
  188.         inorder(t->left);
  189.  
  190.         inorder(t->right);
  191.     }
  192.  
  193. public:
  194.     BST()
  195.     {
  196.         root = NULL;
  197.     }
  198.  
  199.     void insert(int x)
  200.     {
  201.         root = insert(x, root);
  202.     }
  203.  
  204.     void remove(int x)
  205.     {
  206.         root = remove(x, root);
  207.     }
  208.  
  209.     void display()
  210.     {
  211.         inorder(root);
  212.         cout << endl;
  213.     }
  214. };
  215.  
  216. int main()
  217. {
  218.     BST t;
  219.     int liczba;
  220.  
  221.     t.insert(12);
  222.     t.insert(6);
  223.     t.insert(3);
  224.     t.insert(1);
  225.     t.insert(4);
  226.     t.insert(8);
  227.     t.insert(7);
  228.     t.insert(10);
  229.     t.insert(62);
  230.     t.insert(26);
  231.     t.insert(14);
  232.     t.insert(29);
  233.     t.insert(104);
  234.     t.insert(69);
  235.     cin >> liczba;
  236.     t.remove(liczba);
  237.     t.display();
  238. }
  239. /*
  240. #include <iostream>
  241. #include <cstdio>
  242. #include <string>
  243. #include <malloc.h>
  244. #include <cstdlib>
  245.  
  246. using namespace std;
  247.  
  248. struct drzewoAVL{
  249.     int liczba;
  250.     int wysokosc;
  251.     struct drzewoAVL* lewy;
  252.     struct drzewoAVL* prawy;
  253. };
  254.  
  255. typedef drzewoAVL* AVL;
  256.  
  257. void insert(AVL &wezel, int liczba)
  258. {
  259.     if(wezel == NULL)
  260.     {
  261.         wezel = new drzewoAVL();
  262.         wezel->prawy = wezel->lewy = NULL;
  263.         wezel->liczba = liczba;
  264.         wezel->wysokosc = 0;
  265.     }
  266.     else if(liczba < wezel->liczba)
  267.     {
  268.         insert(wezel->lewy, liczba);
  269.     }
  270.     else if(liczba > wezel->liczba)
  271.     {
  272.         insert(wezel->prawy,liczba);
  273.     }
  274. }
  275. void preOrder(AVL wezel)
  276. {
  277.     if(wezel)
  278.     {
  279.         cout << wezel->liczba << " ";
  280.         preOrder(wezel->lewy);
  281.         preOrder(wezel->prawy);
  282.     }
  283. }
  284.  
  285. AVL rotacjaPrawo(AVL wezel)
  286. {
  287.     AVL dzieckoL = wezel->lewy;
  288.     wezel->lewy = dzieckoL->prawy;
  289.     dzieckoL->prawy = wezel;
  290.  
  291.     if(wezel->lewy->wysokosc > wezel->prawy->wysokosc)
  292.     {
  293.         wezel->wysokosc = wezel->lewy->wysokosc + 1;
  294.     }
  295.     else
  296.     {
  297.         wezel->wysokosc = wezel->prawy->wysokosc + 1;
  298.     }
  299.     if(dzieckoL->lewy->wysokosc > dzieckoL->prawy->wysokosc)
  300.     {
  301.         dzieckoL->wysokosc = dzieckoL->lewy->wysokosc + 1;
  302.     }
  303.     else
  304.     {
  305.         dzieckoL->wysokosc = dzieckoL->prawy->wysokosc + 1;
  306.     }
  307.     return dzieckoL;
  308. }
  309. AVL rotacjaLewo(AVL wezel)
  310. {
  311.     AVL dzieckoR = wezel->prawy;
  312.     wezel->prawy = dzieckoR->lewy;
  313.     dzieckoR->lewy = wezel;
  314.  
  315.     if(wezel->lewy->wysokosc > wezel->prawy->wysokosc)
  316.     {
  317.         wezel->wysokosc = wezel->lewy->wysokosc + 1;
  318.     }
  319.     else
  320.     {
  321.         wezel->wysokosc = wezel->prawy->wysokosc + 1;
  322.     }
  323.     if(dzieckoR->lewy->wysokosc > dzieckoR->prawy->wysokosc)
  324.     {
  325.         dzieckoR->wysokosc = dzieckoR->lewy->wysokosc + 1;
  326.     }
  327.     else
  328.     {
  329.         dzieckoR->wysokosc = dzieckoR->prawy->wysokosc + 1;
  330.     }
  331.     return dzieckoR;
  332. }
  333. drzewoAVL usunWezel(AVL wezel, int liczba)
  334. {
  335.     if(wezel)
  336.     {
  337.         if(liczba == wezel->liczba)
  338.         {
  339.             AVL _temp = wezel;
  340.             if((wezel->prawy && wezel->lewy)==NULL)
  341.             {
  342.                 free(wezel);
  343.             }
  344.             if(wezel->prawy && !wezel->lewy)
  345.             {
  346.  
  347.             }
  348.  
  349.  
  350.  
  351.         }
  352.         if(liczba < wezel->liczba)
  353.         {
  354.             usunWezel(wezel->lewy, liczba);
  355.         }
  356.         if(liczba > wezel->liczba)
  357.         {
  358.             usunWezel(wezel->prawy, liczba);
  359.         }
  360.  
  361.     }
  362. }
  363. int main() {
  364.     AVL korzen = NULL;
  365.     int usun;
  366.  
  367.     insert(korzen, 12);
  368.     insert(korzen, 6);
  369.     insert(korzen, 3);
  370.     insert(korzen, 1);
  371.     insert(korzen, 4);
  372.     insert(korzen, 8);
  373.     insert(korzen, 7);
  374.     insert(korzen, 10);
  375.     insert(korzen, 62);
  376.     insert(korzen, 26);
  377.     insert(korzen, 14);
  378.     insert(korzen, 29);
  379.     insert(korzen, 12);
  380.     insert(korzen, 104);
  381.     insert(korzen, 69);
  382.  
  383.     cin >> usun;
  384.     usunWezel(korzen, usun);
  385.     preOrder(korzen);
  386.  
  387.     return 0;
  388. }
  389. */
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