baadgeorge

Untitled

Apr 15th, 2021 (edited)
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <ctime>
  3. #include <iomanip>
  4.  
  5. using namespace std;
  6.  
  7. int maximum(int a, int b)
  8. {
  9.     if (a > b) return a;
  10.     else return b;
  11. }
  12.  
  13. int minimum(int a, int b)
  14. {
  15.     if (a > b) return b;
  16.     else return a;
  17. }
  18.  
  19. struct Node
  20. {
  21.     int key;
  22.     struct Node* left;
  23.     struct Node* right;
  24. };
  25.  
  26. typedef struct Node N;
  27.  
  28. N* treeInit(int _key)
  29. {
  30.     N* newNode = new N;
  31.     newNode->key = _key;
  32.     newNode->left = NULL;
  33.     newNode->right = NULL;
  34.     return newNode;
  35. }
  36.  
  37. N* searchInsert(N* Root, int _key)
  38. {
  39.     N* tmp = Root;
  40.     N* prev = NULL;
  41.     bool found = false;
  42.  
  43.     while ((tmp != NULL) && (found == false))
  44.     {
  45.         prev = tmp;
  46.         if (_key == tmp->key)
  47.             found = true;
  48.         else
  49.         {
  50.             if (_key < tmp->key) tmp = tmp->left;
  51.             else  tmp = tmp->right;
  52.         }
  53.     }
  54.     if (found)
  55.         return tmp;
  56.  
  57.     N* newNode = new N;
  58.     newNode->key = _key;
  59.     newNode->left = NULL;
  60.     newNode->right = NULL;
  61.     if (_key < prev->key)
  62.         prev->left = newNode;
  63.     else
  64.         prev->right = newNode;
  65.     return newNode;
  66. }
  67.  
  68. int MaxTreeH(N* Root) {
  69.     if (Root == NULL)
  70.         return 0;
  71.     return 1 + maximum(MaxTreeH(Root->left), MaxTreeH(Root->right));
  72. }
  73.  
  74. int MinTreeH(N* Root) {
  75.     if (Root == NULL)
  76.         return 0;
  77.     return 1 + minimum(MinTreeH(Root->left), MinTreeH(Root->right));
  78. }
  79.  
  80. void printTree(N* Root, int level)
  81. {
  82.     if (Root != NULL)
  83.     {
  84.         printTree(Root->right, level + 1);
  85.         for (int i = 0; i < level; i++) cout << "   ";
  86.         cout << Root->key << endl;
  87.         printTree(Root->left, level + 1);
  88.     }
  89. }
  90.  
  91. void deleteTree(N* Root)
  92. {
  93.     if (Root == NULL) return;
  94.  
  95.     deleteTree(Root->left);
  96.     deleteTree(Root->right);
  97.     delete Root;
  98. }
  99.  
  100. struct RNode
  101. {
  102.     int key;
  103.     int size;
  104.     RNode* left;
  105.     RNode* right;
  106. };
  107.  
  108. typedef RNode* RN;
  109.  
  110. RN RTreeInit(int _key)
  111. {
  112.     RN newNode = new RNode;
  113.     newNode->key = _key;
  114.     newNode->left = NULL;
  115.     newNode->right = NULL;
  116.     return newNode;
  117. }
  118.  
  119. void printRTree(RN Root, int level)
  120. {
  121.     if (Root != NULL)
  122.     {
  123.         printRTree(Root->right, level + 1);
  124.         for (int i = 0; i < level; i++) cout << "   ";
  125.         cout << Root->key << endl;
  126.         printRTree(Root->left, level + 1);
  127.     }
  128. }
  129.  
  130. int SizeRTree(RN _node)
  131. {
  132.     if (_node == NULL) return 0;
  133.     return _node->size;
  134. }
  135.  
  136. void fixRTreeSize(RN _node)
  137. {
  138.     _node->size = SizeRTree(_node->left) + SizeRTree(_node->right) + 1;
  139. }
  140.  
  141. RN rotateRight(RN _node)
  142. {
  143.     RN tmp = _node->left;
  144.     if (!tmp) return _node;
  145.     _node->left = tmp->right;
  146.     tmp->right = _node;
  147.     tmp->size = _node->size;
  148.     fixRTreeSize(_node);
  149.     return tmp;
  150. }
  151.  
  152. RN rotateLeft(RN _node)
  153. {
  154.     RN tmp = _node->right;
  155.     if (!tmp) return _node;
  156.     _node->right = tmp->left;
  157.     tmp->left = _node;
  158.     tmp->size = _node->size;
  159.     fixRTreeSize(_node);
  160.     return tmp;
  161. }
  162.  
  163. RN insertToRTreeRoot(RN* _node, int _key)
  164. {
  165.     if (!(*_node))
  166.     {
  167.         RN newNode = new RNode;
  168.         newNode->size = 1;
  169.         newNode->left = NULL;
  170.         newNode->right = NULL;
  171.         newNode->key = _key;
  172.         return newNode;
  173.     }
  174.  
  175.     if (_key < (*_node)->key)
  176.     {
  177.         (*_node)->left = insertToRTreeRoot(&((*_node)->left), _key);
  178.         return rotateRight((*_node));
  179.     }
  180.     else
  181.     {
  182.         (*_node)->right = insertToRTreeRoot(&((*_node)->right), _key);
  183.         return rotateLeft((*_node));
  184.     }
  185. }
  186.  
  187. RN insertRand(RN* _node, int _key)
  188. {
  189.     if (!(*_node))
  190.     {
  191.         RN newNode = new RNode;
  192.         newNode->size = 1;
  193.         newNode->left = NULL;
  194.         newNode->right = NULL;
  195.         newNode->key = _key;
  196.         return newNode;
  197.     }
  198.     if (rand() % ((*_node)->size + 1) == 0) return (*_node) = insertToRTreeRoot(_node, _key);
  199.     if ((*_node)->key > _key)   (*_node)->left = insertRand(&((*_node)->left), _key);
  200.     else (*_node)->right = insertRand(&((*_node)->right), _key);
  201.     fixRTreeSize((*_node));
  202.     return (*_node);
  203. }
  204.  
  205. int getMaxRTreeHeight(RN Root) {
  206.     if (Root == NULL)
  207.         return 0;
  208.     return 1 + maximum(getMaxRTreeHeight(Root->left), getMaxRTreeHeight(Root->right));
  209. }
  210.  
  211. int getMinRTreeHeight(RN Root) {
  212.     if (Root == NULL)
  213.         return 0;
  214.     return 1 + minimum(getMinRTreeHeight(Root->left), getMinRTreeHeight(Root->right));
  215. }
  216.  
  217. void deleteRTree(RN Root)
  218. {
  219.     if (Root == NULL) return;
  220.  
  221.     deleteRTree(Root->left);
  222.     deleteRTree(Root->right);
  223.     delete Root;
  224. }
  225.  
  226. struct DATA
  227. {
  228.     int* mas;
  229.     int min;
  230.     int max;
  231.     int size;
  232. };
  233.  
  234. typedef struct DATA Data;
  235.  
  236.  
  237. int random(int N)
  238. {
  239.     int result = rand() % N;
  240.     return result;
  241. }
  242.  
  243.  
  244. int formRArray(Data* data)
  245. {
  246.     int tmp;
  247.     bool inArray;
  248.     int i = 0;
  249.     if ((data->max - data->min) < data->size) return -1;
  250.     while (i < data->size)
  251.     {
  252.         inArray = false;
  253.         tmp = data->min + random(data->max - data->min);
  254.         for (int j = 0; j < i; j++)
  255.         {
  256.             if (data->mas[j] == tmp)
  257.             {
  258.                 inArray = true;
  259.                 break;
  260.             }
  261.         }
  262.         if (inArray == false)
  263.         {
  264.             data->mas[i] = tmp;
  265.             i++;
  266.         }
  267.     }
  268.     return 0;
  269. }
  270.  
  271. int copyArray(Data dataFrom, Data* dataTo)
  272. {
  273.     for (int i = 0; i < dataFrom.size; i++)
  274.     {
  275.         dataTo->mas[i] = dataFrom.mas[i];
  276.     }
  277.     return 0;
  278. }
  279.  
  280.  
  281. void printMas(Data& data)
  282. {
  283.     for (int i = 0; i < data.size; i++)
  284.         cout << data.mas[i] << ' ';
  285.     cout << '\n';
  286. }
  287.  
  288. void ShellSort(Data& data)
  289. {
  290.     int h = 0;
  291.  
  292.     while (h < data.size / 3)
  293.     {
  294.         h = 3 * h + 1;
  295.     }
  296.  
  297.     for (h; h > 0; h = (h - 1) / 3)
  298.     {
  299.         for (int i = h; i < data.size; i++)
  300.         {
  301.             int j = i;
  302.             int tmp = data.mas[i];
  303.  
  304.             for (j = i; j >= h && data.mas[j - h] > tmp; j -= h)
  305.             {
  306.                 data.mas[j] = data.mas[j - h];
  307.  
  308.             }
  309.             data.mas[j] = tmp;
  310.         }
  311.     }
  312.  
  313.     return;
  314. }
  315.  
  316. int main()
  317. {
  318.     system("color F0");
  319.     setlocale(LC_ALL, "RUS");
  320.  
  321.     srand(time(NULL));
  322.  
  323.     N* Tree1 = NULL;
  324.     N* Tree2 = NULL;
  325.  
  326.     RN RandTree1 = NULL;
  327.     RN RandTree2 = NULL;
  328.  
  329.     Data unsortedArray{ NULL, 0, 1000, 10 };
  330.     Data sortedArray{ NULL, 0, 1000, 10 };
  331.  
  332.     unsortedArray.mas = new int[unsortedArray.size];
  333.  
  334.     formRArray(&unsortedArray);
  335.  
  336.     sortedArray.mas = new int[sortedArray.size];
  337.  
  338.     copyArray(unsortedArray, &sortedArray);
  339.  
  340.     ShellSort(sortedArray);
  341.  
  342.     cout << "Несортированная последовательность: "; printMas(unsortedArray);
  343.     cout << "\nСортированная последовательность: "; printMas(sortedArray);
  344.  
  345.     Tree1 = treeInit(unsortedArray.mas[0]);
  346.     Tree2 = treeInit(sortedArray.mas[0]);
  347.  
  348.     for (int i = 1; i < unsortedArray.size; i++)
  349.     {
  350.         searchInsert(Tree1, unsortedArray.mas[i]);
  351.     }
  352.  
  353.     for (int i = 0; i < unsortedArray.size; i++)
  354.     {
  355.         RandTree1 = insertRand(&RandTree1, unsortedArray.mas[i]);
  356.     }
  357.  
  358.     for (int i = 1; i < sortedArray.size; i++)
  359.     {
  360.         searchInsert(Tree2, sortedArray.mas[i]);
  361.     }
  362.  
  363.     for (int i = 0; i < sortedArray.size; i++)
  364.     {
  365.         RandTree2 = insertRand(&RandTree2, sortedArray.mas[i]);
  366.     }
  367.  
  368.    
  369.     cout << "\nДеревья для несортированной последовательности: \n\n";
  370.  
  371.     cout << "\nОбычное дерево:\n";
  372.     printTree(Tree1, 0);
  373.     cout << "\nМаксимальная высота: " << MaxTreeH(Tree1) << endl;
  374.     cout << "Минимальная высота: " << MinTreeH(Tree1) << endl;
  375.     cout << "\nРандомизированное дерево:\n";
  376.     printRTree(RandTree1, 0);
  377.     cout << "\nМаксимальная высота: " << getMaxRTreeHeight(RandTree1) << endl;
  378.     cout << "Минимальная высота: " << getMinRTreeHeight(RandTree1) << endl;
  379.  
  380.     cout << "\n\nДеревья для сортированной последовательности: \n\n";
  381.  
  382.     cout << "\nОбычное дерево:\n";
  383.     printTree(Tree2, 0);
  384.     cout << "\nМаксимальная высота: " << MaxTreeH(Tree2) << endl;
  385.     cout << "Минимальная высота: " << MinTreeH(Tree2) << endl;;
  386.     cout << "\nРандомизированное дерево:\n";
  387.     printRTree(RandTree2, 0);
  388.     cout << "\nМаксимальная высота: " << getMaxRTreeHeight(RandTree2) << endl;
  389.     cout << "Минимальная высота: " << getMinRTreeHeight(RandTree2) << endl;
  390.  
  391.    
  392.  
  393.     deleteTree(Tree1);
  394.     deleteTree(Tree2);
  395.     deleteRTree(RandTree1);
  396.     deleteRTree(RandTree2);
  397.  
  398.     delete[] unsortedArray.mas;
  399.     delete[] sortedArray.mas;
  400.  
  401.     cout << endl;
  402.  
  403.     for (int keyCount = 25; keyCount <= 300; keyCount = keyCount + 25)
  404.     {
  405.         Tree1 = NULL;
  406.         Tree2 = NULL;
  407.  
  408.         RandTree1 = NULL;
  409.         RandTree2 = NULL;
  410.  
  411.         unsortedArray.size = keyCount;
  412.         sortedArray.size = keyCount;
  413.  
  414.         unsortedArray.mas = new int[keyCount];
  415.         formRArray(&unsortedArray);
  416.         sortedArray.mas = new int[keyCount];
  417.         copyArray(unsortedArray, &sortedArray);
  418.         ShellSort(sortedArray);
  419.  
  420.         Tree1 = treeInit(unsortedArray.mas[0]);
  421.         Tree2 = treeInit(sortedArray.mas[0]);
  422.         RandTree1 = insertRand(&RandTree1, unsortedArray.mas[0]);
  423.         RandTree2 = insertRand(&RandTree2, unsortedArray.mas[0]);
  424.  
  425.         for (int i = 1; i < keyCount; i++)
  426.         {
  427.             searchInsert(Tree1, unsortedArray.mas[i]);
  428.             RandTree1 = insertRand(&RandTree1, unsortedArray.mas[i]);
  429.             searchInsert(Tree2, sortedArray.mas[i]);
  430.             RandTree2 = insertRand(&RandTree2, sortedArray.mas[i]);
  431.         }
  432.  
  433.         cout << " n = " << keyCount << endl;
  434.         cout << " Случайная последовательность максимум:" << endl;
  435.         cout << "   Обычное дерево: высота " << MaxTreeH(Tree1) << endl;
  436.         cout << "   Рандом. дерево: высота " << MaxTreeH(Tree2) << endl;
  437.         cout << "\n Упорядоченная последовательность максимум:" << endl;
  438.         cout << "   Обычное дерево: высота " << getMaxRTreeHeight(RandTree1) << endl;
  439.         cout << "   Рандом. дерево: высота " << getMaxRTreeHeight(RandTree2) << endl;
  440.         cout << "\n Случайная последовательность минимум:" << endl;
  441.         cout << "   Обычное дерево: высота " << MinTreeH(Tree1) << endl;
  442.         cout << "   Рандом. дерево: высота " << MinTreeH(Tree2) << endl;
  443.         cout << "\n Упорядоченная последовательность минимум:" << endl;
  444.         cout << "   Обычное дерево: высота " << getMinRTreeHeight(RandTree1) << endl;
  445.         cout << "   Рандом. дерево: высота " << getMinRTreeHeight(RandTree2) << "\n\n\n";
  446.  
  447.         deleteTree(Tree1);
  448.         deleteTree(Tree2);
  449.         deleteRTree(RandTree1);
  450.         deleteRTree(RandTree2);
  451.  
  452.         delete unsortedArray.mas;
  453.         delete sortedArray.mas;
  454.     }
  455. }
Add Comment
Please, Sign In to add comment