我正在查看我的数据结构课程中的材料，我对这三种树的使用感到困惑。那么分别在哪些情况下我们应该更好地使用二叉搜索树、2-3树和B-树呢？有什么优点和缺点？
太感谢了！我对数据结构的东西很陌生...
问问题
5426 次
1 回答
3
所有这三个结构都是有序字典的实现——它们维护一个集合，同时有效地支持插入、删除、查找、后继和前驱查询。
二叉搜索树和 2-3 树与 B-tree 的不同之处在于 BST 和 2-3 树（通常）是主存储器数据结构，而 B-树（通常）是外部存储器数据结构。具体来说，B 树被设计为存储在磁盘上，其中读取或写入磁盘页面的成本明显高于执行简单计算的成本。如果您计划存储大量无法放入主内存的数据，那么 B 树是数据结构的绝佳选择。另一方面，在主存中，具有非常大分支因子的 B-tree 将比 BST 或 2-3 树慢，因为每个 B-tree 插入或删除都可能需要大量的指针重新分配。对于确实适合主内存的数据集，
至于 BST 和 2-3 树：“二叉搜索树”不是单一的数据结构。有没有平衡的纯 BST、红/黑树、AVL 树、AA 树、splay 树、treaps、替罪羊树、权重平衡树、RAVL 树等。这些数据结构中的每一个都试图使用一些规则来平衡 BST以便查找、插入和删除快速。2-3 树是 BST 的一种变体，它允许每个节点有多个键，以便为保持平衡提供简单的规则。问题通常不会是“什么时候 BST 比 2-3 树更好，反之亦然”，而是“2-3 树比其他平衡 BST 有什么优势，反之亦然”，这就是问题所在你必须通过分析来弄清楚。
希望这可以帮助！
于 2014-06-09T17:23:53.690 回答