2-3棵树，数据存储
大家好，我试图了解 2-3 棵树是如何工作的，我理解了关于键的概念，但是我实际上在哪里存储数据本身，仅在叶子中，或者在具有 1 个键（内部节点）和 2 个键（内部节点）也，提前致谢
hello everyone I'm trying to understand how 2-3 trees work, I understood a concept about keys, but where do I actually store data itself, only in leaves, or in nodes with 1 key (internal node), and 2 keys (internal node) also, thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
有一些例子，数据本身只存储在叶子中，内部节点存储路标（参见 Aho、Hopcroft 和 Ullman 的数据结构和算法）i
数据结构、插入和删除算法是相同的（但细节），虽然所需的空间可能是上面列出的示例的两倍，但树的高度只会增加 1，因此，您仍然拥有非常好的查找时间。
There are examples where data itself is only stored in the leaves, and the internal nodes store signposts (see Data Structures and Algorithms, by Aho, Hopcroft & Ullman)i
The data structure, insertion and deletion algorithms are the same (but for the details), and while the space req'd might be double the examples listed above, the tree's height would only increase by 1, so, you still have the very nice look-up times.
我不是这种树结构的专家，而是维基百科页面上的第一句话 2-3 Trees< /a> 似乎回答了您关于数据存储位置的问题：
在我看来，您将数据存储在树的每个节点中。 Wiki 页面还有一个指向 演示插入的 Java Applet 的链接。
编辑：阅读您的评论并再次查看一些示例代码后，我倾向于认为您的数据和密钥（正如您所说的那样）是同一件事（正如乔利特在他们的答案中提到的那样）。
看看这个示例代码（它们只存储整数）我会创建一个twoThreeNode类，它保存指向您正在存储的数据的指针，确保数据类具有重载的比较运算符以允许对它们进行排序。然后像以前一样遵循算法。
我在这里找到了一篇有趣的文章，带有源代码：平衡树，第 2 部分：内部 2-3 棵树
I'm no expert on this tree structure but the first sentence from the Wikipedia page on 2-3 Trees seems to answer your question about where the data is stored:
Seems to me you store data in each node of the tree. The Wiki page also has a link to a Java Applet demonstrating inserts.
EDIT: After reading your comment, and having another look for some sample code, I'm inclined to think your data and key (as you are calling it) are the same thing (as Chowlett has mentioned in their answer).
Looking at this sample code (they are only storing ints) I would create a twoThreeNode class which holds pointers to the data you are storing, ensuring the data class has overloaded comparison operators to allow them to be sorted. Then follow the algorithm as before.
I found an interesting article, with source code, here: Balanced Trees, Part 2: Interior 2-3 Trees
免责声明：我没有使用过这个数据结构；但维基百科文章非常清楚。
数据作为 1 或 2 个字段存储在每个节点（内部节点或叶子节点）上；我认为您所说的“密钥”正是您要存储的数据。每个有 2 个子节点的内部节点都有一个数据项；该项目大于从其左子项派生的所有项目，并且小于或等于从其右子项派生的所有项目（
left < data <= right）。对于 3 个子节点的情况，数据如下：leftleftleftleftleftleftleftleft data_1 <= 中间 < data_2 <= 右。Disclaimer: I haven't used this data structure; but the Wikipedia article is pretty clear.
The data is stored as the 1 or 2 fields on every node, internal or leaf; I think what you're calling "keys" is exactly the data that you're trying to store. Each internal node with 2 children has a single data item; that item is greater-than all the items descended from its left child, and less-than-or-equal all the items descended from its right child (
left < data <= right). In the case of a 3-child node, the data is such that:left < data_1 <= middle < data_2 <= right.