[WTB]67mm CPL# PhotoGear - 摄影器材
f*m
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？
请各位指点。
对于下面的树([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？
请各位指点。
