知识卡片
二叉查找树用键约束子树
每个节点的左子树和右子树按键分别位于节点两侧;重复键应约定放置规则或单独计数。查找沿比较结果向左或向右,成本与树高成正比。平衡时高度 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-