使用不同数据结构实现std::set

Question

受到这个问题的启发：为什么 std::set 不直接称为 std::binary_tree？我想出了自己的一个。红黑树是满足

std::set

要求的唯一可能的数据结构还是还有其他的？例如，另一种自平衡树 - AVL 树 - 似乎是一个很好的替代品，具有非常相似的特性。理论上是否可以替换

std::set

的底层数据结构，或者是否存在一组要求使得红黑树成为唯一可行的选择？

Answer 1

在大多数现实情况下，AVL 树的性能比 RB 树差（不要与渐近复杂度混淆）。您可以将

std::set

基于 AVL 树并完全符合标准，但它不会为您赢得任何客户。

Answer 2

凡是满足AssociativeContainer要求的数据结构都可以用来实现

std::set

容器。二叉搜索树（BST）通常是更合适的数据结构类别，特别是红黑树提供了最好的权衡。

红黑树确保对数时间的插入、擦除和搜索操作以及恒定时间的旋转操作。另一方面，AVL 树可能需要对数时间旋转操作。此外，由于平衡要求不太严格，因此必须执行的重新平衡次数较少。这取决于结构的最大高度，红黑树为 2 logN，AVL 树为 ~1.44 logN，其中 N 表示节点数。

	AVL树	红黑树
最大高度	~1.44 logN	2 logN
旋转	O(logN)	O(1)

但是，自 2009 年以来，可以使用另一种数据结构，WAVL 树。

它的设计结合了红黑树和AVL树的一些最佳特性。 WAVL 树中的每个插入、擦除和搜索操作都涉及遵循单个路径并为路径中的每个节点执行恒定数量的步骤。

最有趣的功能是它能够根据执行的插入和擦除操作的数量改变平衡要求：如果树仅由插入构建，则最大高度限制为~1.44 logN，因此该结构允许更高效搜寻行动；如果对树同时进行插入和删除，则最大高度放宽至2 logN，因此该结构允许更有效的修改操作。通过这种方式，树会自动适应对用例来说可能更有效的需求。

旋转操作始终是恒定时间的。此外，它们的效率比红黑树稍高一些。

	WAVL 树	红黑树
最大高度	~1.44 logN / 2 logN	2 logN
旋转	O(1)	O(1)