daily pastebin goal
14%
SHARE
TWEET

Untitled

a guest Dec 9th, 2018 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. //#include "pch.h"
  3. #include <ctime>
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cstring>
  7.  
  8. using namespace std;
  9.  
  10. class BST
  11. {
  12.     struct Node
  13.     {
  14.         int key;
  15.         Node *left;
  16.         Node *right;
  17.     };
  18.  
  19.     int _length = 0;
  20.  
  21.     Node *findParent(Node *node, Node *root)
  22.     {
  23.         static Node *parent = nullptr;
  24.         if (root)
  25.         {
  26.             if (root->left == node || root->right == node)
  27.             {
  28.                 parent = root;
  29.             }
  30.             else
  31.             {
  32.                 parent = findParent(node, root->left);
  33.                 if (!parent)
  34.                 {
  35.                     findParent(node, root->right);
  36.                 }
  37.             }
  38.         }
  39.  
  40.         return parent;
  41.     }
  42.  
  43.  
  44.     Node * findPredecessor(Node *node)
  45.     {
  46.         Node *temp = node->left;
  47.         while (temp->right)
  48.         {
  49.             temp = temp->right;
  50.         }
  51.         return temp;
  52.     }
  53.  
  54.     void inorderSupport(Node *node)
  55.     {
  56.         if (node != nullptr)
  57.         {
  58.             inorderSupport(node->left);
  59.             cout << node->key << "\t";
  60.             inorderSupport(node->right);
  61.         }
  62.  
  63.     }
  64.  
  65. public:
  66.     Node *root;
  67.  
  68.     BST()
  69.     {
  70.         root = nullptr;
  71.     }
  72.  
  73.     ~BST() {}
  74.  
  75.     void insertElement(int key)
  76.     {
  77.         Node *toInsert = new Node;
  78.         toInsert->key = key;
  79.         toInsert->left = nullptr;
  80.         toInsert->right = nullptr;
  81.  
  82.         if (root == nullptr)
  83.         {
  84.             root = toInsert;
  85.             _length++;
  86.         }
  87.         else
  88.         {
  89.             Node *temp = root;
  90.             while (1)
  91.             {
  92.                 if (key == temp->key)
  93.                 {
  94.                     /// juz taki istnieje
  95.                     break;
  96.                 }
  97.                 else if (key < temp->key)
  98.                 {
  99.                     if (!temp->left)
  100.                     {
  101.                         temp->left = toInsert;
  102.                         _length++;
  103.                         break;
  104.                     }
  105.                     temp = temp->left;
  106.                 }
  107.                 else
  108.                 {
  109.                     if (!temp->right)
  110.                     {
  111.                         temp->right = toInsert;
  112.                         _length++;
  113.                         break;
  114.                     }
  115.                     temp = temp->right;
  116.                 }
  117.             }
  118.         }
  119.     }
  120.  
  121.  
  122.     void insertXElements(int x)
  123.     {
  124.         for (int i = 0; i < x; i++)
  125.         {
  126.             insertElement(rand() % 20001 - 10000);
  127.         }
  128.     }
  129.  
  130.     bool findElement(int key)
  131.     {
  132.         if (root == nullptr)
  133.         {
  134.             cout << "Nie udalo sie odnalezc elementu o kluczu " << key << ", poniewaz drzewo jest puste.\n\n";
  135.             return false;
  136.         }
  137.         else
  138.         {
  139.             Node *temp = root;
  140.             while (temp)
  141.             {
  142.                 if (key == temp->key)
  143.                 {
  144.                     //cout << "Znaleziono element o kluczu " << key << "\n\n";
  145.                     return true;
  146.                 }
  147.                 if (key < temp->key) temp = temp->left;
  148.                 else temp = temp->right;
  149.             }
  150.             return false;
  151.         }
  152.     }
  153.  
  154.     void removeElement(int key)
  155.     {
  156.         if (root == nullptr)
  157.         {
  158.             cout << "Nie udalo sie usunac elementu o kluczu " << key << ", poniewaz drzewo jest puste.\n";
  159.             return;
  160.         }
  161.         else
  162.         {
  163.             Node *temp = root;
  164.             if (root->key = key && !(root->left && root->right))
  165.             {
  166.                 cout << "wchodze w usuwanie roota ktory nie ma 2 dzieci\n";
  167.                 if (!root->left && !root->right)
  168.                 {
  169.                     temp = nullptr;
  170.                     delete temp;
  171.                     return;
  172.                 }
  173.                 else if (!root->right)
  174.                 {
  175.                     root = temp->left;
  176.                     temp = nullptr;
  177.                     delete temp;
  178.                     return;
  179.                 }
  180.                 else
  181.                 {
  182.                     root = temp->right;
  183.                     temp = nullptr;
  184.                     delete temp;
  185.                     return;
  186.                 }
  187.             }
  188.             while (temp)
  189.             {
  190.                 if (key == temp->key)
  191.                 {
  192.                     ///usuwanie
  193.  
  194.                     if (key == temp->key)
  195.                     {
  196.                         ///usuwanie
  197.                         if (temp == root && !(temp->left && temp->right))
  198.                         {
  199.                             if (!temp->left && !temp->right)
  200.                             {
  201.                                 delete root;
  202.                                 return;
  203.                             }
  204.                             else if (!temp->right)
  205.                             {
  206.                                 root = temp->left;
  207.                                 delete temp;
  208.                                 return;
  209.                             }
  210.                             else
  211.                             {
  212.                                 root = temp->right;
  213.                                 delete temp;
  214.                                 return;
  215.                             }
  216.                         }
  217.                     }
  218.                     if (!temp->left && !temp->right) /// brak synow
  219.                     {
  220.                         cout << "wchodze w usuwanie bez synow";
  221.                         if (key > findParent(temp, root)->key)
  222.                         {
  223.                             findParent(temp, root)->right = nullptr;
  224.                             temp = nullptr;
  225.                             delete temp;
  226.                         }
  227.                         else
  228.                         {
  229.                             findParent(temp, root)->left = nullptr;
  230.                             temp = nullptr;
  231.                             delete temp;
  232.                         }
  233.                         _length--;
  234.                         cout << "usuniety bez synow\n";
  235.                         return;
  236.                     }
  237.                     else if (!temp->right)///tylko lewy syn
  238.                     {
  239.                         cout << "wchodze w usuwanie z lewym synem";
  240.                         if (key > findParent(temp, root)->key)
  241.                         {
  242.                             findParent(temp, root)->right = temp->left;
  243.                             temp = nullptr;
  244.                             delete temp;
  245.                         }
  246.                         else
  247.                         {
  248.                             findParent(temp, root)->left = temp->left;
  249.                             temp = nullptr;
  250.                             delete temp;
  251.                         }
  252.                         _length--;
  253.                         cout << "usuniety z lewym synem\n";
  254.                         return;
  255.                     }
  256.                     else if (!temp->left)///tylko prawy syn
  257.                     {
  258.                         cout << "wchodze w usuwanie z prawym synem";
  259.                         if (key > findParent(temp, root)->key)
  260.                         {
  261.                             findParent(temp, root)->right = temp->right;
  262.                             temp = nullptr;
  263.                             delete temp;
  264.                         }
  265.                         else
  266.                         {
  267.                             findParent(temp, root)->left = temp->right;
  268.                             temp = nullptr;
  269.                             delete temp;
  270.                         }
  271.                         _length--;
  272.                         cout << "usuniety z prawym synem\n";
  273.                         return;
  274.                     }
  275.                     else /// ma dwoch synow
  276.                     {
  277.                         cout << "wchodze w usuwanie z 2 synami";
  278.                         Node * predecessor = findPredecessor(temp);
  279.                         if (predecessor->left)
  280.                         {
  281.                             findParent(predecessor, root)->right = predecessor->left;
  282.                         }
  283.                         Node *predParent = findParent(predecessor, root);
  284.                         if (predParent->key > predecessor->key)
  285.                         {
  286.                             predParent->left = nullptr;
  287.                         }
  288.                         else
  289.                         {
  290.                             predParent->right = nullptr;
  291.                         }
  292.                         predecessor->right = temp->right;
  293.                         predecessor->left = temp->left;
  294.  
  295.                         cout << "halko zaraz sprawdzacz rootowy\n";
  296.                         if (temp == root)
  297.                         {
  298.                             cout << "wchodze w usuwanie roota!\n";
  299.                             root = predecessor;
  300.                             temp = nullptr;
  301.                             delete temp;
  302.                             _length--;
  303.                             cout << "usuniety root\n";
  304.                             return;
  305.                         }
  306.  
  307.                         Node *tempParent = findParent(temp, root);
  308.  
  309.                         if (key > tempParent->key)
  310.                         {
  311.                             tempParent->right = predecessor;
  312.                         }
  313.                         else
  314.                         {
  315.                             tempParent->left = predecessor;
  316.                         }
  317.                         temp = nullptr;
  318.                         delete temp;
  319.                         _length--;
  320.                         cout << "usuniety z 2 synami\n";
  321.                         return;
  322.                     }
  323.                 }
  324.                 if (key < temp->key)
  325.                 {
  326.                     temp = temp->left;
  327.                 }
  328.                 else
  329.                 {
  330.                     temp = temp->right;
  331.                 }
  332.             }
  333.             /// nie usunieto
  334.         }
  335.     }
  336.  
  337.     void inorder()
  338.     {
  339.         cout << "\nWyswietlanie w trybie inorder:\n";
  340.         inorderSupport(root);
  341.         cout << "\nLiczba elementow: " << _length << "\n";
  342.     }
  343.  
  344.  
  345.     int getRoot()
  346.     {
  347.         return root->key;
  348.     }
  349.  
  350.  
  351.     void insertXElementsR(int x)
  352.     {
  353.         time_t begin, end;
  354.         double time;
  355.         begin = clock();
  356.         for (int i = 0; i < x; i++)
  357.         {
  358.  
  359.             insertElement((rand()*rand()) % 100000);
  360.         }
  361.  
  362.         end = clock();
  363.         time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
  364.         cout << "Udalo sie dodac " << _length << " elementow\n"
  365.             << "Czas: " << time << "ms\n";
  366.     }
  367.  
  368.     void insertXElementsN(int x)
  369.     {
  370.         clock_t begin, end;
  371.         double time;
  372.         int toInsert = 1;
  373.  
  374.         begin = clock();
  375.         for (int i = 0; i < x; i++)
  376.         {
  377.             if (i % 2 == 0)
  378.             {
  379.                 insertElement((rand()*rand()) % 100000);
  380.             }
  381.             else
  382.             {
  383.                 insertElement(toInsert);
  384.                 toInsert++;
  385.             }
  386.         }
  387.         end = clock();
  388.         time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
  389.         cout << "Udalo sie dodac " << _length << " elementow\n"
  390.             << "Czas: " << time << " ms\n";
  391.  
  392.     }
  393.  
  394.     void findNElements(int n)
  395.     {
  396.         clock_t begin, end;
  397.         double time;
  398.         int found = 0;
  399.         begin = clock();
  400.         for (int i = 0; i < n; i++)
  401.         {
  402.             if (findElement((rand()*rand()) % 100000)) found++;
  403.         }
  404.         end = clock();
  405.         time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
  406.         cout << "Udalo sie odnalezc " << found << " elementow\n"
  407.             << "Czas: " << time << " ms\n";
  408.     }
  409.  
  410.     void removeXElements(int x)
  411.     {
  412.         int lengthBefore = _length;
  413.         time_t begin, end;
  414.         double time;
  415.         begin = clock();
  416.         for (int i = 0; i < x; i++)
  417.         {
  418.             removeElement((rand()*rand() % 100000));
  419.         }
  420.         end = clock();
  421.         time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
  422.         cout << "Udalo sie usunac " << lengthBefore - _length << " elementow\n"
  423.             << "Czas: " << time << " ms\n";
  424.     }
  425.  
  426.  
  427. };
  428.  
  429.  
  430.  
  431.  
  432.  
  433. int main(int argc, char *argv[])
  434. {
  435.     srand(time(nullptr));
  436.  
  437.     int size = atoi(argv[1]);
  438.     BST drzewo;
  439.  
  440.  
  441.     if (strcmp(argv[2], "-r") == 0)
  442.     {
  443.         drzewo.insertXElementsR(size);
  444.     }
  445.     else if (strcmp(argv[2], "-n") == 0)
  446.     {
  447.         drzewo.insertXElementsN(size);
  448.     }
  449.     else
  450.     {
  451.         cout << "Bledny przelacznik";
  452.         return -1;
  453.     }
  454.  
  455.     drzewo.findNElements(size);
  456.     drzewo.removeXElements(size);
  457. }
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