Question

Problem 2 [35 points (155 15)]: Let Ti and T2 be two binary search trees containing the same elements. In this problem, you will show how to transform Ti into T2 (i.e. Ti is altered to now have the same structure as T2) through a series of rotation operations. (a) Define a binary tree to be a right-going chain if no node in the tree has a left child (in other words, the tree is a linked list formed through right-child links) Describe a procedure that takes a binary tree and transforms it into right-going chain through a series of at most -1 right rotations Hint: In your argument, consider the right spine of the T, which is defined as the path from the root to the right-most node. If you peform a right-rotation on ฉ node in the the right spine that has a left child, what happens to the length of the right spine?) (b) Next, given a tree T that is right-going chain and a node a in T, describe how through a series of left rotationswe can make the root of the tree (c) Using the procedures you defined in parts (a) and (b), give an algorithm for transform- ing a binary tree Ti into another binary tree T2. Hint: After completing the procedure in part (b), what does the tree look like? How can the process you ve used so far be repeated on the right and left subtrees in order to make the tree look like T2?)

Answer 1

Answer A->

In tree there are at most n nodes. It is right chained so it is having 1 leaf node and n-1 parent nodes.

So to get right chained binary tree from binary tree.Take right most element as leaf node

and then for every parent if it has left child make parent as right child of its left child by right rotation.In case if left child is already having right child then there is left rotation is done I am giving you example to solve this problem

So, there can be at most rotation for each parent node

Ca (L) 2 2

So each time parent will become right child of its left child in right rotation.

parent will become left child of its right child in left rotation.So there are at max 1 rotation is required to make a parent to child.

Answer 2->If you are having right chained binary tree.You need p rotation to make x as root where p is total number ancestors of x.To make root we will need to perform p left rotation .example is shown in below picture

anator 3

Answer c-> To transform Tree T1 to T2 we need left and right rotation accordingly. We need to reverse back all operations of b and a to get back the tree

Algorithm ->

as we know the depth can be more so , we need to first go till leaf node so that roatation can be performed

function (btree):

               if btree->leftchild

                       function(btree->leftchild);

                       roatate_right(btree)

              else if btree->leftchild=NULL and btree->rightchild

                      rotate_left(btree)

rotate_left ( btree ):

             btree->leftchild=btree->leftchild->rightchild

             btree->leftchild->rightchild=btree;

rotate_right ( btree ):

             btree->rightchild=btree->rightchild->leftchild

             btree->rightchild->leftchild=btree;

These rotation are same as AVL tree.

If you have any doubt.Please feel free to ask.Thanks