练习: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() 操作来排序并写入数据。为了测试实现,尝试在你的学校的网站上搜索你和朋友的名字。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
B-树是一种常见的数据结构,用于高效地组织和管理大量数据。本文介绍了B-树的基本概念和相关练习,涵盖了B-树的结构、实现和应用。其中包括在内存中保存链接的数量、B-树的可视化、B*-树的启发式分裂、B-树在符号表中的性能比较等内容。通过这些练习,读者可以深入了解B-树的原理和应用,以及对B-树进行性能优化的方法。文章内容涵盖了B-树的基础知识和高级应用,适合对数据结构和算法感兴趣的读者阅读学习。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论