For the following intructions, write a self.__balancetree(self, t) method for a
ID: 3713366 • Letter: F
Question
For the following intructions, write a self.__balancetree(self, t) method for a AVL tree that does the following
If t is None, the tree is already balanced. Return t.
If t is left-heavy by 2:
If t's left child is left-heavy by 1 or balanced at 0, rotate right about t and return the new root.
If t's left child is right-heavy by 1, rotate left about t's left child, then rotate right about t and return the new root.
If t is right-heavy by 2:
If t's right child is left-heavy by 1 or balanced at 0, rotate left about t and return the new root.
If t's right child is right-heavy by 1, rotate right about t's right child, then rotate left about t and return the new root.
Explanation / Answer
//Define Structure AVL tree structure
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height; // height will be managed at time of insertion for example single node height will be 1
};
int getheight(strunct Node *self) // return height of node
{
if (self == NULL)
return 0;
return self->height;
}
int getbalance(struct Node *self) // return difference between height of left subtree and right subtree to check balancing
{
if(self==NULL)
return 0;
return getheight(self->left) - getheight(self-right);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
return y;
}
// after insertion a node in AVL tree check height of left subtree and right subtree
// there will be 4 cases
struct Node *balanceTree(struct Node *self,struct Node *t)
{
int bal=getbalance(t);
if(bal==0) // AVL TREE IS BALANCED
return t;
if(bal>1)
{
// t IS LEFT HEAVY BY 2
int diff=getbalance(t-left);
if(diff>0)
{
// t'S LEFT CHILD IS LEFT HEAVY BY 1 ROTATE RIGHT AND RETURN NEW ROOT
/*
Z(t) Y
/ /
Y T4 ----ROTATE RIGHT ABOUT t-- X Z
/ / /
X T3 T1 T2 T3 T4
/
T1 T2
*/
return rightRotate(t);
}
if (diff<0)
{
//t'S LEFT CHILD IS RIGHT HEAVY BY 1 RORATE LEFT ABOUT T'S LEFT CHILD THEN ROTATE RIGHT ABOUT T AND RETURN NEW ROOT
/*
Z(t) Z X
/ / /
Y T4 ----ROTATE LEFT ABOUT t->LEFT -- X T4 ---ROTATE RIGHT ABOUT t -- Y Z
/ / / /
T1 X Y T3 T1 T2 T3 T4
/ /
T2 T3 T1 T2
*/
t->left=rotateLeft(t->left);
return rightRotate(t);
}
}
if(bal<-1) // t IS RIGHT HEAVY BY 2
{
int diff=getbalance(t->right);
if(diff<0)
{
// t'S RIGHT CHILD IS RIGHT HEAVY BY 1 ROTATE LEFT AND RETURN NEW ROOT
/*
Z(t) Y
/ /
T1 Y ----ROTATE LEFT ABOUT t---- Z X
/ / /
T2 X T1 T2 T3 T4
/
T3 T4
*/
return leftRotate(t);
}
if(diff>0)
{
//t'S RIGHT CHILD IS LEFT HEAVY BY 1 ROTATE ROOT ABOUT IT'S RIGHT CHILD AND THEN ROTATE ABOUT IT'S LEFT CHILD
/*
Z(t) Z X
/ / /
T1 Y ----ROTATE RIGHT ABOUT t->RIGHT---- T1 X ---ROTATE LEFT ABOUT t --- Z Y
/ / / /
X T4 T2 Y T1 T2 T3 T4
/ /
T2 T3 T3 T4
*/
t->right=rightRotate(t->right);
return leftRotate(t);
}
}
}