Advertisement
Guest User

Untitled

a guest
Dec 20th, 2014
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // AiSD34
  4. //
  5. // Created by Andrey Bondar on 19.12.14.
  6. // Copyright (c) 2014 Andrey Bondar. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10.  
  11. using namespace std;
  12.  
  13. struct node // структура для представления узлов дерева
  14. {
  15. int key;
  16. unsigned char height;
  17. node* left;
  18. node* right;
  19. node(int k) { key = k; left = right = 0; height = 1; }
  20. };
  21.  
  22. unsigned int height(node* r)
  23. {
  24. return r ? r->height:0;
  25. }
  26.  
  27. int bfactor(node* r)
  28. {
  29. return height(r->right)-height(r->left);
  30. }
  31.  
  32. void fixheight(node* r)
  33. {
  34. unsigned int hl = height(r->left);
  35. unsigned int hr = height(r->right);
  36. r->height = (hl>hr?hl:hr)+1;
  37. }
  38.  
  39. class AVLtree {
  40. public:
  41.  
  42. void insert(int k) {
  43. root = insert_real(root, k);
  44. }
  45.  
  46. void remove(int k) {
  47. root = delete_elem(root, k);
  48. }
  49.  
  50. AVLtree();
  51.  
  52. node *root;
  53.  
  54. void deleteNode(node*& r) {
  55. if( r->left != 0 ) {
  56. deleteNode(r->left);
  57. }
  58. if( r->right != 0 ) {
  59. deleteNode(r->right);
  60. }
  61. delete r;
  62. }
  63.  
  64. ~AVLtree() {
  65. if( root != 0 ) {
  66. deleteNode(root);
  67. }
  68. }
  69.  
  70.  
  71. private:
  72.  
  73. node* rightRot(node *r);
  74. node* leftRot(node *r);
  75. node* balance(node *r);
  76. node* insert_real(node *r, int k);
  77. node* find_min(node *r);
  78. node* del_min(node *r);
  79. node* delete_elem(node *r, int k);
  80.  
  81.  
  82. };
  83.  
  84. AVLtree::AVLtree() : root(0) {}
  85.  
  86. node* AVLtree::rightRot(node *r) {
  87. node *newRoot = r->left;
  88. r->left = newRoot->right;
  89. newRoot->right = r;
  90. fixheight(r);
  91. fixheight(newRoot);
  92. return newRoot;
  93. }
  94.  
  95. node* AVLtree::leftRot(node *r) {
  96. node *newRoot = r->right;
  97. r->right = newRoot->left;
  98. newRoot->left = r;
  99. fixheight(r);
  100. fixheight(newRoot);
  101. return newRoot;
  102. }
  103.  
  104. node* AVLtree::balance(node *r)
  105. {
  106. fixheight(r);
  107. if( bfactor(r) == 2 ) {
  108. if (bfactor(r->right) < 0)
  109. {
  110. r->right = rightRot(r->right);
  111. }
  112. return leftRot(r);
  113. }
  114.  
  115. if( bfactor(r) == -2) {
  116. if( bfactor(r->left) > 0)
  117. {
  118. r->left = leftRot(r->left);
  119. }
  120. return rightRot(r);
  121. }
  122.  
  123. return r;
  124. }
  125.  
  126. node* AVLtree::insert_real(node *r, int k)
  127. {
  128. if (!r) return new node(k);
  129. if (k < r->key)
  130. {
  131. r->left = insert_real(r->left, k);
  132. }
  133. else {
  134. r->right = insert_real(r->right, k);
  135. }
  136. return balance(r);
  137. }
  138.  
  139. node* AVLtree::find_min(node *r) {
  140. return r->left ? find_min(r->left) : r;
  141. }
  142.  
  143. node* AVLtree::del_min(node *r) {
  144. if (r->left == 0) {
  145. return r->right;
  146. }
  147. r->left = del_min(r->left);
  148. return balance(r);
  149. }
  150.  
  151. node* AVLtree::delete_elem(node *r, int k) {
  152. if( !r ) return 0;
  153. if( k < r->key )
  154. r->left = delete_elem(r->left,k);
  155. else if( k > r->key )
  156. {
  157. r->right = delete_elem(r->right,k);
  158. }
  159. else
  160. {
  161. node* left = r->left;
  162. node* right = r->right;
  163. delete r;
  164. if( !right ) return left;
  165. node* min = find_min(right);
  166. min->right = del_min(right);
  167. min->left = left;
  168. return balance(min);
  169. }
  170. return balance(r);
  171. }
  172.  
  173. int main(int argc, const char * argv[]) {
  174. int input = 0;
  175. AVLtree* tree = new AVLtree();
  176. while (cin >> input) {
  177. if (input > 0) {
  178. tree->insert(input);
  179. }
  180. else{
  181. tree->remove(-input);
  182. }
  183. }
  184. cout << height(tree->root);
  185. delete tree;
  186. return 0;
  187. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement