Height balanced BST (AVL Tree):
It is a special type of BST that remains balanced tree even if the input to the tree is sorted. Each node in an AVL tree maintain balance factor which is calculated as
BAL = (height of left sub-tree) – (height of right sub-tree)
A node is said balanced if its balanced factor is (0, -1, 1).
BAL Otherwise node is unbalanced.
If a node is become unbalanced, it is made balanced by rotating the unbalanced node in opposite direction of unbalanced.
NB - When the sign of balance factor is negative (-ve) then node to be rotated left and when the sign of balance factor is positive (+ve) then node to be rotated right.
NB – When two consecutive nodes got unbalanced then two rotations is needed and first node form leaf side is rotated first then other.
NB – When two consecutive node’s balance factor has opposite sign then youngest node is rotated first according to its sign and then other.
When two or more consecutive nodes got unbalanced nearest node from leaf node should rotate.
Functions:
leftrotate(struct avltree *t)
{
Struct avltree *r, *temp;
r= t->right;
temp = r->left;
r->left = t;
t->right = temp;
}
rightrotate(struct avltree *t)
{
struct avltree *l , *temp;
L = t->left;
l->right = t;
temp = l->right;
l->right = t;
t->left = temp;
}
0 comments:
Post a Comment