Advertisement
Guest User

fidaa

a guest
Apr 20th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.18 KB | None | 0 0
  1. // Do not change the next 7 lines
  2. #include "avl.h"
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. typedef enum Position {LEFT, RIGHT} Position; // TIP: use this in your code!
  7. #define MAX(X,Y) (((X)>(Y))?(X):(Y))
  8. #define ABS(X) ((X<0)?(-X):(X))
  9.  
  10.  
  11. // Fill your info here:
  12. /****
  13. Student1 name: ----- -----
  14. Student2 name: ----- -----
  15.  
  16. Student1 ID: -----------
  17. Student2 ID: -----------
  18. ****/
  19.  
  20.  
  21. // Operations
  22. int height(AVLNodePtr tnode)
  23. {
  24. if (tnode == NULL)
  25. return 0;
  26. return tnode->height;
  27. }
  28. int getBalance(AVLNodePtr tnode)
  29. {
  30. if (tnode == NULL)
  31. return 0;
  32. return height(tnode->child[0]) - height(tnode->child[1]);
  33. }
  34. AVLNodePtr avl_search( AVLNodePtr tnode, int k ){
  35. if (tnode == NULL) return NULL;
  36. if (tnode->key == k)
  37. return tnode;
  38.  
  39.  
  40. if (tnode->key < k)
  41. return avl_search(tnode->child[1], k);
  42.  
  43. return avl_search(tnode->child[0], k);
  44.  
  45.  
  46. }
  47. AVLNodePtr avl_insert( AVLNodePtr tnode, int k ){
  48.  
  49.  
  50.  
  51.  
  52. if (tnode == NULL)
  53. {
  54. tnode = (AVLNode*)malloc(sizeof(AVLNode));
  55. tnode->key = k;
  56. tnode->size = 1;
  57. tnode->height = 0;
  58. tnode->child[0] = NULL;
  59. tnode->child[1] = NULL;
  60. }
  61. else
  62. if (k > tnode->key) // insert in right subtree
  63. {
  64. tnode->child[1] = avl_insert(tnode->child[1], k);
  65. if (BF(tnode) == -2)
  66. if (k>tnode->child[1]->key)
  67. tnode = RR(tnode);
  68. else
  69. tnode = RL(tnode);
  70. }
  71. else
  72. if (k<tnode->key)
  73. {
  74. tnode->child[0] = avl_insert(tnode->child[0], k);
  75. if (BF(tnode) == 2)
  76. if (k < tnode->child[0]->key)
  77. tnode = LL(tnode);
  78. else
  79. tnode = LR(tnode);
  80. }
  81. if (tnode->child[0] == NULL && tnode->child[1] == NULL)
  82. tnode->size = 1;
  83. else if (tnode->child[0] == NULL && tnode->child[1] != NULL)
  84. tnode->size = tnode->child[1]->size + 1;
  85. else if (tnode->child[1] == NULL && tnode->child[0] != NULL)
  86. tnode->size = tnode->child[0]->size + 1;
  87. else tnode->size = tnode->child[0]->size + tnode->child[1]->size + 1;
  88. tnode->height = heightt(tnode);
  89. //tnode->size = sizee(tnode);
  90. return(tnode);
  91. }
  92. int sizee(AVLNodePtr node)
  93. {
  94. if (node == NULL)
  95. return 0;
  96. else
  97. return(sizee(node->child[0]) + 1 + sizee(node->child[1]));
  98. }
  99. AVLNodePtr avl_delete( AVLNodePtr tnode, int k ){
  100. AVLNodePtr p;
  101.  
  102. if (tnode == NULL)
  103. {
  104. return NULL;
  105. }
  106. else
  107. if (k > tnode->key) // insert in right subtree
  108. {
  109. tnode->child[1] = avl_delete(tnode->child[1], k);
  110. if (BF(tnode) == 2)
  111. if (BF(tnode->child[0]) >= 0)
  112. tnode = LL(tnode);
  113. else
  114. tnode = LR(tnode);
  115. }
  116. else
  117. if (k<tnode->key)
  118. {
  119. tnode->child[0] = avl_delete(tnode->child[0], k);
  120. if (BF(tnode) == -2) //Rebalance during windup
  121. if (BF(tnode->child[1]) <= 0)
  122. tnode = RR(tnode);
  123. else
  124. tnode = RL(tnode);
  125. }
  126. else
  127. {
  128. //data to be deleted is found
  129. if (tnode->child[1] != NULL)
  130. { //delete its inorder succesor
  131. p = tnode->child[1];
  132.  
  133. while (p->child[0] != NULL)
  134. p = p->child[0];
  135.  
  136. tnode->key = p->key;
  137. tnode->child[1] = avl_delete(tnode->child[1], p->key);
  138.  
  139. if (BF(tnode) == 2)//Rebalance during windup
  140. if (BF(tnode->child[0]) >= 0)
  141. tnode = LL(tnode);
  142. else
  143. tnode = LR(tnode);
  144. }
  145. else
  146. return(tnode->child[0]);
  147. }
  148. if (tnode->child[0] == NULL && tnode->child[1] == NULL)
  149. tnode->size = 1;
  150. else if (tnode->child[0] == NULL && tnode->child[1] != NULL)
  151. tnode->size = tnode->child[1]->size + 1;
  152. else if (tnode->child[1] == NULL && tnode->child[0] != NULL)
  153. tnode->size = tnode->child[0]->size + 1;
  154. else tnode->size = tnode->child[0]->size + tnode->child[1]->size + 1;
  155. tnode->height = heightt(tnode);
  156. return(tnode);
  157. }
  158.  
  159. AVLNodePtr new_avl_node( int k ){
  160. AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
  161. node->key = k;
  162. node->size = 1;
  163. node->height = 0;
  164. node->child[0] = NULL;
  165. node->child[1] = NULL;
  166. return node;
  167. }
  168.  
  169. void delete_avl_tree( AVLNodePtr root ){
  170. if (root == NULL)
  171. {
  172. return;
  173. }
  174. delete_avl_tree(root->child[0]);
  175. delete_avl_tree(root->child[1]);
  176. free(root);
  177.  
  178. }
  179.  
  180. /*int sizee(AVLNodePtr T) {
  181. int rs, sl;
  182. if (T == NULL)
  183. return 0;
  184. if (T->child[0] == NULL)
  185. sl = 0;
  186. else
  187. sl = 1 + T->child[0]->size;
  188. if (T->child[1] == NULL)
  189. rs = 0;
  190. else
  191. rs = 1 + T->child[1]->size;
  192.  
  193. return (rs + sl+1);
  194. }*/
  195.  
  196.  
  197.  
  198. int heightt(AVLNodePtr T)
  199. {
  200. int lh, rh;
  201. if (T == NULL)
  202. return(0);
  203.  
  204. if (T->child[0] == NULL)
  205. lh = 0;
  206. else
  207. lh = 1 + T->child[0]->height;
  208.  
  209. if (T->child[1] == NULL)
  210. rh = 0;
  211. else
  212. rh = 1 + T->child[1]->height;
  213.  
  214. if (lh>rh)
  215. return(lh);
  216.  
  217. return(rh);
  218. }
  219.  
  220. AVLNodePtr rotateright(AVLNodePtr x)
  221. {
  222. AVLNodePtr y;
  223. y = x->child[0];
  224. x->child[0] = y->child[1];
  225. y->child[1] = x;
  226. x->height = heightt(x);
  227. y->height = heightt(y);
  228. x->size = sizee(x);
  229. y->size = sizee(y);
  230. return(y);
  231. }
  232.  
  233. AVLNodePtr rotateleft(AVLNodePtr x)
  234. {
  235. AVLNodePtr y;
  236. y = x->child[1];
  237. x->child[1] = y->child[0];
  238. y->child[0] = x;
  239. x->height = heightt(x);
  240. y->height = heightt(y);
  241. x->size = sizee(x);
  242. y->size = sizee(y);
  243.  
  244. return(y);
  245. }
  246.  
  247.  
  248. AVLNodePtr RR(AVLNodePtr T)
  249. {
  250. T = rotateleft(T);
  251. return(T);
  252. }
  253.  
  254. AVLNodePtr LL(AVLNodePtr T)
  255. {
  256. T = rotateright(T);
  257. return(T);
  258. }
  259.  
  260. AVLNodePtr LR(AVLNodePtr T)
  261. {
  262. T->child[0] = rotateleft(T->child[0]);
  263. T = rotateright(T);
  264.  
  265. return(T);
  266. }
  267.  
  268. AVLNodePtr RL(AVLNodePtr T)
  269. {
  270. T->child[1] = rotateright(T->child[1]);
  271. T = rotateleft(T);
  272. return(T);
  273. }
  274.  
  275. int BF(AVLNodePtr T)
  276. {
  277. int lh, rh;
  278. if (T == NULL)
  279. return(0);
  280.  
  281. if (T->child[0] == NULL)
  282. lh = 0;
  283. else
  284. lh = 1 + T->child[0]->height;
  285.  
  286. if (T->child[1] == NULL)
  287. rh = 0;
  288. else
  289. rh = 1 + T->child[1]->height;
  290.  
  291. return(lh - rh);
  292. }
  293. // Queries
  294.  
  295.  
  296. int next_missing( AVLNodePtr tnode ){
  297. return 1; // Student code goes here. Feel free to remove this line.
  298. }
  299.  
  300. int avl_rank( AVLNodePtr tnode, int k ){
  301.  
  302. if (tnode == NULL)
  303. return NULL;
  304. else
  305. {
  306. AVLNodePtr result = avl_rank(tnode->child[1], k);
  307. if(result)
  308. k--;
  309. if (k == 0)
  310. return tnode->size;
  311. return avl_rank(tnode->child[0], k);
  312. }
  313. }
  314.  
  315. int sizer(AVLNodePtr node) {
  316. if (node == NULL)
  317. return 0;
  318. return node->size;
  319. }
  320.  
  321. /*AVLNodePtr Min(AVLNodePtr node)
  322. {
  323. if (node == NULL)
  324. return;
  325. else {
  326. AVLNodePtr current = node;
  327. while (current->child[0])
  328. {
  329.  
  330. }
  331. }
  332. }*/
  333.  
  334. AVLNodePtr avl_select( AVLNodePtr tnode, int k ){
  335. return NULL; // Student code goes here. Feel free to remove this line.
  336. }
  337.  
  338.  
  339. // Utilities
  340.  
  341.  
  342. // Tests
  343.  
  344. // (when you're ready, remove the comments and test your code)
  345.  
  346.  
  347. typedef enum {FAILED,PASSED} TestResult;
  348.  
  349. void avl_test();
  350. int avl_test_recurse( AVLNodePtr tnode, TestResult * res );
  351. void insert_delete_search_test();
  352. void rank_select_test();
  353. void next_missing_test();
  354.  
  355. void avl_test(){
  356. int i=1;
  357. TestResult res = PASSED;
  358. AVLNodePtr root = NULL;
  359. for( i=1; i<100000; ++i )
  360. root = avl_insert( root, i );
  361. avl_test_recurse( root, &res );
  362. if( res == FAILED )
  363. printf("AVL test failed.\n");
  364. else
  365. printf("AVL test passed.\n");
  366. delete_avl_tree( root );
  367. }
  368.  
  369. int avl_test_recurse( AVLNodePtr tnode, TestResult * res ){
  370. int h_left,h_right;
  371. if( !tnode )
  372. return -1;
  373. h_left = avl_test_recurse( tnode->child[LEFT], res );
  374. h_right = avl_test_recurse( tnode->child[RIGHT], res );
  375. *res = (ABS(h_left-h_right) > 1 ) ? FAILED:*res;
  376. return 1+MAX(h_left,h_right);
  377. }
  378.  
  379.  
  380. void insert_delete_search_test(){
  381. int i=1;
  382. AVLNodePtr node = NULL, root = NULL;
  383. TestResult res = PASSED;
  384. for( i=1; i<20; ++i )
  385. root = avl_insert( root, i );
  386. for( i=1; i<20; ++i ){
  387. if( !((node = avl_search( root, i )) && (node->key == i))){
  388. res = FAILED;
  389. break;
  390. }
  391. root = avl_delete( root, i );
  392. if( avl_search( root, i ) ){
  393. res = FAILED;
  394. break;
  395. }
  396.  
  397. }
  398. if( res == FAILED )
  399. printf("insert/delete/search test failed.\n");
  400. else
  401. printf("insert/delete/search test passed.\n");
  402. delete_avl_tree( root );
  403. }
  404.  
  405. void rank_select_test(){
  406. int i=11;
  407. AVLNodePtr node = NULL, root = NULL;
  408. TestResult res = PASSED;
  409. for( i=11; i<21; ++i )
  410. root = avl_insert( root, i );
  411. if( (avl_rank( root, 20 ) != 10) || \
  412. (avl_rank(root,11) != 1) || \
  413. (avl_rank(root, 15) != 5) )
  414. res = FAILED;
  415. if( res == FAILED )
  416. printf("rank/select test failed.\n");
  417. else
  418. printf("rank/select test passed.\n");
  419. delete_avl_tree( root );
  420. }
  421. /*
  422. void next_missing_test(){
  423. AVLNodePtr root = NULL;
  424. TestResult res = PASSED;
  425. root = avl_insert( root, 1 );
  426. res = (next_missing( root )==2)?res:FAILED;
  427. root = avl_insert( root, 3 );
  428. res = (next_missing( root )==2)?res:FAILED;
  429. root = avl_insert( root, 2 );
  430. res = (next_missing( root )==4)?res:FAILED;
  431. if( res == FAILED )
  432. printf("next_missing test failed.\n");
  433. else
  434. printf("next_missing test passed.\n");
  435. delete_avl_tree( root );
  436. }
  437. */
  438. int main(){
  439.  
  440. avl_test();
  441. insert_delete_search_test();
  442. rank_select_test();
  443. //next_missing_test();
  444.  
  445. printf("AVL: Hello World!\n");
  446. return 0;
  447. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement