menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

GATE1990-13a

7 votes
1.3k views

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.

in DS
edited by 1.3k views

2 Answers

5 votes

Superscript near the nodes indicate their Balance factor. LL and RR rotations are same as those done on AVL trees.

 

0

Your answer makes some sense. 🖕

@ankitgupta.1729

Brother, can you check it?

0
This is correct
4 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.


edited by
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..
0
like BST

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

@srestha , I think, you have added some extra nodes..here 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.

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

edited by
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 ?
1
then 6 will not be leaf
0
@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..
0
yes, required

As this is pattern given in question

some visualization required to ans some ques
0
@srestha In First Image Left Child of E is 4 and Right Child of C is 4 can u explain please?
0
how Complexity will be O(n log n) ??
3
0
O(n) tc if the use of extra space is permitted
0

yes @Bhupendra 

1

@adarsh_1997 why we did rotation on node B when D is also not balanced in 3rd Picture?

0
I think there's a problem with the question . It says values must reside as leaves , meaning letters should be internal nodes . if we have 6 internal node i.e A to F then in a binary tree we can accommodate at max 7 leaves , however the question asks us to fit in 8 leaves .
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

7 votes
4 answers
1
1.1k views
GATE1990-3-iv
Choose the correct alternatives (More than one may be correct). The total external path length, EPL, of a binary tree with $n$ external nodes is, $EPL= \sum_{w} Iw$, where $I_{w}$ is the path length of external node $w$), $\leq n^{2}$ always. $\geq n \log_{2} n$ always. Equal to $n^{2}$ always. $O(n)$ for some special trees.
Choose the correct alternatives (More than one may be correct). The total external path length, EPL, of a binary tree with $n$ external nodes is, $EPL= \sum_{w} Iw$, where $I_{w}$ is the path length of external node $w$), $\leq n^{2}$ always. $\geq n \log_{2} n$ always. Equal to $n^{2}$ always. $O(n)$ for some special trees.
asked Nov 22, 2016 in DS makhdoom ghaya 1.1k views
7 votes
2 answers
2
1.4k views
GATE1990-2-viii
Match the pairs in the following questions: ...
Match the pairs in the following questions:$\begin{array}{|ll|ll|} \hline (a) & \text{A heap construction} & (p) & \ \Omega(n\log_{10}n) \\\hline (b) & \text{Constructing Hashtable with linear probing} & (q) & \ O(n) \\\hline (c) & \text{AVL tree construction} & (r) & \ O(n^{2}) \\\hline (d) & \text{Digital trie construction} & (s) & \ O(n\log_{10}n) \\\hline \end{array}$
asked Nov 19, 2016 in DS makhdoom ghaya 1.4k views
17 votes
1 answer
3
1.8k views
GATE1998-21
Derive a recurrence relation for the size of the smallest AVL tree with height $h$. What is the size of the smallest AVL tree with height $8$?
Derive a recurrence relation for the size of the smallest AVL tree with height $h$. What is the size of the smallest AVL tree with height $8$?
asked Sep 26, 2014 in DS Kathleen 1.8k views
8 votes
3 answers
4
1.2k views
GATE1990-1-iv-b
A 32-bit floating-point number is represented by a 7-bit signed exponent, and a 24-bit fractional mantissa. The base of the scale factor is 16, The range of the exponent is ___________, if the scale factor is represented in excess-64 format.
A 32-bit floating-point number is represented by a 7-bit signed exponent, and a 24-bit fractional mantissa. The base of the scale factor is 16, The range of the exponent is ___________, if the scale factor is represented in excess-64 format.
asked Feb 12, 2018 in Digital Logic jothee 1.2k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...