The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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 Veteran (47.8k points) | 188 views

2 Answers

+1 vote

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 (81.5k 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
0 votes
answered by (67 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

33,714 questions
40,263 answers
38,898 users