3. 20 points Suppose you have an AVL tree with tree nodes such that each tree no

Question

3. 20 points Suppose you have an AVL tree with tree nodes such that each tree node, u as the following pieces of data: .u leftChild .urightChild uparent .u- key ubalance Factor that you are given, as input, a tree node u. (a) Write pseudocode to determine what kind of rotation (if any) should be performed on u to rebalance it (b) Write pseudocode to perform a left-rotation about u (c) Write pseudocode to perform a right-rotation aboutu d) Write pseudocode to perform a left-right-rotation about u (e) Write pseudocode to perform a right-left-rotation about u

Explanation / Answer

Balance-factor = height(left-subtree)-height(right_subtree)

Range of Balance-factor of a balanced AVL tree: {-1,0,1}.

If the balance-factor is

<-2, tree is right-heavy,

>2, tree is left-heavy.

a.

balance_factor = balance_factor(u)

if (balance_factor>=-1 && balance_factor<=1):

//do nothing

else if (balance_factor <=-2 ){

if(balance_factor(u.right_child.right_child)==0):

left_rotation(u)

else if (balance_factor(u.right_child.left_child)==0):

right_left_rotation(u)

}

else if (balance_factor >=2) {

if(balance_factor(u.left_child.right_child)==0):

left_right_rotation(u)

else if (balance_factor(u.left_child.left_child)==0):

right_left_rotation(u)

}

b.(left_rotation(Node u))

Pseudocode to perform left-rotation about u:

parent=parent(u) //Save parent of node u in parent

right_child = right_child(u); //Save right child of u in right_child

if (left_child(parent) == u): //Checking if u is left-child of parent

parent.left_child = right_child // if yes, then make left child of parent as right child of u
u.right_child = left_child(right_child) // Change right child of u to left child of right child of u
right_child.left_child = u; //Change left child of right child of u to u   

else if (right_child(parent)==u): //Checking if u is right-child of parent

parent.right_child = right_child // if yes, then make right child of parent as right child of u   

u.right_child = left_child(right_child) // Change right child of u to left child of right child of u
right_child.left_child = u; //Change left child of right child of u to u

c.(right_rotation(Node u))

Pseudocode to perform right-rotation about u:

parent=parent(u) //Save parent of node u in parent

left_child = left_child(u); //Save right child of u in right_child

if (left_child(parent) == u): //Checking if u is left-child of parent

parent.left_child = left_child // if yes, then make left child of parent as left child of u
u.left_child = right_child(left_child) // Change left child of u to right child of left child of u
left_child.right_child = u; // change right child of left child of u to u

else if (right_child(parent)==u): //Checking if u is right-child of parent

parent.right_child = left_child //if yes, then make right child of parent as left child of u

u.left_child = right_child(left_child) //change left child of u to right child of left child of u
left_child.right_child = u; // change right child of left child of u to u

d.

If node u is unbalanced,

Pseudocode to perform left-right rotation about u:

left_child = left_child(u)

left_rotation(left_child)

// now, the right child of left_child will become left child of u. Now we will perform right rotation about this left child of u.

left = left_child(u)

right_rotation(left)

e. Pseudocode to perform a right-left rotation about u:

right_child = right_child(u)

right_rotation(right_child)

//Now, left child of right_child will become right child of u. We will perform left rotation about this right child of u.

right = right_child(u)

left_rotation(right)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.