tag:blogger.com,1999:blog-6314876008291942531.post9222200781041861264..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: merge two binary search tree in optimal space and timeUnknownnoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6314876008291942531.post-4504447981757575442010-03-31T12:20:05.808-07:002010-03-31T12:20:05.808-07:00I am very curious to see how your algorithm works,...I am very curious to see how your algorithm works, since I have been unable to materialize/visualize it.<br />You said "<i>..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.</i>".<br />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.<br />Could you please provide a pseudo-code so that your algorithm becomes crystal clear :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-36719232399855749312010-03-31T01:37:27.843-07:002010-03-31T01:37:27.843-07:00This algorithm doesn't make random access to a...This algorithm doesn't make random access to any list :-).GiroTontihttps://www.blogger.com/profile/10692779656905527925noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-88048090939746025492010-03-26T12:52:28.978-07:002010-03-26T12:52:28.978-07:00The second step of your procedure in O(n*n), its a...The second step of your procedure in O(n*n), its a linked list, every access of an element is O(n)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-37211643665297234162010-02-10T07:10:14.001-08:002010-02-10T07:10:14.001-08:00Let me describe an algorithm that works in-place u...Let me describe an algorithm that works in-place using linear time. <br />The algorihtm destroys the two original trees, reusing their spaceto store the tree in output.<br /><br />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.<br /> <br />On one-side it is possible to linearize a tree into a linked-list, in linear time and in-place.<br />The algorithm makes use of simple rotations of the tree. Initially we are in the root of the tree, and<br />keep on rotating rightward until the root has no left child. Then we move on the right child of the root and <br />apply the same procedure, and so on until the tree becomes an ordered list. It is easy to prove that the<br />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. <br /><br />In this way, we can transform the two original trees into ordered lists which can be easily merged in place<br />into a single ordered list. The final step of the solution consists in transforming the ordered list into a balanced search tree. <br /><br />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<br />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 <br />the rightmost path at each stage, an easy calculation shows that the total running time of the algorithm is linear.GiroTontihttps://www.blogger.com/profile/10692779656905527925noreply@blogger.com