二叉树、2-3树和B-树的用法和优缺点

Question

我正在复习我的数据结构类中的材料，我对这三种树的用法感到有点困惑。那么在什么情况下我们应该分别使用二叉树、2-3树和B-树呢？有什么好处和坏处？

非常感谢!我对数据结构是个新手……

Answer 1

所有这三种结构都是有序字典的实现-它们维护一个集合，同时有效地支持插入、删除、查找、后继和前置查询。

二叉树和2-3树与B-树的不同之处在于，BST和2-3树(通常)是主存储器数据结构，而B-树(通常)是外部存储器数据结构。具体地说，B树被设计为存储在磁盘上，在这些磁盘中，读或写磁盘页的成本明显高于执行简单计算的成本。如果您计划存储大量无法放入主内存的数据，那么B树是数据结构的最佳选择。另一方面，在主存储器中，具有非常大的分支因子的B树将比BST或2-3树慢，因为每次B树插入或删除可能需要大量的指针重新分配。对于适合主内存的数据集，2-3个树和BST通常是更好的选择(尽管有一些研究表明，由于缓存效应，低阶B-树在主内存中的性能优于BST。)

对于BST和2-3树：“二叉树”不是单一的数据结构。有没有平衡的纯BST，红/黑树，AVL树，AA树，展开树，树，替罪羊树，权重平衡树，RAVL树等。这些数据结构中的每一个都试图使用一些规则来平衡BST，以便快速查找、插入和删除。2-3树是BST的变体，它允许每个节点有多个键，以便给出维护平衡的简单规则。问题通常不是“什么时候BST比2-3树更好，或者反之亦然”，而是“2-3树比其他平衡BST有什么优势，反之亦然”，这是您必须通过分析弄清楚的问题。

希望这能有所帮助！