我又开始研究数据结构了。我发现它的实际用途很少。其中之一是关于磁盘上的文件系统。有人能给我更多关于 m-way tree 实际用途的例子吗?
问问题
3005 次
2 回答
9
M-way树出现在很多领域。这是一个小样本:
- B树:这些是搜索树,例如具有巨大分支因子的二叉搜索树。它们的设计方式使得每个节点都可以放入内存中,可以一次从硬盘读取。它们具有常规 BST 的所有相同的渐近保证,但旨在最小化搜索节点以找到特定元素的数量。因此,许多大型数据库系统使用 B 树或其他相关结构将大型表存储在磁盘上。这样,昂贵的磁盘读取次数被最小化,整体效率更高。
- 八叉树。八叉树及其二维表亲四叉树是用于在三维空间中存储点的数据结构。它们在视频游戏中被广泛用于快速碰撞检测和实时渲染计算,如果没有它们,我们会变得更糟。
- 链接/砍树。这些专门的树用于网络流问题,以比传统方法更有效地计算匹配或找到最大流,这在运筹学中具有巨大的适用性。
- 不相交的森林。这些多路树用于最小生成树算法,以快速计算连通性,将运行时间优化到理论极限附近。
- 尝试。这些树用于对字符串数据进行编码,并允许对字符串集进行极快的查找、存储和维护。它们也用于一些正则表达式游行者。
- Van Emde Boas Trees - 一种闪电般快速的整数优先级队列实现,由具有巨大分支因子的树木森林支持。
- 后缀树。文本处理世界的这些宝石允许快速字符串搜索。它们通常还具有远大于二的分支因子。
- PQ-树。这些用于编码排列的树允许进行线性时间平面性测试,这在电路布局和绘图中具有应用。
呸!那是很多树。希望这可以帮助!
于 2011-02-02T10:23:20.110 回答
0
通过m-way,您是指广义树吗?如果是这样,几乎任何“单亲”层次结构。
于 2011-02-02T10:23:47.393 回答