知识卡片
搜索树按全子树范围排除
二叉搜索树对每个节点要求左子树所有值小于它、右子树所有值大于它,并且子树也遵守相同规则。查询比较当前值后只向可能包含目标的一侧继续。
这比仅比较两个直接孩子更强;每次排除一侧不保证排除一半节点,只有高度受控时才有对数路径。原书此实现不接受重复键,别的多重集合设计可以另定规则。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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 ‧ 若