知识卡片
区间搜索沿单路径下降
- 查找相交区间时,若当前区间不相交,且左子树存在、其最大右端点不小于查询左端点,就向左走;
- 否则向右。
每步只检查一个节点,红黑树高度保证 O(lg n);找到任一交集即返回。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第17章 数据结构的扩张 · 查看原书依据
INTERVAL-SEARCH(T, i) 1 x = T.root 2 while x ≠ T.nil and i does not overlap x.int 3 if x.left ≠ T.nil and x.left.max ≥ i.low 4 x = x.left // overlap in left subtree or no overlap in right subtree 5 else x = x.right // no overlap in left subtree 6 return x
参考来源
- 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[25000,30000))。
- 结论依据:原文伪代码给出分支条件,并按树高推导查询时间。
- 原始内容:I NTERVAL -S EARCH ( T , i ) 1 x = T . root 2 while x ≠ T . nil and i does not overlap x . int 3 if x . left ≠ T . nil and x . left . max ≥ i . low 4 x = x . left // overlap in left subtree or no overlap in right subtree 5 else x = x . right // no overlap in left subtree 6 return x