红黑树和AVL树之间的区别
有人可以解释这两个数据结构之间的主要区别是什么？ 我一直在试图find一个在线来源，突出差异/相似之处，但我还没有发现任何太多的信息。 在什么情况下会比另一个更受欢迎？ 什么样的实际情况让一个人比另一个“更好”使用？
AVL树比红黑树保持更加刚性的平衡。 在AVL树中从根到最深叶的path最多为〜1.44 lg（n + 2），而在红黑树中最多为〜2 lg（n + 1）。
因此，AVL树中的查找速度通常更快，但这是由于更多的旋转操作而导致的较慢插入和删除的代价。 因此，如果您期望查找数量支配树的更新数量，请使用AVL树。
对于小数据 ：
插入 ：RB树＆avl树具有恒定的最大旋转数，但是由于平均RB树使用较less的旋转，所以RB树将更快。
查找 ：AVL树更快，因为AVL树深度更小。
删除 ：RB树具有恒定的最大旋转数，但是AVL树可以具有O（log N）个旋转次数作为最差。 而平均RB树的旋转次数也较less，RB树更快。
对于大数据 ：
插入 ：AVL树更快。 因为您需要在插入之前查找特定的节点。 因为您有更多的数据，查找特定节点的时间差异会与O（log N）成比例。 但是在最坏的情况下，AVL树和RB树仍然只需要恒定的旋转次数。 因此，瓶颈将成为您查找特定节点的时间。
查找 ：AVL树更快。 （和小数据一样）
删除 ：AVL树平均速度更快，但在最坏的情况下，RB树更快。 因为在删除之前还需要查找非常深的节点来进行交换（类似于插入的原因）。 平均而言，两棵树的旋转次数是不变的。 但是RB树具有恒定的旋转上限。
引用： AVL和红黑树之间的区别
RB树和AVL树都是自平衡的。 它们都提供O（log n）查找和插入性能。 不同的是RB-Trees保证每个插入操作的O（1）旋转。 这实际上是在实际执行中花费性能的成本。 简化的RB树从概念上是从2-3树中获得这个优点，而不会带来dynamic节点结构的开销。 物理RB树被实现为二叉树，红/黑旗模拟2-3行为。
根据定义，每个AVL因此是红黑的子集。 人们应该能够对任何AVL树进行着色，而不用重新调整或旋转，将其转换成红黑树。
树木的最大高度是保持平衡最重要的。 对于AVL，它几乎等于1.44 * log(n) ，而对于RB树，则是2 * log(n) 。 所以我们可以得出这样的结论：当问题是search激励时，使用AVL更好。 重要的是AVL和RB树的另一个问题。 面向以较低成本旋转的随机插入时，RB树比AVL好，但是可以插入升序或降序数据的AVL。 所以如果问题是插入激励，我们可以使用RB树。
经常将AVL树与红黑树进行比较，因为它们都支持相同的一组操作，并将
O(log n)时间用于基本操作。 对于查找密集型应用，AVL树比红黑树更快，因为它们更加严格平衡。 类似于红黑树，AVL树是高度平衡的。 对于任何μ≤½来说，两者通常不是重量平衡的，也不是μ平衡的; 也就是说，兄弟节点可以有很多不同的后代。
从维基百科关于AVL树的文章
根据我所看到的，AVL树看起来像AVL树（Log n）所期望的那样，可以根据需要进行多次旋转（有时recursion上升）。 这使得它更加严格的平衡。
对于红黑树有5组规则，你需要确保通过插入和删除留下，你可以在这里findhttp://en.wikipedia.org/wiki/Red-black_tree 。
主要的事情可能会帮助你的红黑树是这样的事实，即根据这五个规则，你可以recursion着色的树如果叔叔是红色的根。 如果叔叔是黑人，那么你需要做最大限度的两次轮换来解决你所有的问题，但是在你完成了一两轮之后。 打包并说晚安，因为这是你需要做的操作的结束。
大规则是数字5 …'从给定节点到其任何后代叶子的每条简单path包含相同数量的黑色节点'。
这将导致大部分的轮作，使树木工作，并导致树不会失去太多的平衡。
总之：AvlTrees比RedBlackTrees稍好一些。 两棵树的查找，插入和删除的总时间都是O（log n），但是对于插入和删除，前者需要O（log n）旋转，而后者只需要旋转O（1）。
由于旋转意味着写入内存，并且写入内存很昂贵，所以RedBlackTrees实际上比AvlTrees更快地更新
RedBlack树有更less的旋转的事实可以使他们更快的插入/删除，但….。 由于它们通常会更深一点，它们在插入和删除时也会变慢。 每次从树中的一个层次到下一个层次，所请求的信息都不在caching中，并且必须从RAM中检索。 因此，较less旋转所获得的时间可能已经丢失，因为它必须更深入地导航，并且因此必须更频繁地更新其caching。 能够从caching中操作或者不能做出很大的改变。 如果相关信息在高速caching中，则可以执行多轮循环操作，在导航附加级别所需的时间内，下一级信息不在高速caching中。 因此，在RedBlack理论上速度更快的情况下，只考虑所需的操作，由于caching未命中，实际上可能会变慢。
要了解AVL树如何工作， 这种交互式可视化有所帮助。
AVL以及RedBlack Trees是高度平衡的树数据结构。 它们非常相似，真正的区别在于在任何添加/删除操作时执行的旋转操作次数 – 在AVL的情况下更高，以保持整体更均匀的平衡。
这两个实现的规模都是一个O(lg N) ，其中N是树叶的数量，但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。 另一方面，明智的插入和删除，AVL树比较慢：需要更高的旋转次数才能在修改后正确地重新平衡数据结构。
对于通用的实现（即先验，查找是操作的主要部分并不清楚），RedBlack树是首选：它们更容易实现，并且在常见情况下更快 – 无论数据结构的修改频率如何。 例如，Java中的TreeMap和TreeSet使用了一个支持RedBlack Tree。
