AVL and B3
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree so in short there it is a sorted BST to make searching, inserting, etc, faster. since it has a habt of rebalancing it self. 4 possible case:- left left case left right case right right case right left case for each of the following cases, there are actions took to rebalance the tree and sort the tree by rotating it. B-tree B-Tree is a self-balancing search tree. In most of the ...