The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 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.

asked in DS by Boss (40k points) | 249 views

2 Answers

+2 votes

We have to merge $T_{1}$ and $T_{2}$

Only the D node will be participate in merging

All the values of the tree are in leaf node

and it should be height balanced

Complexity will be O(n log n)

As here all nodes of 2nd tree needs to be insert in tree and rotation of nodes needed.

answered by Veteran (86.9k points)
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..
like BST

F can be right child of B and 5 will be in left subtree leaf of F

@srestha , I think, you have added some extra T1 contains 9 nodes and T2 contains 5 nodes. So, after merging , total nodes should be 14..but in your 1st image , no. of nodes = 15 and in 3rd 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 h1 and h2. and could you please explain what is meaning of merge using node D.


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
@srestha , instead of adding one extra node , can't we add 6 to the  left of E and 5 to the left of 6 ?
then 6 will not be leaf
@srestha , is it necessary that all given leaf nodes should also be leaf nodes in the merged tree ?  it is not mentioned in the question..
yes, required

As this is pattern given in question

some visualization required to ans some ques
–1 vote
answered by (61 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,194 questions
43,647 answers
42,929 users