在选择自平衡BST类型时，需要考虑哪些决策？

Question

例如，我知道2-3树和红黑树的概念和想法，但你能给我一些情况，他们中的一个比另一个更好吗？我应该问自己什么问题？

由于问题不仅仅是关于2-3树和红黑树，请随意给出其他自平衡树的示例，我将对它们进行研究。我只是想从一般的角度来问这个问题，以便其他想知道类似或相同问题的人可以很容易地用谷歌搜索。

Answer 1

主要考虑的是插入/擦除的数量与查找的数量。通常情况下，选择要么是红黑，要么是AVL。

AVL以更复杂的平衡操作为代价来维持更严格的平衡。AVL还需要每个节点多一点的信息，但是RB和AVL通常都可以被实现，使得所需的信息被隐藏在已经存在的成员中(即，在分配在对齐地址处的缓冲器的低位中)。

请注意，如果你的树不是很大，那么你选择哪一棵树可能并不重要(或者甚至一棵树，一个列表甚至数组，如果你只有12个项目，可能就很好了)。如果你的树不是数万棵，即使是非常粗糙的平衡也可能是“足够好”的。

如果你打算在一个较大的节点中使用多个值的树(就像在2-3树中一样)，那么使用一个完整的b树并使用更大的因子可能会更有意义。在构建更有用的结构的过程中，我只遇到过2-3和2-3-4树。