知识卡片

普通读书笔记卡 · 5654.d.1.e.3

搜索树按全子树范围排除

理解等级:中级

二叉搜索树对每个节点要求左子树所有值小于它、右子树所有值大于它,并且子树也遵守相同规则。查询比较当前值后只向可能包含目标的一侧继续。

这比仅比较两个直接孩子更强;每次排除一侧不保证排除一半节点,只有高度受控时才有对数路径。原书此实现不接受重复键,别的多重集合设计可以另定规则。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      若cur.val < num ,说明目标节点在cur 的右子树中,因此执行cur = cur.right ‧ 若cur.val > num ,说明目标节点在cur 的左子树中,因此执行cur = cur.left ‧ 若

    参考来源

    - 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[3734,3844)) - 结论依据:实际搜索比较/定义与重复节点处理,强调全子树不变量及高度条件。 - 原始内容:若cur.val < num ,说明目标节点在cur 的右子树中,因此执行cur = cur.right ‧ 若cur.val > num ,说明目标节点在cur 的左子树中,因此执行cur = cur.left ‧ 若