Implementation of AVL Tree in C<\/h3>\n#include <stdio.h>\r\n#include <stdlib.h>\r\n\r\nstruct Node \r\n{\r\n int Val;\r\n struct Node *left;\r\n struct Node *right;\r\n int height;\r\n};\r\n\r\nint max(int a, int b);\r\n\r\nint height(struct Node *N) \r\n{\r\n if (N == NULL)\r\n return 0;\r\n return N->height;\r\n}\r\n\r\nint max(int a, int b) \r\n{\r\n return (a > b) ? a : b;\r\n}\r\n\r\nstruct Node *newNode(int Val) \r\n{\r\n struct Node *node = (struct Node *)\r\n malloc(sizeof(struct Node));\r\n node->Val = Val;\r\n node->left = NULL;\r\n node->right = NULL;\r\n node->height = 1;\r\n return (node);\r\n}\r\n\r\nstruct Node *RotateRight(struct Node *y) \r\n{\r\n struct Node *x = y->left;\r\n struct Node *TEMP2 = x->right;\r\n\r\n x->right = y;\r\n y->left = TEMP2;\r\n\r\n y->height = max(height(y->left), height(y->right)) + 1;\r\n x->height = max(height(x->left), height(x->right)) + 1;\r\n\r\n return x;\r\n}\r\n\r\nstruct Node *RotateLeft(struct Node *x) \r\n{\r\n struct Node *y = x->right;\r\n struct Node *TEMP2 = y->left;\r\n\r\n y->left = x;\r\n x->right = TEMP2;\r\n\r\n x->height = max(height(x->left), height(x->right)) + 1;\r\n y->height = max(height(y->left), height(y->right)) + 1;\r\n\r\n return y;\r\n}\r\n\r\nint getBalance(struct Node *N) \r\n{\r\n if (N == NULL)\r\n return 0;\r\n return height(N->left) - height(N->right);\r\n}\r\n\r\nstruct Node *insertNode(struct Node *node, int Val) \r\n{\r\n \r\n if (node == NULL)\r\n return (newNode(Val));\r\n\r\n if (Val < node->Val)\r\n node->left = insertNode(node->left, Val);\r\n else if (Val > node->Val)\r\n node->right = insertNode(node->right, Val);\r\n else\r\n return node;\r\n\r\n node->height = 1 + max(height(node->left),height(node->right));\r\n\r\n int balance = getBalance(node);\r\n if (balance > 1 && Val < node->left->Val)\r\n return RotateRight(node);\r\n\r\n if (balance < -1 && Val > node->right->Val)\r\n return RotateLeft(node);\r\n\r\n if (balance > 1 && Val > node->left->Val) \r\n {\r\n node->left = RotateLeft(node->left);\r\n return RotateRight(node);\r\n }\r\n\r\n if (balance < -1 && Val < node->right->Val) \r\n {\r\n node->right = RotateRight(node->right);\r\n return RotateLeft(node);\r\n }\r\n\r\n return node;\r\n}\r\n\r\nstruct Node *minValueNode(struct Node *node) \r\n{\r\n struct Node *current = node;\r\n\r\n while (current->left != NULL)\r\n current = current->left;\r\n\r\n return current;\r\n}\r\n\r\nstruct Node *deleteNode(struct Node *root, int Val) \r\n{\r\n if (root == NULL)\r\n return root;\r\n\r\n if (Val < root->Val)\r\n root->left = deleteNode(root->left, Val);\r\n\r\n else if (Val > root->Val)\r\n root->right = deleteNode(root->right, Val);\r\n\r\n else \r\n {\r\n if ((root->left == NULL) || (root->right == NULL)) \r\n {\r\n struct Node *temp = root->left ? root->left : root->right;\r\n\r\n if (temp == NULL)\r\n {\r\n temp = root;\r\n root = NULL;\r\n } \r\n else\r\n *root = *temp;\r\n free(temp);\r\n } \r\n else \r\n {\r\n struct Node *temp = minValueNode(root->right);\r\n\r\n root->Val = temp->Val;\r\n\r\n root->right = deleteNode(root->right, temp->Val);\r\n }\r\n }\r\n\r\n if (root == NULL)\r\n return root;\r\n\r\n root->height = 1 + max(height(root->left),height(root->right));\r\n\r\n int balance = getBalance(root);\r\n if (balance > 1 && getBalance(root->left) >= 0)\r\n return RotateRight(root);\r\n\r\n if (balance > 1 && getBalance(root->left) < 0) \r\n {\r\n root->left = RotateLeft(root->left);\r\n return RotateRight(root);\r\n }\r\n\r\n if (balance < -1 && getBalance(root->right) <= 0)\r\n return RotateLeft(root);\r\n\r\n if (balance < -1 && getBalance(root->right) > 0) \r\n {\r\n root->right = RotateRight(root->right);\r\n return RotateLeft(root);\r\n }\r\n\r\n return root;\r\n}\r\n\r\nvoid printPreOrder(struct Node *root) \r\n{\r\n if (root != NULL) \r\n {\r\n printf(\"%d \", root->Val);\r\n printPreOrder(root->left);\r\n printPreOrder(root->right);\r\n }\r\n}\r\n\r\nint main() \r\n{\r\n struct Node *root = NULL;\r\n\r\n root = insertNode(root, 56);\r\n root = insertNode(root, 14);\r\n root = insertNode(root, 86);\r\n root = insertNode(root, 25);\r\n root = insertNode(root, 38);\r\n root = insertNode(root, 69);\r\n root = insertNode(root, 89);\r\n\r\n printPreOrder(root);\r\n\r\n root = deleteNode(root, 14);\r\n\r\n printf(\"AVL after deletion: \");\r\n printPreOrder(root);\r\n\r\n return 0;\r\n}\r\n<\/pre>\nAVL Tree implementation in C++<\/h3>\n#include <iostream>\r\nusing namespace std;\r\n\r\nstruct Node \r\n{\r\n int Val;\r\n struct Node *left;\r\n struct Node *right;\r\n int height;\r\n};\r\n\r\nint max(int a, int b);\r\n\r\nint height(struct Node *N) \r\n{\r\n if (N == NULL)\r\n return 0;\r\n return N->height;\r\n}\r\n\r\nint max(int a, int b) \r\n{\r\n return (a > b) ? a : b;\r\n}\r\n\r\nstruct Node *newNode(int Val) \r\n{\r\n struct Node *node = (struct Node *)\r\n malloc(sizeof(struct Node));\r\n node->Val = Val;\r\n node->left = NULL;\r\n node->right = NULL;\r\n node->height = 1;\r\n return (node);\r\n}\r\n\r\nstruct Node *RotateRight(struct Node *y) \r\n{\r\n struct Node *x = y->left;\r\n struct Node *TEMP2 = x->right;\r\n\r\n x->right = y;\r\n y->left = TEMP2;\r\n\r\n y->height = max(height(y->left), height(y->right)) + 1;\r\n x->height = max(height(x->left), height(x->right)) + 1;\r\n\r\n return x;\r\n}\r\n\r\nstruct Node *RotateLeft(struct Node *x) \r\n{\r\n struct Node *y = x->right;\r\n struct Node *TEMP2 = y->left;\r\n\r\n y->left = x;\r\n x->right = TEMP2;\r\n\r\n x->height = max(height(x->left), height(x->right)) + 1;\r\n y->height = max(height(y->left), height(y->right)) + 1;\r\n\r\n return y;\r\n}\r\n\r\nint getBalance(struct Node *N) \r\n{\r\n if (N == NULL)\r\n return 0;\r\n return height(N->left) - height(N->right);\r\n}\r\n\r\nstruct Node *insertNode(struct Node *node, int Val) \r\n{\r\n \r\n if (node == NULL)\r\n return (newNode(Val));\r\n\r\n if (Val < node->Val)\r\n node->left = insertNode(node->left, Val);\r\n else if (Val > node->Val)\r\n node->right = insertNode(node->right, Val);\r\n else\r\n return node;\r\n\r\n node->height = 1 + max(height(node->left),height(node->right));\r\n\r\n int balance = getBalance(node);\r\n if (balance > 1 && Val < node->left->Val)\r\n return RotateRight(node);\r\n\r\n if (balance < -1 && Val > node->right->Val)\r\n return RotateLeft(node);\r\n\r\n if (balance > 1 && Val > node->left->Val) \r\n {\r\n node->left = RotateLeft(node->left);\r\n return RotateRight(node);\r\n }\r\n\r\n if (balance < -1 && Val < node->right->Val) \r\n {\r\n node->right = RotateRight(node->right);\r\n return RotateLeft(node);\r\n }\r\n\r\n return node;\r\n}\r\n\r\nstruct Node *minValueNode(struct Node *node) \r\n{\r\n struct Node *current = node;\r\n\r\n while (current->left != NULL)\r\n current = current->left;\r\n\r\n return current;\r\n}\r\n\r\nstruct Node *deleteNode(struct Node *root, int Val) \r\n{\r\n if (root == NULL)\r\n return root;\r\n\r\n if (Val < root->Val)\r\n root->left = deleteNode(root->left, Val);\r\n\r\n else if (Val > root->Val)\r\n root->right = deleteNode(root->right, Val);\r\n\r\n else \r\n {\r\n if ((root->left == NULL) || (root->right == NULL)) \r\n {\r\n struct Node *temp = root->left ? root->left : root->right;\r\n\r\n if (temp == NULL)\r\n {\r\n temp = root;\r\n root = NULL;\r\n } \r\n else\r\n *root = *temp;\r\n free(temp);\r\n } \r\n else \r\n {\r\n struct Node *temp = minValueNode(root->right);\r\n\r\n root->Val = temp->Val;\r\n\r\n root->right = deleteNode(root->right, temp->Val);\r\n }\r\n }\r\n\r\n if (root == NULL)\r\n return root;\r\n\r\n root->height = 1 + max(height(root->left),height(root->right));\r\n\r\n int balance = getBalance(root);\r\n if (balance > 1 && getBalance(root->left) >= 0)\r\n return RotateRight(root);\r\n\r\n if (balance > 1 && getBalance(root->left) < 0) \r\n {\r\n root->left = RotateLeft(root->left);\r\n return RotateRight(root);\r\n }\r\n\r\n if (balance < -1 && getBalance(root->right) <= 0)\r\n return RotateLeft(root);\r\n\r\n if (balance < -1 && getBalance(root->right) > 0) \r\n {\r\n root->right = RotateRight(root->right);\r\n return RotateLeft(root);\r\n }\r\n\r\n return root;\r\n}\r\n\r\nvoid printPreOrder(struct Node *root) \r\n{\r\n if (root != NULL) \r\n {\r\n printf(\"%d \", root->Val);\r\n printPreOrder(root->left);\r\n printPreOrder(root->right);\r\n }\r\n}\r\n\r\nint main() \r\n{\r\n struct Node *root = NULL;\r\n\r\n root = insertNode(root, 56);\r\n root = insertNode(root, 14);\r\n root = insertNode(root, 86);\r\n root = insertNode(root, 25);\r\n root = insertNode(root, 38);\r\n root = insertNode(root, 69);\r\n root = insertNode(root, 89);\r\n\r\n printPreOrder(root);\r\n\r\n root = deleteNode(root, 14);\r\n\r\n cout <<\"AVL after deletion: \" ;\r\n printPreOrder(root);\r\n\r\n return 0;\r\n}\r\n<\/pre>\nImplementation of AVL Tree in JAVA<\/h3>\nclass Node {\r\n int item, height;\r\n Node left, right;\r\n\r\n Node(int d) {\r\n item = d;\r\n height = 1;\r\n }\r\n}\r\n\r\nclass AVL {\r\n Node root;\r\n\r\n int height(Node N) {\r\n if (N == null)\r\n return 0;\r\n return N.height;\r\n }\r\n\r\n int max(int a, int b) {\r\n return (a > b) ? a : b;\r\n }\r\n\r\n Node RotateRight(Node y) {\r\n Node x = y.left;\r\n Node T2 = x.right;\r\n x.right = y;\r\n y.left = T2;\r\n y.height = max(height(y.left), height(y.right)) + 1;\r\n x.height = max(height(x.left), height(x.right)) + 1;\r\n return x;\r\n }\r\n\r\n Node RotateLeft(Node x) {\r\n Node y = x.right;\r\n Node T2 = y.left;\r\n y.left = x;\r\n x.right = T2;\r\n x.height = max(height(x.left), height(x.right)) + 1;\r\n y.height = max(height(y.left), height(y.right)) + 1;\r\n return y;\r\n }\r\n\r\n int getBalanceFactor(Node N) {\r\n if (N == null)\r\n return 0;\r\n return height(N.left) - height(N.right);\r\n }\r\n\r\n Node insertNode(Node node, int item) {\r\n\r\n if (node == null)\r\n return (new Node(item));\r\n if (item < node.item)\r\n node.left = insertNode(node.left, item);\r\n else if (item > node.item)\r\n node.right = insertNode(node.right, item);\r\n else\r\n return node;\r\n\r\n node.height = 1 + max(height(node.left), height(node.right));\r\n int balanceFactor = getBalanceFactor(node);\r\n if (balanceFactor > 1) {\r\n if (item < node.left.item) {\r\n return RotateRight(node);\r\n } else if (item > node.left.item) {\r\n node.left = RotateLeft(node.left);\r\n return RotateRight(node);\r\n }\r\n }\r\n if (balanceFactor < -1) {\r\n if (item > node.right.item) {\r\n return RotateLeft(node);\r\n } else if (item < node.right.item) {\r\n node.right = RotateRight(node.right);\r\n return RotateLeft(node);\r\n }\r\n }\r\n return node;\r\n }\r\n\r\n Node nodeWithMimumValue(Node node) {\r\n Node current = node;\r\n while (current.left != null)\r\n current = current.left;\r\n return current;\r\n }\r\n\r\n Node deleteNode(Node root, int item) {\r\n\r\n if (root == null)\r\n return root;\r\n if (item < root.item)\r\n root.left = deleteNode(root.left, item);\r\n else if (item > root.item)\r\n root.right = deleteNode(root.right, item);\r\n else {\r\n if ((root.left == null) || (root.right == null)) {\r\n Node temp = null;\r\n if (temp == root.left)\r\n temp = root.right;\r\n else\r\n temp = root.left;\r\n if (temp == null) {\r\n temp = root;\r\n root = null;\r\n } else\r\n root = temp;\r\n } else {\r\n Node temp = nodeWithMimumValue(root.right);\r\n root.item = temp.item;\r\n root.right = deleteNode(root.right, temp.item);\r\n }\r\n }\r\n if (root == null)\r\n return root;\r\n\r\n root.height = max(height(root.left), height(root.right)) + 1;\r\n int balanceFactor = getBalanceFactor(root);\r\n if (balanceFactor > 1) {\r\n if (getBalanceFactor(root.left) >= 0) {\r\n return RotateRight(root);\r\n } else {\r\n root.left = RotateLeft(root.left);\r\n return RotateRight(root);\r\n }\r\n }\r\n if (balanceFactor < -1) {\r\n if (getBalanceFactor(root.right) <= 0) {\r\n return RotateLeft(root);\r\n } else {\r\n root.right = RotateRight(root.right);\r\n return RotateLeft(root);\r\n }\r\n }\r\n return root;\r\n }\r\n\r\n void preOrder(Node node) {\r\n if (node != null) {\r\n System.out.print(node.item + \" \");\r\n preOrder(node.left);\r\n preOrder(node.right);\r\n }\r\n }\r\n\r\n private void printTree(Node currPtr, boolean last) {\r\n if (currPtr != null) \r\n {\r\n \r\n System.out.print(currPtr.item+ \" \");\r\n printTree(currPtr.left, false);\r\n printTree(currPtr.right, true);\r\n }\r\n }\r\n\r\n public static void main(String[] args)\r\n {\r\n AVL tree = new AVL();\r\n tree.root = tree.insertNode(tree.root, 56);\r\n tree.root = tree.insertNode(tree.root, 14);\r\n tree.root = tree.insertNode(tree.root, 86);\r\n tree.root = tree.insertNode(tree.root, 25);\r\n tree.root = tree.insertNode(tree.root, 38);\r\n tree.root = tree.insertNode(tree.root, 69);\r\n tree.root = tree.insertNode(tree.root, 89);\r\n tree.printTree(tree.root, true);\r\n tree.root = tree.deleteNode(tree.root, 14);\r\n System.out.println(\"AVL After Deletion: \");\r\n tree.printTree(tree.root, true);\r\n }\r\n}\r\n<\/pre>\nImplementation of AVL Tree in Python<\/h3>\nimport sys\r\nclass TreeNode(object):\r\n def __init__(self, key):\r\n self.key = key\r\n self.left = None\r\n self.right = None\r\n self.height = 1\r\n\r\n\r\nclass AVLTree(object):\r\n\r\n def insert_node(self, root, key):\r\n\r\n if not root:\r\n return TreeNode(key)\r\n elif key < root.key:\r\n root.left = self.insert_node(root.left, key)\r\n else:\r\n root.right = self.insert_node(root.right, key)\r\n\r\n root.height = 1 + max(self.getHeight(root.left),self.getHeight(root.right))\r\n\r\n balanceFactor = self.getBalance(root)\r\n if balanceFactor > 1:\r\n if key < root.left.key:\r\n return self.RotateRight(root)\r\n else:\r\n root.left = self.RotateLeft(root.left)\r\n return self.RotateRight(root)\r\n\r\n if balanceFactor < -1:\r\n if key > root.right.key:\r\n return self.RotateLeft(root)\r\n else:\r\n root.right = self.RotateRight(root.right)\r\n return self.RotateLeft(root)\r\n\r\n return root\r\n\r\n def delete_node(self, root, key):\r\n\r\n if not root:\r\n return root\r\n elif key < root.key:\r\n root.left = self.delete_node(root.left, key)\r\n elif key > root.key:\r\n root.right = self.delete_node(root.right, key)\r\n else:\r\n if root.left is None:\r\n temp = root.right\r\n root = None\r\n return temp\r\n elif root.right is None:\r\n temp = root.left\r\n root = None\r\n return temp\r\n temp = self.getMinValueNode(root.right)\r\n root.key = temp.key\r\n root.right = self.delete_node(root.right,\r\n temp.key)\r\n if root is None:\r\n return root\r\n\r\n root.height = 1 + max(self.getHeight(root.left),\r\n self.getHeight(root.right))\r\n\r\n balanceFactor = self.getBalance(root)\r\n\r\n if balanceFactor > 1:\r\n if self.getBalance(root.left) >= 0:\r\n return self.RotateRight(root)\r\n else:\r\n root.left = self.RotateLeft(root.left)\r\n return self.RotateRight(root)\r\n if balanceFactor < -1:\r\n if self.getBalance(root.right) <= 0:\r\n return self.RotateLeft(root)\r\n else:\r\n root.right = self.RotateRight(root.right)\r\n return self.RotateLeft(root)\r\n return root\r\n\r\n def RotateLeft(self, z):\r\n y = z.right\r\n T2 = y.left\r\n y.left = z\r\n z.right = T2\r\n z.height = 1 + max(self.getHeight(z.left),self.getHeight(z.right))\r\n y.height = 1 + max(self.getHeight(y.left),self.getHeight(y.right))\r\n return y\r\n\r\n def RotateRight(self, z):\r\n y = z.left\r\n T3 = y.right\r\n y.right = z\r\n z.left = T3\r\n z.height = 1 + max(self.getHeight(z.left),self.getHeight(z.right))\r\n y.height = 1 + max(self.getHeight(y.left),self.getHeight(y.right))\r\n return y\r\n\r\n def getHeight(self, root):\r\n if not root:\r\n return 0\r\n return root.height\r\n\r\n def getBalance(self, root):\r\n if not root:\r\n return 0\r\n return self.getHeight(root.left) - self.getHeight(root.right)\r\n\r\n def getMinValueNode(self, root):\r\n if root is None or root.left is None:\r\n return root\r\n return self.getMinValueNode(root.left)\r\n\r\n def preOrder(self, root):\r\n if not root:\r\n return\r\n print(\"{0} \".format(root.key), end=\"\")\r\n self.preOrder(root.left)\r\n self.preOrder(root.right)\r\n\r\n def printAVL(self, currPtr, last):\r\n if currPtr != None:\r\n \r\n print(currPtr.key)\r\n self.printAVL(currPtr.left, False)\r\n self.printAVL(currPtr.right, True)\r\n\r\n\r\nmyTree = AVLTree()\r\nroot = None\r\nnums = [56, 14, 86, 25, 38, 69, 89]\r\nfor num in nums:\r\n root = myTree.insert_node(root, num)\r\nmyTree.printAVL(root, True)\r\nkey = 14\r\nroot = myTree.delete_node(root, key)\r\nprint(\"After Deletion: \")\r\nmyTree.printAVL(root, True)\r\n<\/pre>\nComplexity of AVL tree<\/h3>\n
Insertion: O( log n )
\nDeletion: O( log n )
\nSearch: O( log n )<\/p>\n
Applications of AVL Tree<\/h3>\n\n- Searching operations in very large datasets<\/li>\n
- Indexing of data in very large databases.<\/li>\n<\/ul>\n
Conclusion<\/h3>\n
AVL Trees are self-balancing binary trees. If at any point, during insertion or deletion, there is an unbalancing in the tree, it is again balanced by different rotations. AVL Trees are more balanced than red-black trees. AVL Tree is preferred over red-black trees in cases where the insertion and deletion are less frequent.<\/p>\n
In further articles, we will learn about another type of binary tree known as spanning tree.<\/p>\n","protected":false},"excerpt":{"rendered":"
AVL tree is a specific type of binary search tree where the difference between heights of left and right subtrees is either 0 or 1 only for all nodes. It implements all properties of...<\/p>\n","protected":false},"author":1,"featured_media":100402,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24020],"tags":[24901,24897,24899,24900,24898],"class_list":["post-100203","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure-tutorials","tag-applications-of-avl-tree","tag-avl-tree","tag-avl-tree-implementation-in-c","tag-complexity-of-avl-tree","tag-implementation-of-avl-tree-in-ds"],"yoast_head":"\n
AVL Tree in Data Structure - DataFlair<\/title>\n<meta name=\"description\" content=\"Learn what is AVL tree in Data Structure. See AVL rotations, operations, Working, implementation, applications & complexity of AVL tree.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/avl-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"AVL Tree in Data Structure - DataFlair\" \/>\n<meta property=\"og:description\" content=\"Learn what is AVL tree in Data Structure. See AVL rotations, operations, Working, implementation, applications & complexity of AVL tree.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/avl-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-20T03:30:38+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"14 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"AVL Tree in Data Structure - DataFlair","description":"Learn what is AVL tree in Data Structure. See AVL rotations, operations, Working, implementation, applications & complexity of AVL tree.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/avl-tree\/","og_locale":"en_US","og_type":"article","og_title":"AVL Tree in Data Structure - DataFlair","og_description":"Learn what is AVL tree in Data Structure. See AVL rotations, operations, Working, implementation, applications & complexity of AVL tree.","og_url":"https:\/\/data-flair.training\/blogs\/avl-tree\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-08-20T03:30:38+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"14 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9"},"headline":"AVL Tree in Data Structure","datePublished":"2021-08-20T03:30:38+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/"},"wordCount":644,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS.jpg","keywords":["Applications of AVL Tree","AVL tree","AVL Tree implementation in C++","Complexity of AVL tree","Implementation of AVL Tree in DS"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/avl-tree\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/","url":"https:\/\/data-flair.training\/blogs\/avl-tree\/","name":"AVL Tree in Data Structure - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS.jpg","datePublished":"2021-08-20T03:30:38+00:00","description":"Learn what is AVL tree in Data Structure. See AVL rotations, operations, Working, implementation, applications & complexity of AVL tree.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/avl-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS.jpg","width":1200,"height":628,"caption":"AVL tree in DS"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/avl-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Data Structure Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/data-structure-tutorials\/"},{"@type":"ListItem","position":3,"name":"AVL Tree in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team is a group of passionate educators and industry experts dedicated to providing high-quality online learning resources on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. With years of experience in the field, the team aims to simplify complex topics and help learners advance their careers. At DataFlair, we believe in empowering students and professionals with the knowledge and skills needed to thrive in today\u2019s fast-paced tech industry. Follow us for Free courses, expert insights, tutorials, and practical tips to boost your learning journey.","url":"https:\/\/data-flair.training\/blogs\/author\/datafbdad\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/100203","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=100203"}],"version-history":[{"count":2,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/100203\/revisions"}],"predecessor-version":[{"id":100416,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/100203\/revisions\/100416"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/100402"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=100203"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=100203"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=100203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"AVL](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image01.jpg\")
<\/a><\/p>\n![\"LL](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image02.jpg\")
<\/a><\/p>\n![\"RR](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image03.jpg\")
<\/a><\/p>\n![\"L](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image04.jpg\")
<\/a><\/p>\n![\"R](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image05.jpg\")
<\/a><\/p>\n![\"Insertion](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image6.jpg\")
<\/a><\/p>\n![\"Working](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image07.jpg\")
<\/a><\/p>\n![\"Insertion](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image08.jpg\")
<\/a><\/p>\n![\"AVL](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image09.jpg\")
<\/a><\/p>\n![\"AVL](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image010.jpg\")
<\/a><\/p>\n![\"Insert](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/08\/AVL-tree-in-DS-normal-image011.jpg\")
<\/a><\/p>\n