何时选择红黑树而不是 AVL 树？

问：

我知道这个问题经常被问到，但所有的答案似乎都不能让我满意。知道何时选择红黑树而不是 AVL，反之亦然并不像看起来那么容易。为了提供准确的答案，很多因素都在起作用。我找到了两个实际上接近答案的来源：

• https://stackoverflow.com/a/28846533/10061169
• https://codedeposit.wordpress.com/2015/10/07/red-black-vs-avl/

我认为基准测试是一种“好”的方法，但它并不能解释“为什么”我们会看到我们所看到的。到目前为止，我从研究中得出的结论是：

1. 最坏情况

1.1 插入

在红黑树和 avl 树“插入”操作的情况下，“最坏情况”的定义是将数据插入到树的一侧。这意味着数据将按升序或降序插入。

在红黑树中插入 7 个节点时，这意味着在最坏的情况下：

• 旋转、颜色翻转、旋转、颜色翻转、旋转（使用 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 进行可视化）

在 AVL 树中插入 7 个节点时，这意味着在最坏的情况下：

• Ratation， Rotation， Rotation， Rotation （使用 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 进行可视化）

此外，在插入第 7 个节点时，红黑树必须比 AVL 树多比较 1 个节点，这意味着搜索需要更长的时间。

为了得出哪棵树对插入操作具有最佳时间复杂度（在最坏情况下），必须将“权重”因子添加到与数据集大小相关的旋转、颜色翻转和搜索操作中：

• 当数据集较小时，重新平衡（=旋转和颜色翻转）的“行为”似乎超过了搜索的“行为”。这是因为树的高度相对较小。
• 当数据集很大时，搜索的“行为”似乎超过了“再平衡”的“行为”。这是因为高度在增长，但再平衡“行为”保持不变。

在这方面，两个来源（堆栈溢出和基准测试的答案）似乎是匹配的。基准测试表明，最初红黑树具有更好的时间复杂度，但是当数据集增长并且搜索变得更加“主导”时，AVL树就会变得“更快”。

1.2 搜索

在红黑树和 avl 树“搜索”操作的情况下，“最坏情况”的定义是，当数据以这样一种方式分布时，它会导致左右子树之间最重的不平衡因子。

搜索红黑树时，这意味着在最坏的情况下：

• 左右子树之间的高度差为 2

当搜索 n 个 AVL 树时，这意味着在最坏的情况下：

• 左右子树之间的高度差为 1

在最坏的情况下，红黑树必须在“搜索”期间进行一次额外的比较。这使得 AVL 树在最坏情况下对较小和较大的数据集进行搜索时“更快”。

在这方面，两个来源（来自 Stack Overflow 的答案和基准测试）似乎匹配。

2. 平均案例

2.1 插入

在红黑树和 avl 树的“插入”操作中，“平均情况”的定义是将数据插入到树的随机一侧。在基准标记的情况下，这意味着使用随机数生成器。

当“插入”红黑树时，这意味着在一般情况下：

• 当在红黑树的左侧或右侧随机“插入”时，颜色翻转的几率会变得更大（与最坏的情况相比）。因此，红黑树中发生的旋转次数会减少。一般来说，与最坏情况相比，再平衡的频率会降低。
• 由于节点更加分散，不平衡的可能性变得更小（与最坏的情况相比）。这意味着“搜索”成为一个不那么“主导”的因素。

当“插入”到 AVL 树中时，这意味着在一般情况下：

• AVL 树只会从随机分布中受益，因为它只有一种再平衡的“方式”。

导致不平衡的随机插入将使 AVL 树旋转，而可能会使红黑树变为颜色翻转。颜色翻转比旋转“便宜”。在插入过程中，“搜索”行为变得不那么相关，因为数据将更多地分布在树的右侧和左侧。也就是说，在红黑树的情况下，左右子树之间高度差为 2 的几率变得更小（与最坏的情况相比）。

在“插入”操作的平均情况下，红黑树比 AVL 树“更快”，并且与数据集中的元素数量无关。基准与此声明一致。但是，https://stackoverflow.com/a/28846533/10061169 没有。

2.2 搜索

在红黑树和AVL树“搜索”操作的情况下，“平均情况”的定义是节点随机分布在左右树之间。在基准标记的情况下，这意味着使用随机数生成器。

随着数据以更加分散的方式插入，不平衡的可能性将减少。这意味着与最坏的情况相比，红黑树的高度差可能会减少 2。由于红黑树中的“极端”不平衡将不那么频繁地出现，因此 AVL 和红黑树在平均情况下的“搜索”操作将执行相同的操作。

基准测试似乎与 AVL 和红黑树在“搜索”操作的平均情况下表现相同。但是，堆栈溢出帖子不会。它指出 AVL 树在“搜索”方面总是更快。

问题：

1. 我似乎不清楚的是，为什么在最坏的情况下，红黑树对于“插入”操作来说更快？即，为什么红黑树中的 2 次颜色翻转和 1 次附加比较比 AVL 树的 1 次旋转快？
2. 基准显示，在“插入”操作的平均情况下，红黑树比 AVL 树“更快”。但是，https://stackoverflow.com/a/28846533/10061169 表明，对于较大的数据集，情况并非如此。这是否意味着 stackoverflow 的答案没有考虑平均情况，或者我遗漏了什么？
3. 基准标记显示，在“搜索”操作的平均情况下，红黑树和 AVL 树表现相似。但是，https://stackoverflow.com/a/28846533/10061169 不同意。这是否意味着 stackoverflow 的答案没有考虑平均情况，或者我遗漏了什么？
4. 有没有人在平均和最坏情况下都有“删除”操作的 AVL 与红黑树基准？