fork(1) download
  1.  
  2. Avl.h
  3.  
  4. //-------------------------------------------------------------------------------------------------------------
  5. //-------------------------------------------------------------------------------------------------------------
  6. class cUser; // Add a class to store
  7.  
  8. typedef cUser* element;
  9.  
  10. struct AVL_Node
  11. {
  12. int key;
  13. element data;
  14. AVL_Node *parent,
  15. *left,
  16. *right;
  17.  
  18. AVL_Node()
  19. {
  20. left = right = parent = NULL;
  21. }
  22.  
  23. char factor; //byte
  24. };
  25. //-------------------------------------------------------------------------------------------------------------
  26. //------------------------------------------------------------------------------------------------------------- s
  27. class AVL_Tree
  28. {
  29. public:
  30. AVL_Tree();
  31. void insert(int key);
  32. void erase(int key);
  33. element find(int key);
  34. void dfs();
  35. int size;
  36. inline int height(AVL_Node * pos) const;
  37. AVL_Node *root;
  38.  
  39. private:
  40. protected:
  41. AVL_Node *tmp;
  42. AVL_Node *K1, *K2, *K3, *newnode;
  43. cUser * tmpdata;
  44. bool h;
  45.  
  46. inline int max(int a, int b) const;
  47.  
  48. AVL_Node * singleRotateLeft(AVL_Node *K2);
  49. AVL_Node * singleRotateRight(AVL_Node *K2);
  50.  
  51. AVL_Node * doubleRotateLeft(AVL_Node *K2);
  52. AVL_Node * doubleRotateRight(AVL_Node *K2);
  53.  
  54. AVL_Node * _insert(int key, AVL_Node * node);
  55. AVL_Node * _erase(int key, AVL_Node * node);
  56. void _dfs(AVL_Node * v) const;
  57. };
  58.  
  59. Avl.cpp
  60.  
  61. #include <cstdio>
  62. #include <iostream>
  63. #include "Avl.h"
  64. //-------------------------------------------------------------------------------------------------------------
  65. //-------------------------------------------------------------------------------------------------------------
  66. AVL_Tree::AVL_Tree()
  67. {
  68. size=0;
  69.  
  70. root=NULL;
  71. }
  72. //-------------------------------------------------------------------------------------------------------------
  73. //-------------------------------------------------------------------------------------------------------------
  74. element AVL_Tree::find(int key)
  75. {
  76. if(size==0)
  77. return NULL;
  78. tmp=root;
  79. while(tmp!=NULL)
  80. {
  81. if(key<tmp->key)
  82. tmp=tmp->left;
  83. else if(key>tmp->key)
  84. tmp=tmp->right;
  85. else
  86. return tmp->data;
  87. }
  88. return NULL;
  89. }
  90. //-------------------------------------------------------------------------------------------------------------
  91. //-------------------------------------------------------------------------------------------------------------
  92. inline int AVL_Tree::height( AVL_Node * pos ) const
  93. {
  94. if( pos == NULL )
  95. return -1;
  96. else
  97. return pos->factor;
  98. }
  99. //-------------------------------------------------------------------------------------------------------------
  100. //-------------------------------------------------------------------------------------------------------------
  101. inline int AVL_Tree::max( int a, int b ) const
  102. {
  103. return a > b ? a : b;
  104. }
  105. //-------------------------------------------------------------------------------------------------------------
  106. //-------------------------------------------------------------------------------------------------------------
  107. AVL_Node * AVL_Tree::singleRotateLeft(AVL_Node *K2)
  108. {
  109. K1 = K2->left;
  110. K2->left = K1->right;
  111. K1->right = K2;
  112.  
  113. K2->factor = max(height(K2->left), height(K2->right))+1;
  114. K1->factor = max(height(K1->left), K2->factor)+1;
  115.  
  116.  
  117. return K1; // new root
  118. }
  119. //-------------------------------------------------------------------------------------------------------------
  120. //-------------------------------------------------------------------------------------------------------------
  121. AVL_Node * AVL_Tree::singleRotateRight(AVL_Node *K1)
  122. {
  123. K2 = K1->right;
  124. K1->right = K2->left;
  125. K2->left = K1;
  126.  
  127. K1->factor = max(height(K1->left), height(K1->right))+1;
  128. K2->factor = max(height(K2->right), K1->factor)+1;
  129.  
  130.  
  131. return K2; // new root
  132. }
  133. //-------------------------------------------------------------------------------------------------------------
  134. //-------------------------------------------------------------------------------------------------------------
  135. AVL_Node * AVL_Tree::doubleRotateLeft(AVL_Node *K3)
  136. {
  137. K3->left = singleRotateRight(K3->left);
  138.  
  139. return singleRotateLeft(K3);
  140. }
  141. //-------------------------------------------------------------------------------------------------------------
  142. //-------------------------------------------------------------------------------------------------------------
  143. AVL_Node * AVL_Tree::doubleRotateRight(AVL_Node *K1)
  144. {
  145. K1->right = singleRotateLeft(K1->right);
  146.  
  147. return singleRotateRight(K1);
  148. }
  149. //-------------------------------------------------------------------------------------------------------------
  150. //-------------------------------------------------------------------------------------------------------------
  151. void AVL_Tree::insert(int key)
  152. {
  153. size++;
  154. root=_insert(key,root);
  155. }
  156. //-------------------------------------------------------------------------------------------------------------
  157. //-------------------------------------------------------------------------------------------------------------
  158. AVL_Node * AVL_Tree::_insert(int key, AVL_Node * node)
  159. {
  160. if (node==NULL)
  161. {
  162. node = new AVL_Node;
  163. node->factor=0;
  164. node->key=key;
  165. node->data=tmpdata;
  166. node->left=NULL;
  167. node->right=NULL;
  168. }
  169. else if(key < node->key)
  170. {
  171. node->left= _insert(key,node->left);
  172. if(height(node->left) - height(node->right) == 2)
  173. {
  174. if(key < node->left->key)
  175. node = singleRotateLeft(node);
  176. else
  177. node = doubleRotateLeft(node);
  178. }
  179. }
  180. else if(key > node->key)
  181. {
  182. node->right= _insert(key,node->right);
  183. if(height(node->right) - height(node->left) == 2)
  184. {
  185. if(key > node->right->key)
  186. node = singleRotateRight(node);
  187. else
  188. node = doubleRotateRight(node);
  189. }
  190. }
  191. node->factor = max(height(node->left ),height(node->right))+1;
  192. return node;
  193.  
  194. }
  195. //-------------------------------------------------------------------------------------------------------------
  196. //-------------------------------------------------------------------------------------------------------------
  197. void AVL_Tree::erase(int key)
  198. {
  199. root=_erase(key,root);
  200. }
  201. //-------------------------------------------------------------------------------------------------------------
  202. //-------------------------------------------------------------------------------------------------------------
  203. AVL_Node * AVL_Tree::_erase(int key, AVL_Node * node)
  204. {
  205. bool done=false;
  206. if (node==NULL)
  207. {
  208. h=false;
  209. done=true;
  210. }
  211. else
  212. if (key < node->key) //delee from left subtree
  213. {
  214. newnode=_erase(key,node->left);
  215. node->left=newnode;
  216. if(h)
  217. {
  218. if(height(node->right) - height(node->left) == 2)
  219. {
  220. if(height(node->right) > height(node->left))
  221. node = singleRotateLeft(node);
  222. else
  223. node = singleRotateRight(node);
  224. }
  225.  
  226. node->factor = max(height(node->left ),height(node->right))+1;
  227.  
  228.  
  229. // if (node->factor >= 0)
  230. // {
  231. // node->factor=root->factor-1;
  232. // if (node->factor==-1)
  233. // h=false;
  234. // }
  235. // else if (node->right->factor==-1)
  236. // singleRotateRight(node);
  237. // else
  238. // singleRotateLeft(node);
  239.  
  240. done=true;
  241. return node;
  242. }
  243.  
  244.  
  245. }
  246. else if (key == node->key) //del node
  247. {
  248. if (node->left==NULL || node->right==NULL) // one or no children
  249. {
  250. if (node->left == NULL)
  251. K1=node->right;
  252. else
  253. K1=node->left;
  254.  
  255. delete node;
  256.  
  257. h=true; done=true;
  258.  
  259. return(K1);
  260.  
  261. }
  262. else // both of children
  263. {
  264. K2=node->right;
  265. while (K2->left != NULL)
  266. K2=K2->left;
  267.  
  268. node->key=K2->key;
  269. key=node->key;
  270. }
  271. }
  272.  
  273. if (!done && key >= node->key) // delete from right subtree
  274. {
  275. newnode=_erase(key, node->right);
  276. node->right=newnode;
  277. if (h)
  278. {
  279. if(height(node->right) - height(node->left) == 2)
  280. {
  281. if(height(node->right) > height(node->left))
  282. node = singleRotateLeft(node);
  283. else
  284. node = singleRotateRight(node);
  285. }
  286. node->factor = max(height(node->left ),height(node->right))+1;
  287. //
  288. /* if (node->factor <= 0)
  289.   {
  290.   node->factor=node->factor+1;
  291.   if (node->factor ==1)
  292.   h=false;
  293.   }
  294.   else if (node->right->factor==1)
  295.   singleRotateLeft(node);
  296.   else
  297.   singleRotateRight(node);*/
  298. return node;
  299. }
  300. }
  301.  
  302.  
  303. }
  304. //-------------------------------------------------------------------------------------------------------------
  305. //-------------------------------------------------------------------------------------------------------------
  306. void AVL_Tree::dfs()
  307. {
  308. _dfs(root);
  309. }
  310. //-------------------------------------------------------------------------------------------------------------
  311. //-------------------------------------------------------------------------------------------------------------
  312. void AVL_Tree::_dfs(AVL_Node * v) const
  313. {
  314.  
  315.  
  316. if(v->left!=NULL)
  317. _dfs(v->left);
  318.  
  319. std::cout << v->key << std::endl;
  320. if(v->right!=NULL)
  321. _dfs(v->right);
  322. }
  323. //-------------------------------------------------------------------------------------------------------------
  324. //---------------------------------
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout

Standard output is empty