merge two binary search tree - 未名空间MITBBS历史存档

merge two binary search tree# JobHunting - 待字闺中

l*y2010-04-25 07:04

1 楼

given two binary search trees, merge them in O(n) time with O(1) space.
(Converting them to link lists does not work since it require O(n) extra
pointer space)
谁能给讲一讲。
谢谢！

a*s2010-04-25 07:04

2 楼

我觉得基本思路可以是这样子的:
Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
个结点指针L1和L2，使得
L1->data <= BN2->data <= L2->data
注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)

【在 l*********y 的大作中提到】

: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！

r*o2010-04-25 07:04

3 楼

为什么要么L1的右儿子为空，要么L2的左儿子为空呢？

该也是O(1)，所以总的时间为O(n)

【在 a**********s 的大作中提到】

: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)

f*e2010-04-25 07:04

4 楼

不是相当于遍历两颗树么？
比如分别先根遍历，每访问一个接点，把该节点断开，这样可行么？

【在 l*********y 的大作中提到】

: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！

a*s2010-04-25 07:04

5 楼

因为L1和L2是前后相继的两个结点，其中有一个必然为另外一个的祖先，否则的话，他
们的共同祖先在他们中间。
然后，如果L1为L2的祖先，那么L2在L1的右子树，那么L2的左儿子必然为空，否则的话
，L2的左儿子在L1和L2中间。
同理可证L2为L1的祖先的情况下，L1的右儿子为空。
我明白了你为什么困惑了，我前面忘了写L1和L2前后相继了，现在改过来了。

【在 r****o 的大作中提到】

: 为什么要么L1的右儿子为空，要么L2的左儿子为空呢？
:
: 该也是O(1)，所以总的时间为O(n)

k*i2010-04-25 07:04

6 楼

你怎么读第二个bst的每一个节点是从小到大？inorder？，并且读的复杂度不是O（n）
？为啥？

该也是
O(1)，所以总的时间为O(n)

【在 a**********s 的大作中提到】

: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)

l*y2010-04-25 07:04

7 楼

想了一下，感觉你说的是对的。而且这个题non-recursive的implementation似乎要比
recursive简单一些。

【在 a**********s 的大作中提到】

: 因为L1和L2是前后相继的两个结点，其中有一个必然为另外一个的祖先，否则的话，他
: 们的共同祖先在他们中间。
: 然后，如果L1为L2的祖先，那么L2在L1的右子树，那么L2的左儿子必然为空，否则的话
: ，L2的左儿子在L1和L2中间。
: 同理可证L2为L1的祖先的情况下，L1的右儿子为空。
: 我明白了你为什么困惑了，我前面忘了写L1和L2前后相继了，现在改过来了。

r*o2010-04-25 07:04

8 楼

你是说两个都以non-recursive的inorder访问?
我有个疑问是，对于第二个BST的每一个节点，怎么找到第一个BST的一对L1和L2呢？
这里是不是要用到binary search?

该也是O(1)，所以总的时间为O(n)

【在 a**********s 的大作中提到】

: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)

x*y2010-04-25 07:04

9 楼

How can you inorder traverse the 2nd BST in O(1) space? At least a stack is
needed for non-recursive method.....In essence, what trick in your method
makes the space from O(n), in flattening and merging method, to O(1). thanks a lot
...

该也是O(1)，所以总的时间为O(n)

【在 a**********s 的大作中提到】

: 我觉得基本思路可以是这样子的:
: Non-recursively访问第二个BST的每一个节点（这样的话，得到的是从小到大的顺序，
: 并且时间空间复杂度分别是O(N2)和O(1)），一个一个的插入到第一个BSP，假设每一步
: 待插入的node为BN2。然后第一个BSP也是non-recursively访问，并保持前后相继的两
: 个结点指针L1和L2，使得
: L1->data <= BN2->data <= L2->data
: 注意到要么L1的右儿子为空，要么L2的左儿子为空，这样插入每一个节点的复杂度应该也是O(1)，所以总的时间为O(n)

a*s2010-04-25 07:04

10 楼

明白大家为什么困惑了，non-resursive BST traversal是基本的二叉树操作，只需要线性时间和常数空间复杂度，但是需要一个父指针。。。
没有父指针的二叉树合并，好像也是可以做的，我再想想。

k*e2010-04-25 07:04

11 楼

please check DSW algorithm

【在 l*********y 的大作中提到】

: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！

g*u2010-04-25 07:04

12 楼

呵呵，我以前也问过这个题目。就是DSW，先把两个BST通过旋转变为两个link list，
再merge，再旋转为满二叉树。

【在 k***e 的大作中提到】

: please check DSW algorithm

l*y2010-04-25 07:04

13 楼

请问这个不是space O(n) 吗？

【在 g*****u 的大作中提到】

: 呵呵，我以前也问过这个题目。就是DSW，先把两个BST通过旋转变为两个link list，
: 再merge，再旋转为满二叉树。

p*o2010-04-25 07:04

14 楼

Inplace的啊

【在 l*********y 的大作中提到】

: 请问这个不是space O(n) 吗？

c*p2010-04-25 07:04

15 楼

if re-use the left and right pointer in nodes of binary search tree as prev
and next pointer to build a linked-list, no extra O(n) space is needed.

【在 l*********y 的大作中提到】

: given two binary search trees, merge them in O(n) time with O(1) space.
: (Converting them to link lists does not work since it require O(n) extra
: pointer space)
: 谁能给讲一讲。
: 谢谢！

s*92010-04-25 07:04

16 楼

没有父指针的话，需要有一个龙lg(n)的stack。在O(1)额外内存的限制下，只能是把两
棵树都用连续的左转操作转换成List，合并后再右转操作成一颗平衡二叉树。

要线性时间和常数空间复杂度，但是需要一个父指针。。。

【在 a**********s 的大作中提到】

: 明白大家为什么困惑了，non-resursive BST traversal是基本的二叉树操作，只需要线性时间和常数空间复杂度，但是需要一个父指针。。。
: 没有父指针的二叉树合并，好像也是可以做的，我再想想。