Consider the height-balanced tree T₁ with values stored at only the leaf…

PYQ GATE 1990

Consider the height-balanced tree T₁ with values stored at only the leaf nodes, shown in Fig. 4.

Height-balanced tree T1: root B; left child A with leaf children 1 and 2; right child D with left child C, whose leaves are 3 and 4, and right leaf 5.

Show how to merge to the tree T₁ elements from tree T₂ shown in Fig. 5 using node D of tree T₁.

Height-balanced tree T2: root F; left child E with leaf children 6 and 7; right leaf 8.

What is the time complexity of a merge operation of balanced trees T₁ and T₂ where T₁ and T₂ are of height h₁ and h₂ respectively, assuming that rotation schemes are given. Give reasons.

Attempted by 2 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…