我想实现一个 m 路搜索树，我需要实现 m 路搜索树的基础知识。任何人都可以为我提供好的资源来帮助我实施同样的事情吗？
问问题
2279 次
2 回答
1
大多数 m 向搜索树通过在每个节点中按排序顺序存储 (m-1) 个键来工作。然后这些值将元素拆分为 m 个区域：在 (m-1) 个键之间有 m-2 个区域，比最左边的键小一个区域，比最大的键大一个区域。例如，四向树中的节点可能如下所示：
1 3 7
x < 1 1 < x < 3 3 < x < 7 7 < x
要实现搜索，您从树的根开始，并将元素与存储在节点中的每个值进行比较。根据它属于哪个组，要么报告找到该节点，要么向下下降到适当的子节点。
插入和删除节点背后的实际机制取决于您使用的多路树的类型，就像在二叉搜索树中插入和删除如何随树的类型（AVL、splay、红/黑等）而变化一样。一个好的起点可能是B-tree，也许是最著名的 m-way 树。著名的 CLRS 教科书有一整章专门介绍结构，这将是算法细节的绝佳资源。
希望这可以帮助！
于 2011-08-19T09:08:02.717 回答
0
也许您想寻找三元树？三叉树是一种类似于 trie 的数据结构，但与 patricia trie 或 crit-bit 树一样，它使用 B-tree 作为类型或树模型。卡丁车也是一个很好的起点。
于 2011-08-19T09:59:53.850 回答