问2-3棵树，数据存储

EN

我不是这种树结构的专家，但是2-3 Trees上维基百科页面上的第一句话似乎回答了你关于数据存储位置的问题：

计算机科学中的2-3树是一种数据结构，其中每个带子节点(内部节点)都有两个子节点和一个数据元素(2节点)或三个子节点和两个数据元素(3节点)。

在我看来，您将数据存储在树的每个节点中。维基页面也有一个指向Java Applet demonstrating inserts的链接。

编辑:在阅读了您的评论，并重新查看了一些示例代码后，我倾向于认为您的数据和键(正如您所说的)是一样的(正如Chowlett在他们的答案中提到的那样)。

查看这个sample code (它们只存储整数)，我会创建一个twoThreeNode类，它保存指向您要存储的数据的指针，确保数据类具有重载的比较运算符以允许对它们进行排序。然后像以前一样遵循算法。

我在这里找到了一篇有趣的文章，里面有源代码：Balanced Trees, Part 2: Interior 2-3 Trees

有些例子中，数据本身只存储在树叶中，而内部节点存储路标(参见Aho，Hopcroft &Ullman所著的data Structures and Algorithms )i

数据结构、插入和删除算法是相同的(但对于细节而言)，虽然所需的空间可能是上面列出的示例的两倍，但树的高度只会增加1，因此，您仍然有非常好的查找时间。

免责声明:我没有使用过这种数据结构；但是Wikipedia article非常清楚。

数据被存储为每个节点、内部节点或叶节点上的1或2个字段；我认为您所说的“键”正是您试图存储的数据。每个具有两个子节点的内部节点都有一个数据项；该项大于其左子节点的所有项，并且小于或等于其右子节点(left < data <= right)的所有项。对于3个子节点，数据是这样的：left < data_1 <= middle < data_2 <= right。