练习：B- 树
Robert Sedgewick Kevin Wayne
6.14 假设在一棵三层树中，总共可以在内存中保存
条链接。每个页中可以保存
条指向内部结点的链接和
条指向外部结点中的链接。在这样一棵树中最多可以含有多少个项（作为、
、
的函数）？
条链接。每个页中可以保存 条指向内部结点的链接和 条指向外部结点中的链接。在这样一棵树中最多可以含有多少个项（作为、、 的函数）？6.15 开发一个 Page 的实现，将 B- 树的结点表示为一个 BinarySearchST 类的对象。
6.16 扩展 BTreeSET 来实现能够关联键和值的 BTreeST 类，并完整支持有序符号表 API，包括 min()、max()、floor()、ceiling()、deleteMin()、deleteMax()、select()、rank() 方法以及接受两个参数的 size() 和 get() 方法。
6.17 编写一个程序，使用 StdDraw 将 B- 树的生长过程可视化，如同正文描述的方式一样。
6.18 在一个有缓存的典型系统中，估计对 B- 树的
次随机查找中，每次查找的平均探查次数。缓存可以将
个最近访问的页保存在内存中（因此无需探查）。假设 远大于。
次随机查找中，每次查找的平均探查次数。缓存可以将 个最近访问的页保存在内存中（因此无需探查）。假设 远大于。6.19 网络搜索。开发一个 Page 类的实现，为了索引网页，用 B- 树的结点表示网页中的文本。用一个文件表示搜索的关键字。从标准输入接受被索引的网页。为了控制规模，接受命令行参数
并将内部结点的数量限制在
内。（在使用较大的 前请联系系统管理员。）使用一个 位的数字来表示内部结点。例如，当 为 4 时，结点名可以是 BTreeNode0000、BTreeNode0001、BTreeNode0002 等。在页中保存成对的字符串。向 API 中添加一个 close() 操作来排序并写入数据。为了测试实现，尝试在你的学校的网站上搜索你和朋友的名字。
并将内部结点的数量限制在 内。（在使用较大的 前请联系系统管理员。）使用一个 位的数字来表示内部结点。例如，当 为 4 时，结点名可以是 BTreeNode0000、BTreeNode0001、BTreeNode0002 等。在页中保存成对的字符串。向 API 中添加一个 close() 操作来排序并写入数据。为了测试实现，尝试在你的学校的网站上搜索你和朋友的名字。公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
B-树是一种常见的数据结构，用于高效地组织和管理大量数据。本文介绍了B-树的基本概念和相关练习，涵盖了B-树的结构、实现和应用。其中包括在内存中保存链接的数量、B-树的可视化、B*-树的启发式分裂、B-树在符号表中的性能比较等内容。通过这些练习，读者可以深入了解B-树的原理和应用，以及对B-树进行性能优化的方法。文章内容涵盖了B-树的基础知识和高级应用，适合对数据结构和算法感兴趣的读者阅读学习。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论