edited by
3,805 views
11 votes
11 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.

edited by

2 Answers

Best answer
15 votes
15 votes

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

selected by
6 votes
6 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

Related questions

14 votes
14 votes
3 answers
2
makhdoom ghaya asked Nov 19, 2016
5,016 views
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{Construct...
9 votes
9 votes
2 answers
3
makhdoom ghaya asked Nov 26, 2016
1,918 views
Show that the elements of the lattice $(N, \leq)$, where $N$ is the set of positive intergers and $a \leq b$ if and only if $a$ divides $b$, satisfy the distributive prop...
0 votes
0 votes
0 answers
4