多路树

多路树是指可以有超过两个子树的树。如果一个多路树最多有 m 个子树，那么这个树被称为 m 阶多路树（或 m 路树）。

与已经研究过的其他树一样，m 阶多路树中的节点将由 m-1 个键字段和指向子树的指针组成。

5 阶多路树

为了让 m 阶多路树的处理更容易，会在每个节点的键上施加某种约束或顺序，从而形成 m 阶多路搜索树（或 m 路搜索树）。根据定义，m 阶多路搜索树是一种 m 路树，应该满足以下条件：

  • 每个节点与 m 个子树和 m-1 个键字段相关联
  • 每个节点中的键按升序排列。
  • 前 j 个子树中的键小于第 j 个键。
  • 后 m-j 个子树中的键高于第 j 个键。

更新日期：2020 年 1 月 3 日

13K+ 次浏览

开启你的职业生涯

完成课程后即可获得证书

开始
广告