知识卡片

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

左侧最大值不足可安全右行

理解等级:高级

若左子树为空,或它的最大右端点小于查询区间左端点,左侧每个区间都完全在查询区间左边,不可能相交。区间搜索因此能安全放弃左子树,转向右侧。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[30000,35000))。 - 结论依据:定理17.2用子树最大值的不等式证明右行时不会遗漏左侧交集。 - 原始内容:i ′. high ≤ x . left . max < i . low . By the interval trichotomy, therefore, intervals i and i ′ do not overlap, and so x ’s left subtree contains no interval that overlaps i .