知识卡片
搜索树以全子树键序缩小范围
二叉搜索树让左子树键小于当前键、右子树键大于当前键,本章不允许重复键。查找从根比较,目标更小只需进左子树,更大只需进右子树,相等命中;到NULL仍无匹配则不存在。
插入也按同样规则一路定位到空分支,否则后续查找的方向就不可靠。02864找15按20→9→15,插65按20→53→79后挂到79左边。键序约束涵盖整棵子树,不只是紧邻孩子间的比较。
这个不变量不同于基本二叉树的任意左右插入;绕过搜索接口随意挂节点可能破坏它。保存中的键也不能任意改成不符合原位置的值。
168的02888中x在44右子树且49左子树,需44;键序来自全祖先路径。插入导致失衡是高度变化,不是某个合法值从此无法按键序插入。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 搜索树以全子树键序缩小范围
- · 问与答
原书出处 · 2 处
- · 查看原书依据
查询一个结点,从根结点开始一层一层往下查找,直到找到目标结点为止。当遇到一个比目标结点值大的结点时,顺着该结点的左子树继续查找。如果遇到的结点值小于目标结点,则顺着该结点的右子树继续查找。例如,要找出图9-7所示的树中值为15的结点,从根结点开始并往其左子结点移动,因为15比20要小。然后移动到结点
- · 查看原书依据
大于44且小于49。因为按照二叉树的定义,49的左子结点的值必须小于49。另一方面,在44的右子树中的结点其值又必须大于44。 图 9-14 二叉搜索树,x为待插入结点的位置
参考来源
- 位置:《算法精解:C语言描述》第9章《二叉搜索树介绍》(spine1297;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1264.html;u158-ch09-016)。
- 结论依据:158查找和插入全部说明及02864整树路径图实读,按图核对15/65路径,不只摘二叉树名称。
- 原始内容:查询一个结点,从根结点开始一层一层往下查找,直到找到目标结点为止。当遇到一个比目标结点值大的结点时,顺着该结点的左子树继续查找。如果遇到的结点值小于目标结点,则顺着该结点的右子树继续查找。例如,要找出图9-7所示的树中值为15的结点,从根结点开始并往其左子结点移动,因为15比20要小。然后移动到结点
- 位置:《算法精解:C语言描述》第9章《问与答》(spine1306;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1273.html;u168-ch09-016)。
- 结论依据:168的02888中x在44右子树且49左子树,需44<x<49;键序来自全祖先路径。插入导致失衡是高度变化,不是某个合法值从此无法按键序插入。
- 原始内容:大于44且小于49。因为按照二叉树的定义,49的左子结点的值必须小于49。另一方面,在44的右子树中的结点其值又必须大于44。 图 9-14 二叉搜索树,x为待插入结点的位置