Advertisement
baadgeorge

Untitled

Jun 7th, 2021
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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. }
  456.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement