AVL Tree and Binary Tree
1. AVL TREE What is AVL tree? AVL tree is a binary search tree in which the difference of heights of left and right subtrees of any node is less than or equal to one. The goal is to keep the height of a BST to be O(log n). Operations like insertion or deletion will have lower time complexity. Here we see that the first tree is balanced and the next two trees are not balanced In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the difference is 2. In the third tree, the right subtree of A has height 2 and the left is missing, so it is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only 1. If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some rotation techniques. AVL ROTATION There are 4 types of rotation: - Left rotation - Right rotation - Left-Right rotation - Right-Left rotation We will ...