fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. #ifndef AVL_TREE_HPP
  6. #define AVL_TREE_HPP
  7.  
  8. #include <algorithm>
  9. #include <iostream>
  10. #include <string>
  11. #include <sstream>
  12.  
  13. using namespace std;
  14.  
  15. template <class T>
  16. struct AVLNode {
  17.     T data;
  18.     int height = 0;
  19.     AVLNode<T>* left = nullptr, * right = nullptr, * parent = nullptr;
  20.  
  21.     AVLNode(T t) : data(t) {}
  22.     AVLNode(T t, AVLNode<T>* p) : data(t), parent(p) {}
  23. };
  24.  
  25. template <class T> class AVLTree {
  26. public:
  27.  
  28. AVLNode<T>* root = nullptr;
  29.  
  30. void insert(AVLNode<T>*, T);
  31. int update_height(AVLNode<T>*);
  32. int check_balance(AVLNode<T>*);
  33. AVLNode<T>* left_rotate(AVLNode<T>*);
  34. AVLNode<T>* right_rotate(AVLNode<T>*);
  35. void double_left_rotate(AVLNode<T>*);
  36. void double_right_rotate(AVLNode<T>*);
  37. void serialize(AVLNode<T>*, std::stringstream&);
  38. void clear();
  39. void remove(int);
  40. void insert(T);
  41. std::string serialize(); // helper that calls a recursive
  42.  
  43. public:
  44. AVLTree() {}
  45. ~AVLTree() {}
  46.  
  47. private:
  48. AVLNode<T>* removeUtil(AVLNode<T>* ,int);
  49. AVLNode<T>* maxValueNode(AVLNode<T>* node);
  50. void clearUtil(AVLNode<T>* n);
  51.  
  52. };
  53.  
  54. template <class T>
  55. void AVLTree<T>::remove(int key) {
  56.  
  57. root=removeUtil(root,key);
  58.  
  59. return;
  60. }
  61.  
  62. template <class T>
  63. AVLNode<T>* AVLTree<T>::maxValueNode(AVLNode<T>* node)
  64. {
  65.     AVLNode<T>* current = node;
  66.  
  67.     /* loop down to find the leftmost leaf */
  68.     while (current->right != NULL)
  69.         current = current->right;
  70.  
  71.     return current;
  72. }
  73.  
  74.  
  75.  
  76. template <class T>
  77. AVLNode<T>* AVLTree<T>::removeUtil(AVLNode<T>* root,int key){
  78.  
  79.  
  80.  if (root == NULL)
  81.         return root;
  82.  
  83.     // If the key to be deleted is smaller than the
  84.     // root's key, then it lies in left subtree
  85.     if ( key < root->data )
  86.         root->left= removeUtil(root->left, key);
  87.     // If the key to be deleted is greater than the
  88.     // root's key, then it lies in right subtree
  89.     else if( key > root->data )
  90.         root->right= removeUtil(root->right, key);
  91.  
  92.     // if key is same as root's key, then This is
  93.     // the node to be deleted
  94.     else
  95.     {
  96.         // node with only one child or no child
  97.         if( (root->left == NULL) || (root->right == NULL) )
  98.         {
  99.             AVLNode<T>* temp = root->left ? root->left :
  100.                                              root->right;
  101.  
  102.             // No child case
  103.             if (temp == NULL)
  104.             {
  105.                 temp = root;
  106.                 root = NULL;
  107.  
  108. 				return NULL;
  109.             }
  110.  
  111.             else // One child case
  112.              *root = *temp; // Copy the contents of
  113.                             // the non-empty child
  114.  
  115.             delete temp;
  116.         }
  117.         else
  118.         {
  119.             // node with two children: Get the inorder
  120.             // successor (smallest in the right subtree)
  121.             AVLNode<T> *temp = maxValueNode(root->left);
  122.             // Copy the inorder successor's data to this node
  123.             root->data = temp->data;
  124.  
  125.             // Delete the inorder successor
  126.             root->left = removeUtil(root->left, temp->data);
  127.  
  128.         }
  129.     }
  130.  
  131.     // If the tree had only one node then return
  132.     if (root == NULL)
  133.       return root;
  134.  
  135.  
  136.     // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
  137.  
  138.     root->height = 1 + std::max(update_height(root->left),
  139.                            update_height(root->right));
  140.  
  141.     // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
  142.     // check whether this node became unbalanced)
  143.     int balance = check_balance(root);
  144.  
  145.     // If this node becomes unbalanced, then there are 4 cases
  146.  
  147.     // Left Left Case
  148.     if (balance > 1 && check_balance(root->left) >= 0)
  149.         return right_rotate(root);
  150.  
  151.     // Left Right Case
  152.     if (balance > 1 && check_balance(root->left) < 0)
  153.     {
  154.         root->left =  left_rotate(root->left);
  155.         return right_rotate(root);
  156.     }
  157.  
  158.     // Right Right Case
  159.     if (balance < -1 && check_balance(root->right) <= 0)
  160.         return left_rotate(root);
  161.  
  162.     // Right Left Case
  163.     if (balance < -1 && check_balance(root->right) > 0)
  164.     {
  165.         root->right = right_rotate(root->right);
  166.         return left_rotate(root);
  167.     }
  168.  
  169.     return root;
  170. }
  171.  
  172.  
  173. template <class T>
  174. void AVLTree<T>::clear() {
  175.  
  176. while(root!=NULL){
  177. clearUtil(root);
  178. }
  179.  
  180. }
  181.  
  182. template <class T>
  183. void AVLTree<T>::clearUtil(AVLNode<T>* n) {
  184.  
  185.  
  186.     if (n!= NULL)
  187. 	{
  188.  
  189. 		clearUtil(n->left);
  190. 		clearUtil(n->right);
  191.         remove(n->data);
  192.  
  193. 	}
  194. return;
  195. }
  196.  
  197.  
  198. template <class T>
  199. int AVLTree<T>::update_height(AVLNode<T>* n) {
  200. if (!n)
  201. return 0;
  202.  
  203. n->height = 1 + std::max(n->left ? n->left->height : -1, n->right ? n->right->height : -1);
  204. return n->height;
  205. }
  206.  
  207. template <class T>
  208. int AVLTree<T>::check_balance(AVLNode<T>* n) {
  209. return (n->left ? n->left->height : -1) - (n->right ? n->right->height : -1);
  210. }
  211.  
  212. template <class T>
  213. AVLNode<T>* AVLTree<T>::left_rotate(AVLNode<T>* n) {
  214. AVLNode<T>* p = n;
  215. AVLNode<T>* m = n->right;
  216. p->right = m->left;
  217.  
  218. if (m->left)
  219. m->left->parent = p;
  220.  
  221. m->parent = n->parent;
  222.  
  223. m->left = p;
  224. p->parent = m;
  225.  
  226. if (!m->parent)
  227. root = m;
  228. else
  229. m->data < m->parent->data ? m->parent->left = m : m->parent->right = m;
  230.  
  231. update_height(p);
  232. update_height(m);
  233.  
  234. return m;
  235. }
  236.  
  237. template <class T>
  238. AVLNode<T>* AVLTree<T>::right_rotate(AVLNode<T>* n) {
  239. AVLNode<T>* p = n;
  240. AVLNode<T>* m = n->left;
  241. p->left = m->right;
  242. if (m->right)
  243. m->right->parent = p;
  244.  
  245. m->parent = n->parent;
  246.  
  247. m->right = p;
  248. p->parent = m;
  249.  
  250. if (!m->parent)
  251.     root = m;
  252. else
  253.     m->data < m->parent->data ? m->parent->left = m : m->parent->right = m;
  254.  
  255.     update_height(p);
  256.     update_height(m);
  257.  
  258.     return m;
  259. }
  260.  
  261. template <class T>
  262. void AVLTree<T>::double_left_rotate(AVLNode<T>* n) {
  263. right_rotate(n->right);
  264. left_rotate(n);
  265. }
  266.  
  267. template <class T>
  268. void AVLTree<T>::double_right_rotate(AVLNode<T>* n) {
  269. left_rotate(n->left);
  270. right_rotate(n);
  271. }
  272.  
  273. template <class T>
  274. void AVLTree<T>::insert(T t) {
  275. if (!root) {
  276. root = new AVLNode<T>(t);
  277. return;
  278. }
  279. insert(root, t); // recursive function call
  280. }
  281.  
  282. template <class T>
  283. void AVLTree<T>::insert(AVLNode<T>* n, T t) {
  284. if (n->data == t)
  285. return;
  286.  
  287. if (n->data > t) {
  288. if (n->left) {
  289. insert(n->left, t);
  290. } else {
  291. n->left = new AVLNode<T>(t, n);
  292. }
  293. } else {
  294. if (n->right) {
  295. insert(n->right, t);
  296. } else {
  297. n->right = new AVLNode<T>(t, n);
  298. }
  299. }
  300. update_height(n);
  301. int bf = check_balance(n);
  302. if (bf < -1) {
  303. if (check_balance(n->right) > 0) {
  304. double_left_rotate(n);
  305. } else {
  306. left_rotate(n);
  307. }
  308. } else if (bf > 1) {
  309. if (check_balance(n->left) < 0) {
  310. double_right_rotate(n);
  311. } else {
  312. right_rotate(n);
  313. }
  314. }
  315. }
  316.  
  317.  
  318. template <class T>
  319. std::string AVLTree<T>::serialize() {
  320. std::stringstream ret;
  321. serialize(root, ret);
  322. return ret.str();
  323. }
  324.  
  325. template <class T>
  326. void AVLTree<T>::serialize(AVLNode<T>* n, std::stringstream& s) {
  327. if (!n) {
  328. s << "[/]";
  329. return;
  330. }
  331.  
  332. s << "[" << n->data << "]";
  333. serialize(n->left, s);
  334. serialize(n->right, s);
  335. }
  336. #endif
  337.  
  338. using namespace std;
  339.  
  340. int main() {
  341.  
  342.   AVLTree<int> avl;
  343.  
  344.   std::cout << "----------------------------------------------------" << std::endl;
  345.   for (auto x : { 1, 2, 3, 4, 5, 6, 7 })
  346.     {
  347.     avl.insert(x);
  348.     }
  349.  
  350.   std::cout << avl.serialize() << std::endl;
  351.   std::cout << "----------------------------------------------------\n" << std::endl;
  352.  
  353.   avl.clear();
  354.  
  355.   std::cout << "----------------------------------------------------" << std::endl;
  356.   for (auto x : { 30, 10, 50, 48, 20 })
  357.     {
  358.         avl.insert(x);
  359.     }
  360.  
  361.   std::cout << avl.serialize() << std::endl;
  362.   std::cout << "----------------------------------------------------\n" << std::endl;
  363.  
  364.   avl.clear();
  365.  
  366.   std::cout << "----------------------------------------------------" << std::endl;
  367.   for (auto x : { 1, 2, 3, 4, 5, 6, 7 })
  368.     avl.insert(x);
  369.  
  370.   for (auto x : { 4, 3 })
  371.     avl.remove(x);
  372.  
  373.   std::cout << avl.serialize() << std::endl;
  374.   std::cout << "----------------------------------------------------\n" << std::endl;
  375.  
  376.   avl.clear();
  377.  
  378.   std::cout << "----------------------------------------------------" << std::endl;
  379.     for (auto x : { 10, 5, 15, 9, 8, 7, 6 })
  380.     {
  381.         avl.insert(x);
  382.     }
  383.  
  384.     for (auto x : { 10, 9 })
  385.     {
  386.         avl.remove(x);
  387.     }
  388.  
  389.     for (auto x : { 30, 10, 11, 12 })
  390.     {
  391.         avl.insert(x);
  392.     }
  393.  
  394.  
  395.   std::cout << avl.serialize() << std::endl;
  396.   std::cout << "----------------------------------------------------\n" << std::endl;
  397.  
  398.   avl.clear();
  399.  
  400.  
  401. }
Running #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/jwLuwP
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
7 years ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!