API tools faq
paste
Advertisement
warmi12

kurwa jebana w dupe ruchana - drzewko

warmi12
Nov 21st, 2019
133
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.54 KB | None | 0 0
raw download clone embed print report
  1. #include "Nagłówek.h"
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <time.h>
  5. #include <ctime>
  6. #include <string>
  7. #include <random>
  8. using namespace std;
  9.  
  10. template<typename T>
  11. class Wezel {
  12. public:
  13.     T dane;
  14.     Wezel *up, *left, *right;
  15.     long long indeks;
  16.     bool color; //0 czarny 1 czerwony
  17.  
  18.     Wezel()
  19.     {
  20.         up, left, right = nullptr;
  21.         indeks = 0;
  22.         color = 0;
  23.     }
  24.  
  25.     ~Wezel()
  26.     {
  27.  
  28.         delete right, left;
  29.     }
  30. };
  31.  
  32. template<typename T>
  33. class Drzewo {
  34. private:
  35.     Wezel <T> * root;
  36.     unsigned int counter;
  37. public:
  38.     Drzewo() {
  39.         root = nullptr;
  40.     /*  root->up = nullptr;
  41.         root->left = nullptr;
  42.         root->right = nullptr;*/
  43.         counter = 0;
  44.     }
  45.     ~Drzewo() {
  46.         del(root);
  47.     }
  48.  
  49.     void del(Wezel <T> *wsk)
  50.     {
  51.         if (wsk)
  52.         {
  53.             del(wsk->left);
  54.             del(wsk->right);
  55.             delete wsk;
  56.         }
  57.     }
  58.     void usun()
  59.     {
  60.         del(root);
  61.     }
  62.  
  63.     void dodaj_nowy_element(const T &obiekt)
  64.     {
  65.         Wezel<T> *nowy_obiekt = new Wezel<T>;
  66.         Wezel<T> *p;
  67.         nowy_obiekt->dane = obiekt;
  68.         nowy_obiekt->left = nullptr;
  69.         nowy_obiekt->right = nullptr;
  70.         nowy_obiekt->indeks = counter;
  71.         counter++;
  72.         p = root;
  73.    
  74.         if (p)
  75.         {
  76.             for (;;)
  77.             {
  78.                 if (p->dane < obiekt)
  79.                 {
  80.                     if (p->right)
  81.                     {
  82.                         p = p->right;
  83.                     }
  84.                     else
  85.                     {
  86.                         p->right = nowy_obiekt;
  87.                         nowy_obiekt->up = p;
  88.                         break;
  89.                     }
  90.                 }
  91.                 else
  92.                 {
  93.                     if (p->left)
  94.                     {
  95.                         p = p->left;
  96.                     }
  97.                     else
  98.                     {
  99.                         p->left = nowy_obiekt;
  100.                         nowy_obiekt->up = p;
  101.                         break;
  102.                     }
  103.                 }
  104.        
  105.             }
  106.         }
  107.         else
  108.         {
  109.             root = nowy_obiekt;
  110.         }//znalezienie miejsca
  111.        
  112.         nowy_obiekt->color = 1;
  113.        
  114.         while( (nowy_obiekt !=root)&&(nowy_obiekt->up->color==1))
  115.         {
  116.             if (nowy_obiekt->up == nowy_obiekt->up->up->left)
  117.             {
  118.                 if (nowy_obiekt->up->up->right)
  119.                 {
  120.                     p = nowy_obiekt->up->up->right; //stryj
  121.                     if (p->color == 1) //przypadek1
  122.                     {
  123.                         nowy_obiekt->up->color = 0;
  124.                         p->color = 0;
  125.                         nowy_obiekt->up->up->color = 1;
  126.                         nowy_obiekt = nowy_obiekt->up->up;
  127.                         continue;
  128.                     }
  129.                 }
  130.            
  131.                 if (nowy_obiekt == nowy_obiekt->up->right)
  132.                 {
  133.                     nowy_obiekt = nowy_obiekt->up;
  134.                     rotacja_l(nowy_obiekt);
  135.                        
  136.                 }
  137.                 nowy_obiekt->up->color = 0;
  138.                 nowy_obiekt->up->up->color = 1;
  139.                 rotacja_r(nowy_obiekt->up->up);
  140.                 break;
  141.                
  142.             }
  143.             else
  144.             {//tutaj sie wykrzacza bo stryjka nie ma
  145.                 if (nowy_obiekt->up->up->left)
  146.                 {
  147.                     p = nowy_obiekt->up->up->left;
  148.                     if (p->color == 1)
  149.                     {
  150.                         nowy_obiekt->up->color = 0;
  151.                         p->color = 0;
  152.                         nowy_obiekt->up->up->color = 1;
  153.                         nowy_obiekt = nowy_obiekt->up->up;
  154.                         continue;
  155.                     }
  156.  
  157.                 }
  158.                    
  159.                 if (nowy_obiekt == nowy_obiekt->up->left)
  160.                 {
  161.                     nowy_obiekt = nowy_obiekt->up;
  162.                     rotacja_r(nowy_obiekt);
  163.                    
  164.                 }
  165.                 nowy_obiekt->up->color = 0;
  166.                 nowy_obiekt->up->up->color = 1;
  167.                 rotacja_l(nowy_obiekt->up->up);
  168.                 break;
  169.                
  170.             }
  171.         }
  172.  
  173.         root->color = 0;
  174.     }
  175.    
  176.    
  177.  
  178.     void in(Wezel <T> *wsk)
  179.     {
  180.         if (wsk)
  181.         {
  182.             in(wsk->left);
  183.             cout << "indeks: " << wsk->indeks << " dane: " << wsk->dane << endl;
  184.             in(wsk->right);
  185.            
  186.         }
  187.  
  188.     }
  189.  
  190.     void pre(Wezel <T> *wsk)
  191.     {
  192.         if (wsk)
  193.         {
  194.             cout << "indeks: " << wsk->indeks << " dane: " << wsk->dane << endl;
  195.             pre(wsk->left);
  196.             pre(wsk->right);
  197.         }
  198.     }
  199.  
  200.     Wezel <T> *search(const T &obiekt)
  201.     {
  202.         Wezel <T> *p;
  203.         p = root;
  204.  
  205.         while (p)
  206.         {
  207.             if (obiekt < p->dane)
  208.             {
  209.                 p=p->left;
  210.             }
  211.             else if (p->dane<obiekt)
  212.             {
  213.                 p = p->right;
  214.             }
  215.             else
  216.             {
  217.                 cout << "znalezionio! indeks: " << p->indeks << endl;
  218.                 return p;
  219.             }
  220.         }
  221.         cout << "nie ma takiego obiektu" << endl;
  222.         return p;
  223.        
  224.  
  225.     }
  226.  
  227.     int wys(Wezel <T> *wsk)
  228.     {
  229.         if (wsk == nullptr) return 0;
  230.  
  231.         int wl = wys(wsk->left);
  232.         int wr = wys(wsk->right);
  233.  
  234.         if (wl < wr) return wr+1;
  235.         else return wl+1;
  236.  
  237.     }
  238.  
  239.     void wysokosc()
  240.     {
  241.         int high=wys(root);
  242.         cout << "wysokosc wynosi: " << high<<endl;
  243.     }
  244.  
  245.     //void rotacja_l(Wezel <T> *dziecko, Wezel <T> *rodzic)
  246.     //{
  247.     //  if (dziecko)
  248.     //  {
  249.     //      rodzic->right = dziecko->left;
  250.     //      if (rodzic->right) rodzic->right->up = rodzic;
  251.     //      dziecko->left = rodzic;
  252.     //      dziecko->up = rodzic->up;
  253.     //      rodzic->up = dziecko;
  254.     //      if (dziecko->up)
  255.     //      {
  256.     //          if (dziecko->up->left == dziecko) dziecko->up->left = dziecko;
  257.     //          else dziecko->up->right = dziecko;
  258.     //      }
  259.     //      else root = dziecko;
  260.     //  }
  261.     // 
  262.  
  263.     //}
  264.  
  265.     void rotacja_l(Wezel <T> *rodzic)
  266.     {
  267.         Wezel <T> *dziecko,*p;
  268.         dziecko = rodzic->right;
  269.         if (dziecko)
  270.         {
  271.             p = rodzic->up;
  272.             rodzic->right = dziecko->left;
  273.             if (rodzic->right) rodzic->right->up = rodzic;
  274.             dziecko->left = rodzic;
  275.             dziecko->up =p;
  276.             rodzic->up = dziecko;
  277.             if (dziecko->up)
  278.             {
  279.                 if (p->left == dziecko) p->left = dziecko;
  280.                 else p->right = dziecko;
  281.             }
  282.             else root = dziecko;
  283.         }
  284.  
  285.  
  286.     }
  287.     //void rotacja_r(Wezel <T> *dziecko, Wezel <T> *rodzic)
  288.     //{
  289.     //  if (dziecko)
  290.     //  {
  291.     //      rodzic->left = dziecko->right;
  292.     //      if (rodzic->left) rodzic->left->up = rodzic;
  293.     //      dziecko->right = rodzic;
  294.     //      dziecko->up = rodzic->up;
  295.     //      rodzic->up = dziecko;
  296.     //      if (dziecko->up)
  297.     //      {
  298.     //          if (dziecko->up->left == dziecko) dziecko->up->left = dziecko;
  299.     //          else dziecko->up->right = dziecko;
  300.     //      }
  301.     //      else root = dziecko;
  302.     //  }
  303.     // 
  304.     //}
  305.  
  306.     void rotacja_r(Wezel <T> *rodzic)
  307.     {
  308.         Wezel<T> *dziecko, *p;
  309.         dziecko = rodzic->left;
  310.         if (dziecko)
  311.         {
  312.             p = rodzic -> up;
  313.             rodzic->left = dziecko->right;
  314.             if (rodzic->left) rodzic->left->up = rodzic;
  315.             dziecko->right = rodzic;
  316.             dziecko->up = p;
  317.             rodzic->up = dziecko;
  318.             if (p)
  319.             {
  320.                 if (p->left == dziecko) p->left = dziecko;
  321.                 else p->right = dziecko;
  322.             }
  323.             else root = dziecko;
  324.         }
  325.  
  326.     }
  327.  
  328.  
  329.     void in_order()
  330.     {
  331.         in(root);
  332.     }
  333.  
  334.     void pre_order()
  335.     {
  336.         pre(root);
  337.     }
  338.  
  339.     void printer(Wezel <T> *wsk)
  340.     {
  341.         if (wsk)
  342.         {
  343.             if (wsk->color == 1)
  344.             {
  345.                 if ((wsk->up == nullptr) && (wsk->right == nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: NULL, l: NULL, r: NULL] (" << wsk->dane << "))," << endl;
  346.                 else if ((wsk->up == nullptr) && (wsk->right != nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: NULL, l: " << wsk->left->indeks << ", r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  347.                 else if ((wsk->up == nullptr) && (wsk->right == nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: NULL, l: " << wsk->left->indeks << " r: NULL] (" << wsk->dane << "))," << endl;
  348.                 else if ((wsk->up == nullptr) && (wsk->right != nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: NULL, l: NULL, r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  349.  
  350.                 if ((wsk->up != nullptr) && (wsk->right == nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: " << wsk->up->indeks << ", l: NULL, r: NULL] (" << wsk->dane << "))," << endl;
  351.                 else if ((wsk->up != nullptr) && (wsk->right != nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: " << wsk->up->indeks << ", l: " << wsk->left->indeks << ", r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  352.                 else if ((wsk->up != nullptr) && (wsk->right == nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: " << wsk->up->indeks << ", l: " << wsk->left->indeks << " r: NULL] (" << wsk->dane << "))," << endl;
  353.                 else if ((wsk->up != nullptr) && (wsk->right != nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "RED" << ", p: " << wsk->up->indeks << ", l: NULL, r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  354.  
  355.             }
  356.             else
  357.             {
  358.                 if ((wsk->up == nullptr) && (wsk->right == nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: NULL, l: NULL, r: NULL] (" << wsk->dane << "))," << endl;
  359.                 else if ((wsk->up == nullptr) && (wsk->right != nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: NULL, l: " << wsk->left->indeks << ", r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  360.                 else if ((wsk->up == nullptr) && (wsk->right == nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: NULL, l: " << wsk->left->indeks << " r: NULL] (" << wsk->dane << "))," << endl;
  361.                 else if ((wsk->up == nullptr) && (wsk->right != nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: NULL, l: NULL, r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  362.  
  363.                 if ((wsk->up != nullptr) && (wsk->right == nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: " << wsk->up->indeks << ", l: NULL, r: NULL] (" << wsk->dane << "))," << endl;
  364.                 else if ((wsk->up != nullptr) && (wsk->right != nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: " << wsk->up->indeks << ", l: " << wsk->left->indeks << ", r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  365.                 else if ((wsk->up != nullptr) && (wsk->right == nullptr) && (wsk->left != nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: " << wsk->up->indeks << ", l: " << wsk->left->indeks << " r: NULL] (" << wsk->dane << "))," << endl;
  366.                 else if ((wsk->up != nullptr) && (wsk->right != nullptr) && (wsk->left == nullptr)) cout << "(" << wsk->indeks << ": [" << "BLACK" << ", p: " << wsk->up->indeks << ", l: NULL, r: " << wsk->right->indeks << "] (" << wsk->dane << "))," << endl;
  367.             }
  368.             printer(wsk->left);
  369.             printer(wsk->right);
  370.         }
  371.     }
  372.  
  373.  
  374.     //bool spr()
  375.  
  376.  
  377.     void print()
  378.     {
  379.         //wysokosc();
  380.         printer(root);
  381.     }
  382.  
  383. };
  384.  
  385.  
  386.  
  387.  
  388. std::random_device rd;
  389. std::default_random_engine generator(rd());
  390. std::uniform_int_distribution<long long> zakres(0, 10000000);
  391.  
  392.  
  393.  
  394. struct fruct
  395. {
  396.     long long a;
  397.     char b;
  398.  
  399.     fruct()
  400.     {
  401.         a =zakres(generator);
  402.         b = 'S';
  403.     }
  404.     fruct(int x, char y)
  405.     {
  406.         a = x;
  407.         b = y;
  408.     }
  409.  
  410.     bool operator <(const fruct &n) const{
  411.         return (a < n.a);
  412.     }
  413.  
  414.     bool operator >(const fruct &n)const{
  415.         return (a > n.a);
  416.     }
  417.     bool operator ==(const fruct &n)const{
  418.         return (a == n.a);
  419.     }
  420.  
  421. };
  422.  
  423. ostream &operator <<(ostream&stream, const fruct &n)
  424. {
  425.     return (stream << n.a <<","<< n.b);
  426. }
  427.  
  428.  
  429.  
  430.  
  431. int main() {
  432.  
  433.     Drzewo<fruct> *d1=new Drzewo<fruct>();
  434.     const int max_order = 1;
  435.     //for (int i = 1; i <= max_order; i++)
  436.     //{
  437.        
  438.         for (int j = 0; j <100; j++)
  439.         {
  440.             d1->dodaj_nowy_element(fruct{});
  441.         }
  442.  
  443.     //}
  444.         d1->print();
  445.  
  446. //  d1->pre_order();
  447.     //int licznik_powtorzen=0;
  448.     //long long a=0;
  449.     //
  450.     //for (long long i = 0; i < 100; i++)
  451.     //{
  452.     // 
  453.     //  a =zakres(generator);
  454.     //  tab[i] = a;
  455.     //  for (long long j = 0; j < i; j++)
  456.     //  {
  457.     //      if (tab[j] == tab[i])
  458.     //      {
  459.     //          licznik_powtorzen++;
  460.     //      }
  461.  
  462.     //  }
  463.     //}
  464.     //cout << licznik_powtorzen << "===" << endl;
  465.  
  466.    
  467.     /*int liczba = 0;*/
  468.     //for (int i = 0; i < 10; i++)
  469.     //{
  470.     //  liczba = rand() % 1000;
  471.     //  cout << liczba << endl;
  472.     ////    d1.dodaj_nowy_element(liczba);
  473.     ////}
  474.  
  475.     //Drzewo<int> d1;
  476.  
  477.     //for (int i = 0; i < 1000; i++)
  478.     //{
  479.  
  480.     //  d1.dodaj_nowy_element(rand()%32000);
  481.     //}
  482.  
  483.  
  484.     //d1.dodaj_nowy_element(55);
  485.     //d1.dodaj_nowy_element(69);
  486.     //d1.dodaj_nowy_element(62);
  487.     //d1.dodaj_nowy_element(57);
  488.  
  489.     //d1.dodaj_nowy_element(35);
  490.     //d1.dodaj_nowy_element(83);
  491.     //d1.dodaj_nowy_element(72);
  492.     //d1.dodaj_nowy_element(74);
  493.  
  494.     //d1.pre_order();
  495.  
  496.     //d1.dodaj_nowy_element(20);
  497.     //d1.dodaj_nowy_element(2);
  498.     //d1.dodaj_nowy_element(34);
  499.     //d1.dodaj_nowy_element(16);
  500.  
  501.     //d1.dodaj_nowy_element(96);
  502.     //d1.dodaj_nowy_element(12);
  503.     //d1.dodaj_nowy_element(9);
  504.     //d1.dodaj_nowy_element(44);
  505.  
  506.     //d1.dodaj_nowy_element(4);
  507.     //d1.dodaj_nowy_element(88);
  508.     //d1.dodaj_nowy_element(77);
  509.     //d1.dodaj_nowy_element(66);
  510.  
  511.     //d1.dodaj_nowy_element(55);
  512.     //d1.dodaj_nowy_element(33);
  513.     //d1.dodaj_nowy_element(22);
  514.     //d1.dodaj_nowy_element(11);
  515.  
  516.  
  517.     //d1.dodaj_nowy_element(67);
  518.     //d1.dodaj_nowy_element(52);
  519.     //d1.dodaj_nowy_element(31);
  520.     //d1.dodaj_nowy_element(16);
  521.  
  522.     //d1.dodaj_nowy_element(47);
  523.     //d1.dodaj_nowy_element(99);
  524.     //d1.dodaj_nowy_element(1);
  525.     //d1.dodaj_nowy_element(53);
  526.  
  527.     //d1.dodaj_nowy_element(1);
  528.     //d1.dodaj_nowy_element(2);
  529.     //d1.dodaj_nowy_element(3);
  530.  
  531.  
  532.     //d1.dodaj_nowy_element(59);
  533.     //d1.dodaj_nowy_element(66);
  534.     /*d1.dodaj_nowy_element(3535);
  535.     d1.dodaj_nowy_element(9989);
  536.     d1.dodaj_nowy_element(66765);
  537.     d1.dodaj_nowy_element(353);*/
  538.     //d1.print();
  539.     //
  540.  
  541.     //d1.search(2);
  542.     //d1.search(66);
  543.  
  544.     //d1.wysokosc();
  545.  
  546.  
  547.  
  548.     system("pause");
  549.     return 0;
  550. }
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!