这棵树的名字是什么？

我正在寻找这个简单的树的名字，这是一个非常简单的二叉搜索树的泛化。这棵树的名字是什么？

这是描述。树的每个节点都有固定数量的最大密钥MI和最小数量的密钥数量为1的密钥。每个节点都有MI + 1个子节点的外部链接，或多或少像一棵B树。子节点只包含父节点的两个临近键的间隔中的键，同样也像B树一样。

不同之处在于插入和删除是如何工作的。

插入：

我们从根开始。

如果我们正在检查节点中有空间，因为它没有MI密钥，所以它没有满，我们将我们的密钥添加到正确的位置。

如果节点已满，我们检查孩子。如果这个范围内没有孩子，我们只用我们的钥匙创建一个。等等。

删除：

上删除，如果我有一个节点实例“ACE”，我需要删除“E”，但在“C”和“E”之间的间隔有一个孩子，我得到了孩子的最大元素，并将其替换为“E”（我可能需要在这里递减，因为移除元素可能需要将另一个元素从孩子移到父母）。它比这更复杂一点，但通常需要将子元素从子项移动到拥有已删除键的节点。

我知道这是非常非正式的指定，但我无法找到似乎是一个二叉树的普遍化的名称。

来源

2011-01-28 antirez

你说一个节点可以有MI密钥，但是你在插入时提到了“孩子”。请说明如何选择儿童作为其重要信息。 – marcog 2011-01-28 14:30:14

@margoc：我想我已经提到过，如果当前节点已满，我们会转到在由我们已有的两个键定界的范围内链接的子项。因此，如果MI是4，并且我已经在根节点“A C M Z”中，并且我要添加“E”，我创建了尝试去A-C范围内链接的子节点。如果没有，我创建它。 – antirez 2011-01-28 16:00:35

我认为你的算法是针对非自平衡的“多路树”。看看here。

B树因此是一个自平衡的变体。术语不完全一致。维基百科使用相同名称的感觉是不同的（相当于多元），但我已经在足够多的地方看到了上述解释。

来源

2011-01-29 11:47:03 simeonz

也许这是k-ary tree。

来源

2011-01-28 12:45:47

它肯定是K-tree树，但这是一个通用术语，我认为，问题在于理解我描述的插入/删除算法是否被视为特殊树。 – antirez 2011-01-28 16:01:20

这棵树的名字是什么？

回答

相关问题