例如，我知道 2-3 树和红黑树的概念和思想，但你能告诉我其中一种比另一种更好的情况吗？我应该问自己什么问题？
由于问题不只是关于 2-3 树和红黑树，请随意举出其他自平衡树的示例，我将研究它们。只是想从一般的角度提出这个问题，以便于谷歌搜索其他想知道类似或相同问题的人。
问问题
26 次
1 回答
1
主要考虑因素是插入/擦除的数量与查找的数量。通常选择归结为红黑或 AVL。
AVL 以更复杂的平衡操作为代价保持更严格的平衡。AVL 还需要每个节点更多的信息，但通常可以实现 RB 和 AVL，以便所需的信息隐藏在已经存在的成员中（即在对齐地址分配的缓冲区的低位中）。
请注意，如果您的树不会很大，那么您选择哪种树可能并不重要（甚至根本没有树，如果您只有十几个项目，则列表甚至数组可能都可以）。如果你的树不会有数万棵，那么即使非常粗略的平衡也可能“足够好”。
如果您要在某个较大的节点中处理具有多个值的树（如在 2-3 树中，则使用完整的 b-tree 并使用更大的因子可能更有意义。我只有在通往更有用结构的教学过程中曾经遇到过 2-3 和 2-3-4 树。
于 2020-08-05T19:39:37.867 回答