M路搜索树

Question

我想实现一个m路搜索树，我需要实现m路搜索树的基础知识。任何人都可以提供给我很好的资源，这将有助于我实现相同的目标？

Answer 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教科书有一整章致力于该结构，这将成为算法细节的绝佳资源。

希望这会有所帮助！

Answer 2

也许你想寻找一个三元树？三元树是一种类似数据结构的树，但是像一个帕特里夏树或者一棵暴击树，它使用B树作为类型或树模型。卡丁车赛车也是一个很好的起点。