知识卡片

普通读书笔记卡 · 5654.d.1.e.4.o · 生成模型:未记录

搜索树以全子树键序缩小范围

理解等级:中级

二叉搜索树让左子树键小于当前键、右子树键大于当前键,本章不允许重复键。查找从根比较,目标更小只需进左子树,更大只需进右子树,相等命中;到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为待插入结点的位置