知识卡片
左侧最大值不足可安全右行
若左子树为空,或它的最大右端点小于查询区间左端点,左侧每个区间都完全在查询区间左边,不可能相交。区间搜索因此能安全放弃左子树,转向右侧。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第17章 数据结构的扩张 · 查看原书依据
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.
参考来源
- 位置:《算法导论(第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 .