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 (42.9k points) | 138 views

2 Answers

0 votes
answered by (51 points)
0 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 (70.4k 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

29,154 questions
36,976 answers
34,816 users