知识卡片

普通读书笔记卡 · 1292.g.1.b.1.j · 生成模型:未记录

二叉查找树用键约束子树

理解等级:中级

每个节点的左子树和右子树按键分别位于节点两侧;重复键应约定放置规则或单独计数。查找沿比较结果向左或向右,成本与树高成正比。平衡时高度 O(log n),按有序键依次插入普通树可能退化为链,高度 O(n)。

二叉查找树的节点可以只有一个子节点或没有子节点,书中“每一个内部节点都有两个子节点”不是普遍要求。

134指出元素可含多个属性并选其中键进行查找;若键不唯一,需定义覆盖、计数或返回多个元素等语义。

135图03267平衡例子与03268链状例子含相同键,结构不同导致查找路径不同。书中“每个节点恰有两个子节点”既排除了叶子也不足以定义高度平衡;满二叉树、完全二叉树与高度平衡各有不同条件。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      二叉查找树 在内存中进行二分查找的效率我们已经看到了,非常高效。但是,当查找集合频繁地变动时,二分查找的效率退化得非常严重。如果需要处理动态的数据集合,我们需要采用一种不同的数据结构来得到可以接搜的查找性能。 要存储动态的查找数据集合的话,查找树可能是最常用的数据结构了。无论是在内存中还是在二级存储

    • · 查看原书依据

      输入和输出和二分查找的一样。集合C中每一个元素e都将被存储到查找树中,并且这些元素都需要有一个或者更多的属性能够作为键值,这些键值决定了全集U。元素也必须有能够区分它们的属性。查找树将会存储C中的元素。

    • · 查看原书依据

      二叉查找树性质(Cormen等,2001)。图5-8给出了一棵二叉树的例子。每一个节点都有一个整数键值,唯一的区分节点。你可以看到在图5-8的树中寻找一个键值只需要从根节点开始,最多探测3个节点。这棵树是完全平衡的。也就是说,每一个节点恰好有两个子节点。一棵完全平衡二叉树有2n-1个节点。 图 5-

    参考来源

    - 位置:《算法技术手册》第5章《二叉查找树》(spine1553;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1516.html;u133-ch05-011)。 - 结论依据:133全文及135的03267–03268平衡与退化图对照实读。 - 原始内容:二叉查找树 在内存中进行二分查找的效率我们已经看到了,非常高效。但是,当查找集合频繁地变动时,二分查找的效率退化得非常严重。如果需要处理动态的数据集合,我们需要采用一种不同的数据结构来得到可以接搜的查找性能。 要存储动态的查找数据集合的话,查找树可能是最常用的数据结构了。无论是在内存中还是在二级存储 - 位置:《算法技术手册》第5章《输入/输出》(spine1553;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1516.html;u134-ch05-011)。 - 结论依据:134指出元素可含多个属性并选其中键进行查找;若键不唯一,需定义覆盖、计数或返回多个元素等语义。 - 原始内容:输入和输出和二分查找的一样。集合C中每一个元素e都将被存储到查找树中,并且这些元素都需要有一个或者更多的属性能够作为键值,这些键值决定了全集U。元素也必须有能够区分它们的属性。查找树将会存储C中的元素。 - 位置:《算法技术手册》第5章《使用环境》(spine1554;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1517.html;u135-ch05-011)。 - 结论依据:135图03267平衡例子与03268链状例子含相同键,结构不同导致查找路径不同。书中“每个节点恰有两个子节点”既排除了叶子也不足以定义高度平衡;满二叉树、完全二叉树与高度平衡各有不同条件。 - 原始内容:二叉查找树性质(Cormen等,2001)。图5-8给出了一棵二叉树的例子。每一个节点都有一个整数键值,唯一的区分节点。你可以看到在图5-8的树中寻找一个键值只需要从根节点开始,最多探测3个节点。这棵树是完全平衡的。也就是说,每一个节点恰好有两个子节点。一棵完全平衡二叉树有2n-1个节点。 图 5-