SHARE
TWEET

Drzewo

a guest Nov 14th, 2019 111 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ALGO2 IS1 211A LAB03
  2. //Jakub Ogryzek
  3. //oj44443@zut.edu.pl
  4. #include "pch.h"
  5. #include <iostream>
  6. #include <ctime>
  7. #include <random>
  8.  
  9. using namespace std;
  10.  
  11. template <typename T>
  12. class Node {
  13. public:
  14.     T data;
  15.     Node *left;
  16.     Node *right;
  17.     Node *parent;
  18.     //0 to czerwony, 1 to czarny;
  19.     bool color;
  20.     Node()
  21.     {
  22.         left = nullptr;
  23.         right = nullptr;
  24.         parent = nullptr;
  25.         color = 1;
  26.     }
  27. };
  28.  
  29. template <typename T>
  30. class Tree {
  31. public:
  32.     Node<T> *root;
  33.     int counter;
  34.     Tree()
  35.     {
  36.         counter = 0;
  37.         root = nullptr;
  38.     }
  39.     bool Insert(const T&data)
  40.     {
  41.         if (root == nullptr)
  42.         {
  43.             root = new Node<T>;
  44.             //0 to czerwony, 1 to czarny;
  45.             root->color = 1;
  46.             root->data = data;
  47.             counter += 1;
  48.         }
  49.         else
  50.         {
  51.             Node<T> *current;
  52.             current = root;
  53.             while (current != nullptr)
  54.             {
  55.                 if (data < current->data)
  56.                 {
  57.                     //w lewo
  58.                     if (current->left == nullptr)
  59.                     {
  60.                         current->left = new Node<T>;
  61.                         //current = current->left;
  62.                         //current->data = data;
  63.                         current->left->data = data;
  64.                         current->left->parent = current;
  65.                         //if (current->left->parent->color == 1)
  66.                             //current->left->color = 0;
  67.                         counter += 1;
  68.                         current = current->left;
  69.                         return 1;
  70.                         //return current;
  71.                         //break;
  72.                     }
  73.                     else
  74.                     {
  75.                         current = current->left;
  76.                     }
  77.                 }
  78.                 if (data > current->data)
  79.                 {
  80.                     //w prawo
  81.                     if (current->right == nullptr)
  82.                     {
  83.                         current->right = new Node<T>;
  84.                         //current = current->right;
  85.                         //current->data = data;
  86.                         current->right->data = data;
  87.                         current->right->parent = current;
  88.                         //if (current->right->parent->color == 1)
  89.                             //current->right->color = 0;
  90.                         counter += 1;
  91.                         current = current->right;
  92.                         return 1;
  93.                         //return current;
  94.                         //break;
  95.                     }
  96.                     else
  97.                     {
  98.                         current = current->right;
  99.                     }
  100.                 }
  101.                 if (data == current->data)
  102.                 {
  103.                     //break;
  104.                     //return nullptr;
  105.                     return 0;
  106.                 }
  107.             }
  108.         }
  109.     }
  110.     void AddNewElement(const T&data)
  111.     {
  112.         //0 to czerwony, 1 to czarny;
  113.         /*Node<T>*temp=nullptr;
  114.         while(temp==nullptr)
  115.         temp=Insert(data);*/
  116.         int flag = 0;
  117.         while (flag==0)
  118.         flag=Insert(data);
  119.         Node<T>*temp = ReturnFunction(data);
  120.         temp->color = 0;
  121.         while (temp != root && temp->parent->color == 0)
  122.         {
  123.             if (temp->parent == temp->parent->parent->left)
  124.             {
  125.                 Node<T>*stryj = temp->parent->parent->right; //stryj temp'a
  126.                 //POPRAWIĆ
  127.                 //if (stryj == nullptr)
  128.                 //{
  129.                     //RotateRight(temp, temp->parent);
  130.                 //}
  131.                 //else
  132.                 if (stryj->color == 0)
  133.                 {
  134.                     temp->parent->color = 1;
  135.                     stryj->color = 1;
  136.                     temp->parent->parent->color = 0;
  137.                     temp = temp->parent->parent; //wedrowka o 2 poziomy wyzej
  138.                 }
  139.                 else //stryj jest czarny
  140.                 {
  141.                     if (temp == temp->parent->right) //temp jest prawym potomkiem
  142.                     {
  143.                         RotateLeft(temp->parent, temp);
  144.                         temp = temp->parent;
  145.                     }
  146.                     temp->parent->color = 1;
  147.                     temp->parent->parent = 0;
  148.                     RotateRight(temp, temp->parent);
  149.                 }
  150.             }
  151.             else //ojciec x jest prawym potomkiem dziadka
  152.             {
  153.                 Node<T>*stryj = temp->parent->parent->left; //stryj temp'a
  154.                 //POPRAWIĆ
  155.                 //if (stryj == nullptr)
  156.                 //{
  157.                     //RotateLeft(temp->parent, temp);
  158.                 //}
  159.                 //else
  160.                 if (stryj->color == 0)
  161.                 {
  162.                     temp->parent->color = 1;
  163.                     stryj->color = 1;
  164.                     temp->parent->parent->color = 0;
  165.                     temp = temp->parent->parent; //wedrowka o 2 poziomy wyzej
  166.                 }
  167.                 else //stryj jest czarny
  168.                 {
  169.                     if (temp == temp->parent->left) //temp jest lewym potomkiem
  170.                     {
  171.                         RotateRight(temp, temp->parent);
  172.                         temp = temp->parent;
  173.                     }
  174.                     temp->parent->color = 1;
  175.                     temp->parent->parent->color = 0;
  176.                     RotateLeft(temp->parent, temp);
  177.                 }
  178.             }
  179.         }
  180.         root->color = 1; //korzen zawsze jest czarny
  181.     }
  182.     Node<T> *ReturnFunction(const T&key)
  183.     {
  184.         Node<T> *current;
  185.         current = root;
  186.         if (current->data == key)
  187.         {
  188.             return current;
  189.         }
  190.         else
  191.         {
  192.             while (current != nullptr)
  193.             {
  194.                 if (current->data > key)
  195.                 {
  196.                     //w lewo
  197.                     //current = current->left;
  198.                     if (current->left != nullptr)
  199.                     {
  200.                         if (current->left->data == key)
  201.                         {
  202.                             return current->left;
  203.                         }
  204.                     }
  205.                 }
  206.                 if (current->data > key)
  207.                     current = current->left;
  208.                 if (current->data < key)
  209.                 {
  210.                     //w prawo
  211.                     //current = current->right;
  212.                     if (current->right != nullptr)
  213.                     {
  214.                         if (current->right->data == key)
  215.                         {
  216.                             return current->right;
  217.                         }
  218.                     }
  219.                 }
  220.                 if (current->data < key)
  221.                     current = current->right;
  222.             }
  223.         }
  224.         return NULL;
  225.     }
  226.     Node<T> *SearchElement(const T&key)
  227.     {
  228.         Node<T> *current;
  229.         current = root;
  230.         if (current->data == key)
  231.         {
  232.             cout << "Znaleziono wezel o podanym kluczu (" << current->data << ")" << endl;
  233.             return current;
  234.         }
  235.         else
  236.         {
  237.             while (current != nullptr)
  238.             {
  239.                 if (current->data > key)
  240.                 {
  241.                     //w lewo
  242.                     //current = current->left;
  243.                     if (current->left != nullptr)
  244.                     {
  245.                         if (current->left->data == key)
  246.                         {
  247.                             cout << "Znaleziono wezel o podanym kluczu (" << current->left->data << ")" << endl;
  248.                             return current->left;
  249.                         }
  250.                     }
  251.                 }
  252.                 if (current->data > key)
  253.                     current = current->left;
  254.                 if (current->data < key)
  255.                 {
  256.                     //w prawo
  257.                     //current = current->right;
  258.                     if (current->right != nullptr)
  259.                     {
  260.                         if (current->right->data == key)
  261.                         {
  262.                             cout << "Znaleziono wezel o podanym kluczu (" << current->right->data << ")" << endl;
  263.                             return current->right;
  264.                         }
  265.                     }
  266.                 }
  267.                 if (current->data < key)
  268.                     current = current->right;
  269.             }
  270.         }
  271.         cout << "Nie znaleziono wezla o podanym kluczu (" << key << ")" << endl;
  272.         return NULL;
  273.     }
  274.     void PreOrderRek(Node<T> *current)
  275.     {
  276.         cout << current->data << ", ";
  277.         if (current->left != nullptr)
  278.             PreOrderRek(current->left);
  279.         if (current->right != nullptr)
  280.             PreOrderRek(current->right);
  281.     }
  282.     void PreOrder()
  283.     {
  284.         Node<T> *current;
  285.         current = root;
  286.         cout << "Przejscie Pre-Order:" << endl;
  287.         PreOrderRek(current);
  288.         cout << endl;
  289.     }
  290.     void InOrderRek(Node<T> *current)
  291.     {
  292.         if (current->left != nullptr)
  293.             InOrderRek(current->left);
  294.         cout << current->data << ", ";
  295.         if (current->right != nullptr)
  296.             InOrderRek(current->right);
  297.     }
  298.     void InOrder()
  299.     {
  300.         Node<T> *current;
  301.         current = root;
  302.         cout << "Przejscie In-Order:" << endl;
  303.         InOrderRek(current);
  304.         cout << endl;
  305.     }
  306.     void ToStringRek(Node<T> *current)
  307.     {
  308.         ToStringFunction(current);
  309.         if (current->left != nullptr)
  310.             ToStringRek(current->left);
  311.         if (current->right != nullptr)
  312.             ToStringRek(current->right);
  313.     }
  314.     void ToStringFunction(Node<T> *current)
  315.     {
  316.         cout << "(" << current->data << ") [";
  317.         if (current->color == 1)
  318.             cout << "black";
  319.         if (current->color == 0)
  320.             cout << "red";
  321.         if (current->parent == nullptr)
  322.             cout << ", parent: NULL, left: ";
  323.         else
  324.             cout << ", parent: " << current->parent->data << ", left: ";
  325.         if (current->left == nullptr)
  326.             cout << "NULL, right: ";
  327.         else
  328.             cout << current->left->data << ", right: ";
  329.         if (current->right == nullptr)
  330.             cout << "NULL]";
  331.         else
  332.             cout << current->right->data << "]";
  333.         cout << endl;
  334.     }
  335.     int HeightRek(Node <T> *current)
  336.     {
  337.         if (current == nullptr)
  338.             return 0;
  339.         int height_left = HeightRek(current->left);
  340.         int height_right = HeightRek(current->right);
  341.         if (height_left < height_right)
  342.             return height_right + 1;
  343.         else
  344.             return height_left + 1;
  345.     }
  346.     void Height()
  347.     {
  348.         Node<T> *current;
  349.         current = root;
  350.         int tree_height = HeightRek(current);
  351.         cout << "Wysokosc drzewa wynosi: " << tree_height << endl;
  352.     }
  353.     void ToString()
  354.     {
  355.         cout << "red black tree:" << endl;
  356.         cout << "size: " << counter << endl;
  357.         Node<T> *current;
  358.         current = root;
  359.         ToStringRek(current);
  360.     }
  361.     void TymSobieSprawdzam()
  362.     {
  363.         Node<T> *temp;
  364.         temp = root;
  365.         cout << "Drzewo:" << endl;
  366.         cout << "       " << temp->data << endl;
  367.         cout << "   " << temp->left->data << "      " << temp->right->data << endl;
  368.         cout << temp->left->left->data << "     " << temp->left->right->data << " " << temp->right->left->data << "     " << temp->right->right->data << endl;
  369.     }
  370.     void DeleteTree(Node <T> *root)
  371.     {
  372.         if (root->left != nullptr)
  373.             DeleteTree(root->left);
  374.         if (root->right != nullptr)
  375.             DeleteTree(root->right);
  376.         delete root;
  377.     }
  378.     void RotateLeft(Node<T>*X, Node<T> *Y)
  379.     {
  380.         /*if (X->right == Y)
  381.         {
  382.             if (X->parent != nullptr)
  383.             {
  384.                 Y->parent = X->parent;
  385.                 X->parent = Y;
  386.             }
  387.             else
  388.             {
  389.                 Y->parent = nullptr;
  390.                 X->parent = Y;
  391.             }
  392.             if (X == root)
  393.                 root = Y;
  394.             if (Y->left != nullptr)
  395.             {
  396.                 X->right = Y->left;
  397.                 Y->left = X;
  398.             }
  399.             else
  400.             {
  401.                 X->right = nullptr;
  402.                 Y->left = X;
  403.             }
  404.         }
  405.         else
  406.             cout << "Wezel Y nie jest prawym dzieckiem wezla X" << endl;*/
  407.         if (Y->left != nullptr)
  408.             X->right = Y->left;
  409.         else
  410.             X->right = nullptr;
  411.         if (Y->left != nullptr)
  412.             Y->left->parent = X;
  413.         Y->left = X;
  414.         X->parent = Y;
  415.         if (X == root)
  416.             root = Y;
  417.     }
  418.     void RotateRight(Node<T>*X, Node<T> *Y)
  419.     {
  420.         /*if (Y->left == X)
  421.         {
  422.             if (Y == root)
  423.                 root = X;
  424.             if (Y->parent != nullptr)
  425.             {
  426.                 X->parent = Y->parent;
  427.                 Y->parent = X;
  428.             }
  429.             else
  430.             {
  431.                 X->parent = nullptr;
  432.                 Y->parent = X;
  433.             }
  434.             if (Y == root)
  435.                 root = X;
  436.             if (X->right != nullptr)
  437.             {
  438.                 Y->left = X->right;
  439.                 X->right = Y;
  440.             }
  441.             else
  442.             {
  443.                 Y->left = nullptr;
  444.                 X->right = Y;
  445.             }
  446.         }
  447.         else
  448.             cout << "Wezel X nie jest lewym dzieckiem wezla Y" << endl;*/
  449.         if (X->right != nullptr)
  450.             Y->left = X->right;
  451.         else
  452.             Y->left = nullptr;
  453.         if (X->right != nullptr)
  454.             X->right->parent = Y;
  455.         X->right = Y;
  456.         Y->parent = X;
  457.         if (Y == root)
  458.             root = X;
  459.     }
  460. };
  461.  
  462. struct Struktura
  463. {
  464.     int pole1;
  465.     char pole2;
  466.     Struktura()
  467.     {
  468.         const int MAX_ORDER = 8;
  469.         const int n = pow(10, MAX_ORDER);
  470.         std::random_device rd;
  471.         std::default_random_engine generator(rd());
  472.         std::uniform_int_distribution<long long> zakres(0, n);
  473.         pole1 = zakres(generator);
  474.         pole2 = rand() % ('z' - 'a' + 1) + 'a';
  475.     }
  476.     Struktura(int a,char b)
  477.     {
  478.         pole1 = a;
  479.         pole2 = b;
  480.     }
  481.     bool operator ==(const Struktura&n) const
  482.     {
  483.         return pole1 == n.pole1;
  484.     }
  485.     bool operator >(const Struktura&n) const
  486.     {
  487.         return pole1 > n.pole1;
  488.     }
  489.     bool operator <(const Struktura&n) const
  490.     {
  491.         return pole1 < n.pole1;
  492.     }
  493. };
  494.  
  495. ostream& operator <<(ostream&stream, const Struktura&m)
  496. {
  497.     return (stream << m.pole1 << m.pole2);
  498. }
  499.  
  500. int main()
  501. {
  502.     /*srand(time(NULL));
  503.     const int MAX_ORDER = 7;
  504.     Tree<Struktura>*rbt = new Tree<Struktura>();
  505.     //for (int o = 1; o <= MAX_ORDER; o++)
  506.     //{
  507.         const int n = pow(10, 1);
  508.         //Dodawanie do drzewa
  509.         clock_t t1 = clock();
  510.         for (int i = 0; i < n; i++)
  511.         {
  512.             //int flag = 0; //Flaga powtarzajacego sie elementu 0-powtarza sie, wiec element nie zostal dodany 1-nie powtarza sie, wiec zostal dodany
  513.             //while(flag==0)
  514.             //flag=rbt->AddNewElement(Struktura{});
  515.             rbt->AddNewElement(Struktura{});
  516.         }
  517.         clock_t t2 = clock();
  518.         rbt->ToString();
  519.         cout << "Czas wykonania operacji dodawania " << n << " elementow to: " << (double)(t2 - t1) / CLOCKS_PER_SEC << " sekundy" << endl;
  520.         //Usuwanie drzewa
  521.         rbt->DeleteTree(rbt->root);
  522.         system("pause");
  523.     //}*/
  524.    
  525.  
  526.  
  527.     Tree<int> *tree = new Tree<int>();
  528.     //tree->AddNewElement(4);
  529.     //tree->AddNewElement(2);
  530.     //tree->AddNewElement(6);
  531.     //tree->AddNewElement(1);
  532.     //tree->AddNewElement(3);
  533.     //tree->AddNewElement(5);
  534.     //tree->AddNewElement(7);
  535.  
  536.     tree->AddNewElement(6);
  537.     tree->AddNewElement(7);
  538.     tree->AddNewElement(8);
  539.  
  540.     //tree->TymSobieSprawdzam();
  541.     //Node<int> *Sprawdzenie = tree->SearchElement(7);
  542.     //cout << endl;
  543.     //tree->ToString();
  544.     //tree->PreOrder();
  545.     //tree->InOrder();
  546.     system("pause");
  547.     //tree->Height();
  548. }
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