AVL Tree & B-Tree
AVL Tree What is AVL Tree? AVL Tree is a self-balancing Binary Search Tree (BST), link to learn about BST where the difference between the depth of left and right sub-trees cannot be more than one for all nodes. To get the balance factor we get the longest depth of each left and right of the node. Then using this formula to get the balance, balance = depth of left - depth of right. This is an example of a balanced tree: This is an example of a unbalanced tree: As shown, there are 2 node that violates the balance because there are nodes with balance more than one. If this happens we will choose the deepest node that violates the balance factor to be fixed. Why AVL Trees? Most of the BST operations take O(h) time where h is the height of BST. Worst cast senario may become O(n) for a skewed Binary tree . If we make sure that height of the tree remains O(log n) after every insertion or deletion, then we can guarantee an upper bound of O(log n) for all BST op...