f*********m
发帖数: 726 | 1 interval search算法在该书14.3节（第三版）。
对于下面的树([start，end](maximum end point value in the subtree of the node
))：
[16，21](30)
/ \
[8，9](23) [24，30](30)
/ \ / \
[5，8](8) [15，23](23) [17，19](19) [26，26](26)
若去搜索[22，25]的overlap interval,书上的算法只能找到左边的[15，23]，漏掉了
右边的[24，30]。
书上的算法只保证只找到一个。要找到所有的是不是需要同时搜索左右两个children？
这样复杂度会变成nlogn吧，不如直接做个线性search？
书上是用augmented tree来实现interval tree的，有没有其他形式的interval tree，
可以找到所有的overlap interview? 比如Centered interval tree？
请各位指点。 |
f*********m
发帖数: 726 | 2 请interval大牛们指点。
node
【在 f*********m 的大作中提到】
: interval search算法在该书14.3节（第三版）。
: 对于下面的树([start，end](maximum end point value in the subtree of the node
: ))：
: [16，21](30)
: / \
: [8，9](23) [24，30](30)
: / \ / \
: [5，8](8) [15，23](23) [17，19](19) [26，26](26)
: 若去搜索[22，25]的overlap interval,书上的算法只能找到左边的[15，23]，漏掉了
: 右边的[24，30]。
|
w****x
发帖数: 2483 | 3
node
只能找到一个吧，其实可以找到后删除， 然后再找
【在 f*********m 的大作中提到】
: interval search算法在该书14.3节（第三版）。
: 对于下面的树([start，end](maximum end point value in the subtree of the node
: ))：
: [16，21](30)
: / \
: [8，9](23) [24，30](30)
: / \ / \
: [5，8](8) [15，23](23) [17，19](19) [26，26](26)
: 若去搜索[22，25]的overlap interval,书上的算法只能找到左边的[15，23]，漏掉了
: 右边的[24，30]。
|
f*********m
发帖数: 726 | 4 那复杂度为mlogn,m为overlap的interval数，n为全部interval数。在很多情况下这样
还不如一个一个地和全部Interval比较呢（复杂度总是为n).
【在 w****x 的大作中提到】
:
: node
: 只能找到一个吧，其实可以找到后删除， 然后再找
|
