关于trie和binary search tree的疑问。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于trie和binary search tree的疑问。

关于trie和binary search tree的疑问。# JobHunting - 待字闺中

r*o2010-05-28 07:05

1 楼

我对trie一直不是很懂，
如果要在n个单词中查某个单词(长度为m个字母)的话，
为什么不能把这n个单词组成一个binary search tree呢？这样平均复杂度是O(lgn)。
而用trie查的话复杂度是O(m)。
这样lgn这个问题可能很弱，欢迎拍砖。

X*n2010-05-28 07:05

2 楼

但实际上 m总是有限的, 但n可以无数多, 比如说dictionary
所以一般意义上m远小logn

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

: 我对trie一直不是很懂，
: 如果要在n个单词中查某个单词(长度为m个字母)的话，
: 为什么不能把这n个单词组成一个binary search tree呢？这样平均复杂度是O(lgn)。
: 而用trie查的话复杂度是O(m)。
: 这样lgn: 这个问题可能很弱，欢迎拍砖。

a*d2010-05-28 07:05

3 楼

in binary search tree, each comparison compares entire key.
But for trie, at each node it only compares one bit.
For long key, such as strings, it makes a big difference.
In other word, lg(n) of m character comparison for BST.
O(m) comparison for trie.

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

r*o2010-05-28 07:05

4 楼

谢谢，我没搞明白为什么是lg(n) of m character comparison for BST.
我觉得对于BST就是lg(n)啊.

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

: in binary search tree, each comparison compares entire key.
: But for trie, at each node it only compares one bit.
: For long key, such as strings, it makes a big difference.
: In other word, lg(n) of m character comparison for BST.
: O(m) comparison for trie.

n*02010-05-28 07:05

5 楼

请问怎么把n个单词组成bst？

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

f*52010-05-28 07:05

6 楼

lookup for BST is O(lgn)
but pay attention now u want to compare a word each time,
you need to compare the target word with the word in current node
u need to compare each letter of the word...

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

: 谢谢，我没搞明白为什么是lg(n) of m character comparison for BST.
: 我觉得对于BST就是lg(n)啊.

f*52010-05-28 07:05

7 楼

list to BST with O(n)
please refer to DSW algorithm

【在 n*****0 的大作中提到】

: 请问怎么把n个单词组成bst？

r*o2010-05-28 07:05

8 楼

Thanks a lot!

【在 f*********5 的大作中提到】

: lookup for BST is O(lgn)
: but pay attention now u want to compare a word each time,
: you need to compare the target word with the word in current node
: u need to compare each letter of the word...

n*02010-05-28 07:05

9 楼

如果单词可以放在bst的internal node和leaf node的话
可以根据每个单词的字母排列为node创建一个unique的index
lookup的时候比较node的index就可以了，所以整个过程只需要O(lgn) ，假设树是
balance的
而tire的lookup需要O(m)
所以关键还是单词长度m和单词个数n的关系。
不知道理解的对不对

【在 f*********5 的大作中提到】

: list to BST with O(n)
: please refer to DSW algorithm

b*r2010-05-28 07:05

10 楼

this makes sense

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

f*52010-05-28 07:05

11 楼

大概是这样吧

【在 n*****0 的大作中提到】

: 如果单词可以放在bst的internal node和leaf node的话
: 可以根据每个单词的字母排列为node创建一个unique的index
: lookup的时候比较node的index就可以了，所以整个过程只需要O(lgn) ，假设树是
: balance的
: 而tire的lookup需要O(m)
: 所以关键还是单词长度m和单词个数n的关系。
: 不知道理解的对不对

b*h2010-05-28 07:05

12 楼

如果这个unique的index可以创建，那O（1）不就可以找到了（直接index到一个hash
table里），还要bst干嘛？

【在 n*****0 的大作中提到】

a*d2010-05-28 07:05

13 楼

In BST, it is not always exactly m character comparison, however, the deeper
you go down the tree, more likely you will need to compare more characters.
(strings are more similar)

【在 f*********5 的大作中提到】

n*02010-05-28 07:05

14 楼

嗯用unique的index,用hash table就可以查询了，O(1)就行了。我想的有点多了。。。
不过unique的index还是要handle overflow的问题。

【在 b********h 的大作中提到】

: 如果这个unique的index可以创建，那O（1）不就可以找到了（直接index到一个hash
: table里），还要bst干嘛？