MERGING TREES

Post new topic   Reply to topic

View previous topic View next topic Go down

MERGING TREES

Post  prani on Wed Aug 13, 2008 3:24 pm

Given two balanced binary trees,
how to merge them in minimum time so that final tree is also balanced???

prani

Posts: 15
Join date: 2008-08-12

View user profile

Back to top Go down

@tiwari ji

Post  shivang on Mon Aug 18, 2008 6:34 pm

Do let me know if i am doing this correctly....
Step 1: Convert one of the trees into a linear list. this can be done in the following two ways
i)As it is given that the tree is perfectly balanced we can convert one tree into a linear list using the inorder traversal in O(n) time. But ya if the tree is not balanced this procedure will have to be altered and time complexity will increase.

or

ii)u can convert a tree into list by using the rotations that we studied in Red Black trees in same O(n) time complexity no matter if the tree is balanced or not/

Step 2: Add the list elements into the other tree by simple insert procedure. for one element to be inserted time will be O(lgn)
so the total time complexity will be O(nlgn)

shivang

Posts: 22
Join date: 2008-08-11
Age: 20
Location: Tondon 174

View user profile

Back to top Go down

View previous topic View next topic Back to top


Permissions of this forum:
You cannot reply to topics in this forum