问题标签 [2-3-tree]

有人可以告诉我使用 AVL 是否比使用 2-3 树更可取，反之亦然，为什么会这样？

谢谢

我正在使用 SWI Prolog 学习 Prolog，我对 Prolog 中2-3 字典的实现如何工作有一些疑问。

我知道2-3 字典的理论是树，其内部节点可以生成 2 或 3 个具有以下属性的子树：

1）所有的物品都存放在叶子里，按照从小到大的顺序排列

2）所有叶子都在同一级别

3）内部节点不包含插入的项目，但包含以下列方式指定子树的最小元素的标签：

• 如果内部节点有 2 个子树，则该内部节点中的标签包含其 RIGHT SUBTREE 的 MINIMAL ELEMENT（因此，如果我正在搜索小于标签的项目 X，则我确定它在左子树中）
• 如果内部节点有 3 个子树，则该内部节点中的标签包含 2 个值：M2 和 M3，其中 M1 是存在于中心子树中的最小值，而 M3 是作为右子树的最小值

因此，搜索此类字典中是否存在项目非常简单。

插入更复杂，我已经理解它的理论，但我对 Prolog 的解释有一些问题。

这是我的程序（取自 Ivan Bratko 的书：人工智能编程）：

在这个实现中，我有：

• l(X) rappresent 一个存在于我的树中的项目
• n2(T1,M,T2)表示具有 2 个子树 T1 和 T2 的树，其中 M 是 T2 中的最小元素
• n3(T1,M2,T2,M3,T3)** 表示具有 3 个子树的树：T1,T2,T3 其中 M2 是 T2 中的最小元素，M3 是 T3 中的最小元素

第一个疑问与add23和ins谓词之间存在的关系有关，这些：

正如评论中所写，我认为第一个与新树不会向上生长的情况有关（例如，我有一棵有 2 个子树的树并插入了一个新项目，我正在创建一个新的子树它的叶子在所有其他叶子的同一级别（因此内部节点现在将有 2 个标签）对吗？

所以在逻辑上我可以把它读成：如果ins(Tree, X, Tree1)谓词是 TRUE 那么我将 X 添加到 Tree 生成新 Tree1 ，它与旧 Tree 具有相同的高度但包含 X 项（所以它必须有一个内部节点有 3 个孩子）

第二种情况与我有一棵树的情况有关，我必须在一个已经有 3 个子树的节点中插入一个新项目，所以我必须将旧树拆分为 2 棵树，作为根，两者都作为标签 a单个标签取自旧原始节点的 2 个标签。所以我可以将新项目作为叶子和新树的新根插入。

所以在逻辑上我可以把它读成：

如果谓词ins(Tree, X, T1, M2, T2)为 TRUE，则意味着谓词为 TRUE：add23(Tree, X, n2( T1, M2, T2))

在这种情况下，我将具有3 个子树的原始树 Tree 拆分为两个不同的树：T1 和 T2，它们作为根有一个节点，该节点具有从原始树的旧根获取的单个最小标签。

所以碰巧我肯定会有这些树中的一棵有两个子树，而另一棵有一个子树，所以我可以将新插入的项目添加到这个子树中，并将它用作增加的新树的新根高一级。

这样对吗？我不确定这...

在这本书中，我找到了对ins谓词的三种具体情况的解释，我对它的工作原理有很多疑问：

情况1：

这种情况说我原来的树 Tree是：n2(T1, M , T2)并且我将 X 插入到 Tree 中，这是一棵只有2 个子树的树：T1 和 T2。

M是右子树的最小元素

因此，如果gt(M, X)为 TRUE，则意味着 M>X，因此这意味着 X 可能是成为NT1的左子树（为什么？这可能取决于旧的 T1 在它的一个中只有 1 个叶子）子树？），所以最后，原始树变成了n2(NT1, M, T2)

我认为这种情况很简单

案例二：

在这种情况下，我说原始树 Tree是：n2(T1, M , T2)并且我将 X 插入到 Tree 中，这是一棵只有2 个子树的树：T1 和 T2。

M是右子树的最小元素

