AVL Tree vs Red-Black Tree

  AVL Tree vs Red-Black Tree AVL Tree The best benefit of the BST data structure is the time complexity of all the tree operations is O(logn) , where n is the number of total nodes. If the BST is a left-skewed or right-skewed tree, time complexity becomes O(n) . The solution to this is the AVL tree data structure. Named after the inventors A delson- V elsky and L andis. AVL Tree is a self-balancing binary search tree. In an AVL tree, heights of the two child subtrees of any node differ by maximum one.  AVL Tree is a self – balanced or height-balanced binary search tree where the difference between heights of its left sub-tree and right sub-tree ( Balance Factor ) can't be more than one for all nodes covered by a tree. We can say a tree is balanced if the balance factor of each node of a tree is  -1,0 or 1; otherwise, a tree is considered as unbalanced and needs to balance.             Balance factor (node) = height (left node) – height (right node) We can balance an AVL tree by per