fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node{
  5. 	int data;
  6. 	int height;
  7. 	Node *left;
  8. 	Node *right;
  9. };
  10.  
  11. class AVLTree{
  12. 	public:
  13. 	Node *root;
  14.  
  15. 	AVLTree(){
  16. 		root = NULL;
  17. 	}
  18.  
  19. 	Node *getNode(int &val){
  20. 		Node *newNode = new Node;
  21. 		newNode->data = val;
  22. 		newNode->height = 0;
  23. 		newNode->left = newNode->right = NULL;
  24.  
  25. 		return newNode;
  26. 	}
  27.  
  28. 	int nodeHeight(Node *nd){
  29. 		if(!nd)
  30. 			return -1;
  31.  
  32. 		return nd->height;
  33. 	}
  34.  
  35. 	int balanceFactor(Node *nd){
  36. 		if(!nd)
  37. 			return 0;
  38.  
  39. 		return nodeHeight(nd->left) - nodeHeight(nd->right); 
  40. 	}
  41.  
  42. 	void insertNode(int &val){
  43. 		if(!root){
  44. 			root = getNode(val);
  45. 			return;
  46. 		}
  47.  
  48. 		insertNodeHelper(root, NULL, val, false);
  49. 	}
  50.  
  51. 	void insertNodeHelper(Node *rt, Node *parent, int &val, bool isLeft){
  52. 		if(!rt){
  53. 			isLeft ? parent->left = getNode(val) : parent->right = getNode(val);
  54. 			return;
  55. 		}
  56.  
  57. 		if(val < rt->data)
  58. 			insertNodeHelper(rt->left, rt, val, true);
  59. 		else
  60. 			insertNodeHelper(rt->right, rt, val, false);
  61.  
  62. 		/*======================= Re-Balancing =========================*/	
  63. 		rt->height = 1 + max(nodeHeight(rt->left), nodeHeight(rt->right));
  64.  
  65. 		int balance_fact = balanceFactor(rt);
  66.  
  67. 		if(balance_fact > 1 && val < rt->left->data){//LL rotation
  68. 			rightRotate(rt, parent, isLeft);
  69. 		}
  70.  
  71. 		else if(balance_fact < -1 && val > rt->right->data){//RR rotation
  72. 			leftRotate(rt, parent, isLeft);
  73. 		}
  74.  
  75. 		else if(balance_fact < -1 && val < rt->right->data){//RL rotation
  76. 			rightRotate(rt->right, rt, false);
  77. 			leftRotate(rt, parent, isLeft);
  78. 		}
  79.  
  80. 		else if(balance_fact > 1 && val > rt->left->data){//LR rotation
  81. 			leftRotate(rt->left, rt, true);
  82. 			rightRotate(rt, parent, isLeft);
  83. 		}
  84. 		/*======================= Re-Balancing =========================*/
  85. 	}
  86.  
  87. 	void leftRotate(Node *rootedNode, Node *parent, bool isLeft){
  88. 		Node *rightNode = rootedNode->right;
  89. 		Node *rightNodechild = rightNode->left;
  90.  
  91. 		rightNode->left = rootedNode;
  92. 		rootedNode->right = rightNodechild;
  93.  
  94. 		rootedNode->height = 1 + max(nodeHeight(rootedNode->left),
  95. 									nodeHeight(rootedNode->right));
  96.  
  97. 		rightNode->height = 1 + max(nodeHeight(rightNode->left),
  98. 									nodeHeight(rightNode->right));
  99.  
  100. 		if(parent){
  101. 			isLeft ? parent->left = rightNode : parent->right = rightNode;
  102. 		}
  103. 		else{
  104. 			root = rightNode;
  105. 		}
  106. 	}
  107.  
  108. 	void rightRotate(Node *rootedNode, Node *parent, bool isLeft){
  109. 		Node *leftNode = rootedNode->left;
  110. 		Node *leftNodechild = leftNode->right;
  111.  
  112. 		leftNode->right = rootedNode;
  113. 		rootedNode->left = leftNodechild;
  114.  
  115. 		rootedNode->height = 1 + max(nodeHeight(rootedNode->left),
  116. 									nodeHeight(rootedNode->right));
  117.  
  118. 		leftNode->height = 1 + max(nodeHeight(leftNode->left),
  119. 									nodeHeight(leftNode->right));
  120.  
  121. 		if(parent){
  122. 			isLeft ? parent->left = leftNode : parent->right = leftNode;
  123. 		}
  124. 		else{
  125. 			root = leftNode;
  126. 		}
  127. 	}
  128.  
  129. 	bool deleteNode(int &val){
  130. 		Node *rt = root;
  131.  
  132. 		if(!rt)
  133. 			return false;
  134.  
  135. 		if(rt->data == val){
  136. 			if(!rt->left && !rt->right)
  137. 				root = NULL;
  138. 			else if(!rt->left)
  139. 				root = rt->right;
  140. 			else if(!rt->right)
  141. 				root = rt->left;
  142. 			else
  143. 				return deleteNodeHelper(rt, NULL, val, false);
  144.  
  145. 			delete rt;
  146. 			return true;
  147. 		}
  148.  
  149. 		return deleteNodeHelper(rt, NULL, val, false);
  150. 	}
  151.  
  152. 	bool deleteNodeHelper(Node *rt, Node *parent, int val, bool isLeft){
  153. 		if(!rt)
  154. 			return false;
  155.  
  156. 		if(rt->data == val){
  157.  
  158. 			if(!rt->left && !rt->right){
  159. 				isLeft ? parent->left = NULL : parent->right = NULL;
  160. 				delete rt;
  161. 			}
  162. 			else if(!rt->left){
  163. 				isLeft ? parent->left = rt->right : parent->right = rt->right;
  164. 				delete rt;
  165. 			}
  166. 			else if(!rt->right){
  167. 				isLeft ? parent->left = rt->left : parent->right = rt->left;
  168. 				delete rt;
  169. 			}
  170. 			else{
  171. 				Node *minNd = minNode(rt->right);
  172. 				rt->data = minNd->data;
  173. 				deleteNodeHelper(rt->right, rt, rt->data, false);
  174. 			}
  175.  
  176. 			return true;
  177. 		}
  178.  
  179. 		bool result=false;
  180.  
  181. 		if(val < rt->data){
  182. 			result = deleteNodeHelper(rt->left, rt, val, true);
  183. 		}
  184. 		else{
  185. 			result = deleteNodeHelper(rt->right, rt, val, false);
  186. 		}
  187.  
  188. 		/*======================= Re-Balancing =========================*/
  189. 		rt->height = 1 + max(nodeHeight(rt->left), nodeHeight(rt->right));
  190.  
  191. 		int balance_fact = balanceFactor(rt);
  192.  
  193. 		if(balance_fact > 1 && balanceFactor(rt->left) >= 0){//LL rotation
  194. 			rightRotate(rt, parent, isLeft);
  195. 		}
  196.  
  197. 		else if(balance_fact < -1 && balanceFactor(rt->right) <= 0){//RR rotation
  198. 			leftRotate(rt, parent, isLeft);
  199. 		}
  200.  
  201. 		else if(balance_fact < -1 && balanceFactor(rt->right) > 0){//RL rotation
  202. 			rightRotate(rt->right, rt, false);
  203. 			leftRotate(rt, parent, isLeft);
  204. 		}
  205.  
  206. 		else if(balance_fact > 1 && balanceFactor(rt->left) < 0){//LR rotation
  207. 			leftRotate(rt->left, rt, true);
  208. 			rightRotate(rt, parent, isLeft);
  209. 		}
  210. 		/*======================= Re-Balancing =========================*/
  211.  
  212. 		return result;
  213. 	}
  214.  
  215. 	void inOrder(Node *rt){
  216. 		if(!rt)
  217. 			return;
  218.  
  219. 		inOrder(rt->left);
  220. 		cout<<rt->data<<" ";
  221. 		inOrder(rt->right);
  222. 	}
  223.  
  224. 	void postOrder(Node *rt){
  225. 		if(!rt)
  226. 			return;
  227.  
  228. 		postOrder(rt->left);
  229. 		postOrder(rt->right);
  230. 		cout<<rt->data<<" ";
  231. 	}
  232.  
  233. 	void preOrder(Node *rt){
  234. 		if(!rt)
  235. 			return;
  236.  
  237. 		cout<<rt->data<<" ";
  238. 		preOrder(rt->left);
  239. 		preOrder(rt->right);
  240. 	}
  241.  
  242. 	Node *minNode(Node *rt){
  243. 		if(!rt->left){
  244. 			return rt;
  245. 		}
  246.  
  247. 		return minNode(rt->left);
  248. 	}
  249.  
  250. 	Node *maxNode(Node *rt){
  251. 		if(!rt->right){
  252. 			return rt;
  253. 		}
  254.  
  255. 		return maxNode(rt->right);
  256. 	}
  257.  
  258. 	void heightWiseTraversal(){
  259. 		if(!root){
  260. 			cout<<"The tree is empty!!\n";
  261. 			return;
  262. 		}
  263.  
  264. 		int count=0, hgt = root->height;
  265.  
  266. 		queue<Node*> qu;
  267. 		qu.push(root);
  268.  
  269. 		cout<<"The elements at the,\n";
  270.  
  271. 		while(!qu.empty()){
  272.  
  273. 			int n = qu.size();
  274.  
  275. 			cout<<"Height-"<<hgt--<<": ";
  276.  
  277. 			while(n--){
  278.  
  279. 				Node *temp = qu.front(); qu.pop();
  280.  
  281. 				cout<<temp->data<<" "; ++count;
  282.  
  283. 				if(temp->left){
  284. 					qu.push(temp->left);
  285. 				}
  286.  
  287. 				if(temp->right){
  288. 					qu.push(temp->right);
  289. 				}
  290. 			}
  291.  
  292. 			cout<<"\n";
  293. 		}
  294.  
  295. 		cout<<"Total # nodes in the tree are(n): "<<count<<"\n";
  296. 		cout<<"Height of the tree is: "<<floor(log2(count))<<" { = O(log2(n)) }\n";
  297. 	}
  298.  
  299. 	void searchNode(Node *rt, int &val){
  300. 		if(!root){
  301. 			cout<<"The tree is empty!!\n";
  302. 			return;
  303. 		}
  304.  
  305. 		if(!rt || rt->data == val){
  306. 			cout<<"Element "<<val<<(rt ? " ": " not ")<<"found for search.\n";
  307. 			return;
  308. 		}
  309.  
  310. 		if(val < rt->data)
  311. 			searchNode(rt->left, val);
  312. 		else
  313. 			searchNode(rt->right, val);
  314. 	}
  315. };
  316.  
  317. int main() {
  318. 	int opt, val;
  319.  
  320. 	AVLTree tree;
  321.  
  322. 	cout<<"Operations available on AVL tree are:\n";
  323. 	cout<<"1. Insert an element\n2. Search an element\n3. Delete an element\n"
  324. 	"4. Minimum element in tree\n5. Maximum element in tree\n"
  325. 	"6. InOrder traversal\n7. PreOrder traversal\n8. PostOrder traversal\n"
  326. 	"9. Height wise traversal\n10. Exit\n";
  327. 	cout<<"************************************************\n";
  328. 	while(true){
  329. 		cin>>opt;
  330. 		switch(opt){
  331. 			case 1:
  332. 				cin>>val;
  333. 				tree.insertNode(val);
  334. 				cout<<"Element "<<val<<" is inserted into the AVL tree.\n";
  335. 				break;
  336. 			case 2:
  337. 				cin>>val;
  338. 				tree.searchNode(tree.root, val);
  339. 				break;
  340. 			case 3:
  341. 				cin>>val;
  342. 				cout<<"Element "<<val<<(tree.deleteNode(val) ? " is deleted.\n": " not found for delete.\n");
  343. 				break;
  344. 			case 4:
  345. 				cout<<"The minimum element in the AVL tree is: "<<tree.minNode(tree.root)->data<<"\n";
  346. 				break;
  347. 			case 5:
  348. 				cout<<"The maximum element in the AVL tree is: "<<tree.maxNode(tree.root)->data<<"\n";
  349. 				break;
  350. 			case 6:
  351. 				cout<<"InOrder: ";
  352. 				tree.inOrder(tree.root); cout<<"\n";
  353. 				break;
  354. 			case 7:
  355. 				cout<<"PreOrder: ";
  356. 				tree.preOrder(tree.root); cout<<"\n";
  357. 				break;
  358. 			case 8:
  359. 				cout<<"PostOrder: ";
  360. 				tree.postOrder(tree.root); cout<<"\n";
  361. 				break;
  362. 			case 9:
  363. 				tree.heightWiseTraversal();
  364. 				break;
  365. 			case 10:
  366. 				exit(0);
  367. 		}
  368. 		cout<<"************************************************\n";
  369. 	}
  370. 	return 0;
  371. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
9
1 5
1 3
1 2
1 14
1 4
1 9
1 7
1 6
1 8
1 12
2 23
2 8
6 7 8 9
1 11
1 10
1 13
9
3 9
9
3 10
9
3 12
9
3 14
3 2
3 4
9
6 7 8 10
stdout
copy 
Operations available on AVL tree are:
1. Insert an element
2. Search an element
3. Delete an element
4. Minimum element in tree
5. Maximum element in tree
6. InOrder traversal
7. PreOrder traversal
8. PostOrder traversal
9. Height wise traversal
10. Exit
************************************************
The tree is empty!!
************************************************
Element 5 is inserted into the AVL tree.
************************************************
Element 3 is inserted into the AVL tree.
************************************************
Element 2 is inserted into the AVL tree.
************************************************
Element 14 is inserted into the AVL tree.
************************************************
Element 4 is inserted into the AVL tree.
************************************************
Element 9 is inserted into the AVL tree.
************************************************
Element 7 is inserted into the AVL tree.
************************************************
Element 6 is inserted into the AVL tree.
************************************************
Element 8 is inserted into the AVL tree.
************************************************
Element 12 is inserted into the AVL tree.
************************************************
Element 23 not found for search.
************************************************
Element 8 found for search.
************************************************
InOrder: 2 3 4 5 6 7 8 9 12 14 
************************************************
PreOrder: 5 3 2 4 9 7 6 8 14 12 
************************************************
PostOrder: 2 4 3 6 8 7 12 14 9 5 
************************************************
The elements at the,
Height-3: 5 
Height-2: 3 9 
Height-1: 2 4 7 14 
Height-0: 6 8 12 
Total # nodes in the tree are(n): 10
Height of the tree is: 3 { = O(log2(n)) }
************************************************
Element 11 is inserted into the AVL tree.
************************************************
Element 10 is inserted into the AVL tree.
************************************************
Element 13 is inserted into the AVL tree.
************************************************
The elements at the,
Height-3: 9 
Height-2: 5 12 
Height-1: 3 7 11 14 
Height-0: 2 4 6 8 10 13 
Total # nodes in the tree are(n): 13
Height of the tree is: 3 { = O(log2(n)) }
************************************************
Element 9 is deleted.
************************************************
The elements at the,
Height-3: 10 
Height-2: 5 12 
Height-1: 3 7 11 14 
Height-0: 2 4 6 8 13 
Total # nodes in the tree are(n): 12
Height of the tree is: 3 { = O(log2(n)) }
************************************************
Element 10 is deleted.
************************************************
The elements at the,
Height-3: 11 
Height-2: 5 13 
Height-1: 3 7 12 14 
Height-0: 2 4 6 8 
Total # nodes in the tree are(n): 11
Height of the tree is: 3 { = O(log2(n)) }
************************************************
Element 12 is deleted.
************************************************
The elements at the,
Height-3: 11 
Height-2: 5 13 
Height-1: 3 7 14 
Height-0: 2 4 6 8 
Total # nodes in the tree are(n): 10
Height of the tree is: 3 { = O(log2(n)) }
************************************************
Element 14 is deleted.
************************************************
Element 2 is deleted.
************************************************
Element 4 is deleted.
************************************************
The elements at the,
Height-2: 7 
Height-1: 5 11 
Height-0: 3 6 8 13 
Total # nodes in the tree are(n): 7
Height of the tree is: 2 { = O(log2(n)) }
************************************************
InOrder: 3 5 6 7 8 11 13 
************************************************
PreOrder: 7 5 3 6 11 8 13 
************************************************
PostOrder: 3 6 5 8 13 11 7 
************************************************
https://ideone.com/gnRXTc
AVL Tree with insert, delete || Time complexity: O(log n)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!