MERGING TREES

Go down

MERGING TREES

Post  prani on Wed Aug 13, 2008 9:24 am

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 12: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)
avatar
shivang

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

View user profile

Back to top Go down

Back to top

- Similar topics

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