Let me describe an algorithm that works in-place using linear time. The algorihtm destroys the two original trees, reusing their spaceto store the tree in output.
The solution is based on two transforms which map trees into linked-lists and vice-versa, operating in-place and preserving the order of the elements.
On one-side it is possible to linearize a tree into a linked-list, in linear time and in-place. The algorithm makes use of simple rotations of the tree. Initially we are in the root of the tree, and keep on rotating rightward until the root has no left child. Then we move on the right child of the root and apply the same procedure, and so on until the tree becomes an ordered list. It is easy to prove that the total number of rotations is at most the number of nodes, as each rotation increases the length of the rightmost path, thus the algorithm takes overall linear time.
In this way, we can transform the two original trees into ordered lists which can be easily merged in place into a single ordered list. The final step of the solution consists in transforming the ordered list into a balanced search tree.
This can be done again by repeated use of rotations. Starting from the initial list (which is already a search tree), the algorithm works in successive stages where each stage transforms the current tree into a more balanced one. In each stage we traverse the rightmost path of the tree descending from the root, and apply a leftward rotation on every other node on the path. We stop when the rightmost path has logarithmic length; at this stage the height of the tree will be logarithmic. Since we halve the length of the rightmost path at each stage, an easy calculation shows that the total running time of the algorithm is linear.
I am very curious to see how your algorithm works, since I have been unable to materialize/visualize it. You said "..In each stage we traverse the rightmost path of the tree descending from the root, and apply a leftward rotation on every other node on the path.". As you are building the tree, to find out at which node the tree is unbalanced (i.e. where to apply a left/right rotation) also requires a log(n) traversal of the tree and the unbalances will occur on both sides of the root so you need to rotate on both the sides. Could you please provide a pseudo-code so that your algorithm becomes crystal clear :)
Let me describe an algorithm that works in-place using linear time.
ReplyDeleteThe algorihtm destroys the two original trees, reusing their spaceto store the tree in output.
The solution is based on two transforms which map trees into linked-lists and vice-versa, operating in-place and preserving the order of the elements.
On one-side it is possible to linearize a tree into a linked-list, in linear time and in-place.
The algorithm makes use of simple rotations of the tree. Initially we are in the root of the tree, and
keep on rotating rightward until the root has no left child. Then we move on the right child of the root and
apply the same procedure, and so on until the tree becomes an ordered list. It is easy to prove that the
total number of rotations is at most the number of nodes, as each rotation increases the length of the rightmost path, thus the algorithm takes overall linear time.
In this way, we can transform the two original trees into ordered lists which can be easily merged in place
into a single ordered list. The final step of the solution consists in transforming the ordered list into a balanced search tree.
This can be done again by repeated use of rotations. Starting from the initial list (which is already a search tree), the algorithm works in successive stages
where each stage transforms the current tree into a more balanced one. In each stage we traverse the rightmost path of the tree descending from the root, and apply a leftward rotation on every other node on the path. We stop when the rightmost path has logarithmic length; at this stage the height of the tree will be logarithmic. Since we halve the length of
the rightmost path at each stage, an easy calculation shows that the total running time of the algorithm is linear.
The second step of your procedure in O(n*n), its a linked list, every access of an element is O(n)
ReplyDeleteThis algorithm doesn't make random access to any list :-).
ReplyDeleteI am very curious to see how your algorithm works, since I have been unable to materialize/visualize it.
ReplyDeleteYou said "..In each stage we traverse the rightmost path of the tree descending from the root, and apply a leftward rotation on every other node on the path.".
As you are building the tree, to find out at which node the tree is unbalanced (i.e. where to apply a left/right rotation) also requires a log(n) traversal of the tree and the unbalances will occur on both sides of the root so you need to rotate on both the sides.
Could you please provide a pseudo-code so that your algorithm becomes crystal clear :)