AVL Tree...
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one.
Height of AVL tree...
M(h) is the minimum number of node in a AVL tree with height h.
also we have
Insertion Algorithm...
To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing.
Following are two basic operations that can be performed to balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
- Left Rotation
- Right Rotation
Operation Step By Step...
- Perform the normal BST insertion.
- The current node must be one of the ancestors of the newly inserted node. Update the height of the current node.
- Get the balance factor (left subtree height – right subtree height) of the current node.
- If the balance factor is greater than 1, then the current node is unbalanced and we are either in the Left Left case or left Right case. To check whether it is left left case or not, compare the newly inserted key with the key in the left subtree root.
- If the balance factor is less than -1, then the current node is unbalanced and we are either in the Right Right case or Right-Left case. To check whether it is the Right Right case or not, compare the newly inserted key with the key in the right subtree root.
Height Difference in Black and Red Tree...
the difference between sub trees is equal to the difference between the number of red nodes we also know that this number is at most