红黑树与 AVL 树的区别

小开

RB 树和 AVL 树都是自平衡的，它们都提供 O (logn)查找和插入性能。区别在于 RB 树保证每个插入操作都有 O (1)旋转，这实际上是真实实现中的性能成本。简单来说，RB 树从概念上来说是2-3棵树而不需要承担动态节点结构的开销，从而获得了这种优势。物理上，RB 树实现为二叉树，红色/黑色标志模拟2-3行为。

根据定义，每个 AVL 都是 Red-Black 的子集。一个应该能够颜色任何 AVL 树，没有重组或旋转，转换成一个红黑树。

小开

从我所看到的来看，AVL 树可以根据需要进行很多旋转(有时是递归地向上) ，以获得所需的 AVL 树的高度(Log n)。这使得它的平衡更加严格。

对于红黑树有5套规则，你需要确保停留通过插入和删除，你可以在这里找到 http://en.wikipedia.org/wiki/Red-black_tree。

可能对红黑树有帮助的主要事情是，根据这五条规则，如果“叔叔”是红色的，那么可以递归地将树的颜色染到根部。如果叔叔是黑人，你将需要做最多两个轮换，以解决任何问题，你有，但在这些一个或两个轮换你做了。收拾行李，说晚安吧因为这就是你需要做的操纵的结束。

大规则是第五条。从给定节点到其后代叶子的每条简单路径都包含相同数量的黑色节点。

这将导致大部分的旋转，你需要使树的工作，这导致树不去太远的平衡。

小开

AVL 树比红黑树保持更严格的平衡。在 AVL 树中，从根部到最深叶子的路径最多为1.44 lg (n + 2) ，而在红黑色树中最多为2 lg (n + 1)。

因此，AVL 树中的查找通常更快，但是这样做的代价是由于更多的旋转操作导致插入和删除速度更慢。因此，如果您希望查找的次数主导树的更新次数，那么可以使用 AVL 树。

小开

AVL 树通常与红黑树进行比较，因为两者支持相同的操作集，并且基本操作需要花费 O(log n)时间。对于查找密集型应用程序，AVL 树比红黑树更快，因为它们的平衡更加严格。类似于红黑树，AVL 树是高度平衡的。对于任何 μ ≤1.2，这两个节点通常都不是权重平衡的，也不是 μ- 平衡的; 也就是说，兄弟节点的后代数量可能有很大的不同。

来自维基百科关于美国吸血鬼联盟之树的文章

小开

树木的最大高度是保持平衡的首要条件。对于 AVL，它几乎等于 1.44 * log(n)，但对于 RB 树，它是 2 * log(n)。因此，当问题是搜索激励问题时，我们可以得出结论，使用 AVL 是更好的。对于 AVL 和 RB 树来说，重要的是另一个问题。RB 树比 AVL 树更适合以较低的旋转代价进行随机插入，而 AVL 树更适合插入升序或降序数据。因此，如果问题是插入激励，我们可以使用 RB 树。

小开

对于小数据 :

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _.

查找 : AVL 树更快，因为 AVL 树具有更少的深度。

Delete : RB 树的最大旋转次数是恒定的，而 AVL 树的最大旋转次数是 O (log N)。RB 树平均旋转次数也较少，因此 RB 树速度较快。

大数据 :

Insert : AVL 树更快。因为您需要在插入之前查找特定的节点。随着数据的增加，查找特定节点的时间差与 O (log N)成正比。但是 AVL 树和 RB 树在最坏的情况下仍然只需要恒定的旋转次数。因此瓶颈将成为您查找该特定节点的时间。

查找 : AVL 树更快

Delete : AVL 树平均速度更快，但在最坏的情况下 RB 树更快。因为您还需要在删除之前查找要交换的非常深的节点(类似于插入的原因)。平均两棵树都有固定的旋转次数。但是 RB 树对于旋转有一个常数上界。

小开

总之: AvlTree 比 RedBlackTree 平衡性稍好一些。对于查找、插入和删除，两个树总共需要 O (log n)时间，但是对于插入和删除，前者需要 O (log n)旋转，而后者只需要 O (1)旋转。

由于旋转意味着向内存写入，而向内存写入代价高昂，所以实际上红黑树的更新速度比 AvlTree 快

小开

为了了解 AVL 树是如何工作的，这个交互式可视化会有所帮助。

AVL 和红黑树都是高度平衡树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作上执行的旋转操作的数量——在 AVL 中更高，以保持总体上更均匀的平衡。

两个实现都可以扩展为 O(lg N)，其中 N 是叶子的数量，但实际上 AVL Tree 在查找密集型任务上更快: 利用更好的平衡性，Tree 遍历的平均时间更短。另一方面，插入和删除方面，AVL 树是比较慢的: 需要更多的旋转才能在修改后适当地重新平衡数据结构。

对于一般用途的实现(例如，事先并不清楚查找是否是主要的操作) ，红黑树是首选的: 它们更容易实现，并且在常见情况下更快——只要数据结构像搜索一样频繁地被修改。例如，Java 中的 TreeMap和 TreeSet使用了一个后台 RedBlack Tree。

小开

事实上，RedBlack 树具有较少的旋转可以使它们在插入/删除时更快，但是... ..。因为它们通常比较深，所以插入和删除的速度也可能比较慢。每次从树中的一个级别转到下一个级别时，都会有一个很大的变化，即请求的信息不在缓存中，必须从 RAM 中检索。因此，较少的旋转所获得的时间可能已经丢失，因为它必须导航更深，因此必须更频繁地更新它的缓存。能否在缓存中进行操作会产生很大的不同。如果相关信息在缓存中，那么您可以在导航额外级别所需的时间内执行多次旋转操作，而下一级别的信息不在缓存中。因此，在理论上 RedBlack 更快的情况下，只查看所需的操作，由于缓存丢失，实际上可能会更慢。