如果 M>X 为 TRUE，则谓词为 TRUE：ins(T1, X, NT1a, Mb, NT1b)

这意味着我将 T1 拆分为 2 个子树 NT1a 和 NT1b，将第三个子树添加到成为n3(NT1a, Mb, NT1b, M, T2)的原始树中

好的，这很清楚，但我的问题是：在完整的代码中，这个谓词必须满足什么？我在做混乱...

案例 3：

这种情况是原始树 Tree 有 3 个子树，当我必须插入它时，我必须将原始树分成两棵树（n3（T1，M2，T2，M3，T3）和 n2（NT1a，Mb , NT1b)) ，将新项 X 插入这些子树之一，并使用第二个子树的最小元素作为左子树的根作为新树的根（现在高于一个级别）

我的疑问是：在前一种情况下，NewTree是n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)

所以 M2（右子树的最小元素）是新的根，因为 M2>X 是真的？

你能给我一些提示来更好地理解这些东西吗？

我的班主任给了我一个问题，要求我在 2-3 树中执行插入操作。

我做的是上层方法。而他想要的是下面的方法。你能告诉我哪种方法是正确的，因为我在网上查看过，我可以在那里看到这两种方法。但是我还是不知道为什么我掉了10分！提前感谢您的帮助。

我有一个二叉搜索树，我为节点创建了一个结构，它代表一个元素和它左边的孩子，但是，我无法弄清楚如何检查它是否是一个 2 节点的机制，一个元素和两个孩子或者如果它是 3 个节点，有两个元素和三个子节点。有人可以给我一个提示吗？

这是我的 BNode 模板类

I have a 2-3 tree with the following node structure:

The problem is I don't know how to parse the whole tree. I know how we search for it because you simply go to the right path. But how to I get to check all the nodes in the tree?

我试图找出具有 n 个叶子的 2-3 树中的最小和最大节点数是多少。

我试过用 inf\sup 阻止它，但我不能更进一步，2-3 树中的节点数大于完整 AVL 树中的节点数。

提前致谢

我被分配了创建一个 2-3 搜索树的任务，该树应该支持几个不同的操作，每个操作都分为任务的不同阶段。对于第 1 阶段，我应该支持操作 get、put 和 size。我目前正在尝试实现 get 操作，但我被卡住了，我无法思考如何继续，所以我质疑我编写的所有代码，并且觉得需要其他人的输入。

我已经查看了如何开发 2-3 搜索树，但我发现很多代码对我来说毫无意义，或者它只是没有做我需要它做的事情，我想尝试为我的从头开始，我们现在就在这里。

我的节点类

我的树创建类

我可以告诉自己的是，我需要找到一种方法来绑定values[]每个键，但我不知道如何做。可能是睡眠不足，或者我陷入了这种思维方式。

好的，所以我的思维方式又出现了一些问题（这次我病了）。我需要将一个 .txt 文件实现到一个 2-3 树中，我已经为此奠定了基础。

我的节点类

我的树班

还有我的司机课

因此，对于我的分配，每个单词words都是 1 个键，keyValue1[0]出现次数 = 索引，words并且keyValue1[1]是出现次数。所以我的想法是，对于 in 中的每个单词，words我将它添加到一个节点并将索引号添加为第一个值，然后我将这个单词添加到usedWords并检查该单词在words. 我唯一坚持的是如何将它添加为节点并尝试对其进行排序，并将之前出现的较大节点作为它的父节点。

所以我很难在 2-3 树中找到正确的祖先。在任意高度的 2-3 树中，有几种情况需要寻找。

我的节点设计如下：

是否有算法或类似的东西来找到节点的正确祖先？

例如，假设我们正在寻找 H 的祖先（提供的树的底部），从视觉角度来看，很明显 H 的祖先是树根处的 H。但这需要跳上 4 个父链接。树可能是任意大小，这是问题所在。

我最终的目标是创建一个按顺序遍历 2-3 树的迭代器。查找祖先节点的目的是，祖先节点将成为其父节点的右孩子叶节点的有序后继。同样，如上面提供的示例所示。

我不知道如何处理算法。我在想这样的事情：

有人有更好的主意吗？