知识卡片

普通读书笔记卡 · 3640.c.1.a

区间搜索沿单路径下降

理解等级:中级
  • 查找相交区间时,若当前区间不相交,且左子树存在、其最大右端点不小于查询左端点,就向左走;
  • 否则向右。

每步只检查一个节点,红黑树高度保证 O(lg n);找到任一交集即返回。

这张卡片看不懂?

已有反馈 · 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