a********r
发帖数: 217 | 1 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
search kth smallest key. inorder traversal似乎不能满足要求。 |
r*******k
发帖数: 1423 | 2 bst额外记一个小于等于当前key的点的个数
也就是左子树的节点个数，就可以了吧
【在 a********r 的大作中提到】
: 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
: search kth smallest key. inorder traversal似乎不能满足要求。
|
a********r
发帖数: 217 | 3 但是树已经是建好的,重建的话至少要O (n)
时间。所以说能不能优化, 整数inorder search的时间是关键。
【在 r*******k 的大作中提到】
: bst额外记一个小于等于当前key的点的个数
: 也就是左子树的节点个数，就可以了吧
|
s**x
发帖数: 7506 | 4
参见 augmented data structure in algorithm introduction, 楼上已给出答案。
I do not think they ask you not modifying the tree.
【在 a********r 的大作中提到】
: 但是树已经是建好的,重建的话至少要O (n)
: 时间。所以说能不能优化, 整数inorder search的时间是关键。
|
r*******k
发帖数: 1423 | 5 不加信息是不可能的啊
如果有n个node，求第n个数，
你不遍历前n-1个数，你怎么知道哪个是第n个？
必然是o(n)啊
想到做lgn，必然不会遍历所有的，
剪枝需要额外的信息
【在 a********r 的大作中提到】
: 但是树已经是建好的,重建的话至少要O (n)
: 时间。所以说能不能优化, 整数inorder search的时间是关键。
|
l*********b
发帖数: 65 | 6 我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
node且bst不是balanced
。。。个人觉得 可能就还是线性时间复杂度吧- - |
r*******k
发帖数: 1423 | 7 要是balanced或者是满的
倒是可以猜猜
否则，普通的bst，必然是线性的
【在 l*********b 的大作中提到】
: 我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
: 大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
: node且bst不是balanced
: 。。。个人觉得 可能就还是线性时间复杂度吧- -
|
b********r
发帖数: 620 | 8 对头。如果BST退化成一个单链表，没法再LOGN里面完成。
【在 r*******k 的大作中提到】
: 要是balanced或者是满的
: 倒是可以猜猜
: 否则，普通的bst，必然是线性的
|
