The Gateway to Computer Science Excellence

+7 votes

Consider the height-balanced tree $T_{t}$ with values stored at only the leaf nodes, shown in Fig.4.

(i) Show how to merge to the tree, $T_{1}$ elements from tree $T_{2}$ shown in Fig.5 using node D of tree $T_{1}$.

(ii) What is the time complexity of a merge operation of balanced trees $T_{1}$ and $T_{2}$ where $T_{1}$ and $T_{2}$ are of height $h_{1}$ and $h_{2}$ respectively, assuming that rotation schemes are given. Give reasons.

+3 votes

A height balanced tree is a binary tree in which the difference between the left subtree and right subtree is not greater than 1.

Since the values are stored only at the leaf nodes and the merging is done using node D, we add extra nodes as shown below :-

Complexity will be $O(n \log n)$

As here all nodes of second tree need to be inserted in tree and rotation of nodes are needed.

0

How did you merge t1 and t2.. I m not getting it.. Can't we just put all elements and from t1 and t2 and perform insertion with rotation..

+1

@srestha , I think, you have added some extra nodes..here T_{1} contains 9 nodes and T_{2} contains 5 nodes. So, after merging , total nodes should be 14..but in your 1^{st} image , no. of nodes = 15 and in 3^{rd} image , no. of nodes = 16...

could you please explain why time complexity is O(nlogn).. I think here we should have to write time complexity in terms of h_{1} and h_{2}. and could you please explain what is meaning of merge using node D.

0

@ankit

I havenot added 1 extra node, I added 2 extra node

See in 1st pic after E I added 1 extra node, otherwise 5 couldnot be there in resultant tree

and yes again I added 1 extra node in 3rd pic

Because it holds 6,7 as leaf

Basically according to question, we need to accommodate 8 nodes as leaf

I havenot added 1 extra node, I added 2 extra node

See in 1st pic after E I added 1 extra node, otherwise 5 couldnot be there in resultant tree

and yes again I added 1 extra node in 3rd pic

Because it holds 6,7 as leaf

Basically according to question, we need to accommodate 8 nodes as leaf

0

@srestha , instead of adding one extra node , can't we add 6 to the left of E and 5 to the left of 6 ?

52,345 questions

60,495 answers

201,848 comments

95,306 users