merge two Binary search tree in O(n) time and O(1) space - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

merge two Binary search tree in O(n) time and O(1) space

merge two Binary search tree in O(n) time and O(1) space# Programming - 葵花宝典

c*t2009-12-14 08:12

1 楼

Hi, I am posting this for my friend. She is a Native English speaker and
looking for an English tutoring job.If you are interested, please pm or
reply here. I will contact with you soon.Thanks!
您好, 我替我朋友发这个贴子. 她是老美,正在找一个教英文的工作.如果你有兴趣,请
给我站内发短信.谢谢.我会尽快与您联系.

H*M2009-12-14 08:12

2 楼

that excludes recursion..
can not think of how to...
any ideas?
dsw algorthm by tree rotation?
Thanks!

X*r2009-12-14 08:12

3 楼

Traversing a binary search tree is O(n) time and O(1) space, right?
Just to traverse two trees together, removing nodes from one tree
and insert them into the right place of the other, like merge sort.

【在 H*M 的大作中提到】

: that excludes recursion..
: can not think of how to...
: any ideas?
: dsw algorthm by tree rotation?
: Thanks!

H*M2009-12-14 08:12

4 楼

traversing a binary search tree is O(1) space? how?
if recursion ->no
if iterative, need stack a...

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

: Traversing a binary search tree is O(n) time and O(1) space, right?
: Just to traverse two trees together, removing nodes from one tree
: and insert them into the right place of the other, like merge sort.

X*r2009-12-14 08:12

5 楼

This assumes every node in the tree has a pointer to its parent.
To find the next ndoe of current node: if the current node has right
child, return the left-most descendant of the right child; otherwise
return the parent of the current node.

【在 H*M 的大作中提到】

: traversing a binary search tree is O(1) space? how?
: if recursion ->no
: if iterative, need stack a...

H*M2009-12-14 08:12

6 楼

oh...i forgot to mention...no parent pointer in the Node data structure..

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

: This assumes every node in the tree has a pointer to its parent.
: To find the next ndoe of current node: if the current node has right
: child, return the left-most descendant of the right child; otherwise
: return the parent of the current node.

y*i2009-12-14 08:12

7 楼

你这个算法是 O(nlogn)

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

r*o2009-12-14 08:12

8 楼

what is dsw algorithm?

【在 H*M 的大作中提到】

: that excludes recursion..
: can not think of how to...
: any ideas?
: dsw algorthm by tree rotation?
: Thanks!

H*M2009-12-14 08:12

9 楼

plz google. or I posted a link of the original paper in jobhunting board..

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

: what is dsw algorithm?

z*e2009-12-14 08:12

10 楼

瞟了一眼那个dsw算法，嗯，写paper真的要很能绕...
应该是差不多的做法，你把两个tree都用那个tree_to_vine变成一个基本上sorted的
list，然后就很好merge了，然后剩下就是又用那个vine_to_tree变回到balanced tree
（或者就不管了）。

【在 H*M 的大作中提到】

: plz google. or I posted a link of the original paper in jobhunting board..