红黑树与AVL树_avl和红黑树的复杂度

一、在理解红黑树之前，我们先看一下二叉查找树

由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。

二叉查找树特性：

1、左子树上所有的节点的值都小于或等于他的根节点上的值
2、右子树上所有节点的值均大于或等于他的根节点的值
3、左、右子树也分别为二叉查找树

如图：

可以看到如果要查询10的话，10>9

因此到他的右子树，右子树根节点为13，10<13

因此到其左子树，左子树根节点为11>10

到其左子树，为10，找到相应的节点

不过二叉查找树有一些问题，可能会出现不平横的情况，即如下图所示的情况

从这种情况可以看出，明显存在左子树和右子树深度相差过多，在使用平衡情况下的二叉查找树是时间复杂度为O(log n)，而出现这种极端情况的话，想要查9的位置就需要每一次都遍历下一个右子树，很有可能时间复杂度变为O(n)(即与数组普通查询的时间复杂度相同)

基于上述情况，引入了平衡二叉树，红黑树即为平衡二叉树的一种。（红黑树是在二叉查找树的基础之上提出来的）

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。

二、红黑树五大性质：

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。
在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

性质1. 每个节点是红色或黑色。

性质2. 根节点是黑色。

性质3. 每个叶节点是黑色的 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

性质4. 每个红色节点的两个子节点都是黑色。（如果一个节点是红色的，则它的子节点必须是黑色的）(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论的原因。

结果是这个树大致上是平衡的。那么在查找的时候，就不对出现左子树和右子树失衡的情况。但是红黑树并没有AVL数要求的那么严格，AVL树要求左右子树相差不超过1。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

三、下面我们先介绍两个基本操作，旋转。

旋转的目的：将节点多的一支出让节点给另一个节点少的一支，旋转操作在插入和删除操作中经常会用到，所以要熟记。（转）

具体代码实现，参考这个大佬的文章，我们只做概念解释：

https://blog.csdn.net/v_july_v/article/details/6105630
1

其他精选好文章：

https://blog.csdn.net/yang_yulei/article/details/26066409

https://blog.csdn.net/q3244676719/article/details/81540830

https://www.jianshu.com/p/37c845a5add6

https://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
1
2
3
4
5
6
7

2-3-4 Tree(2-3-4树)文章：

https://www.jianshu.com/p/37c845a5add6
1

四、AVL树与红黑树

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

红黑树与AVL树的区别

红黑树旋转操作非常局部化，而且次数极少（插入最多两次旋转，删除最多三次旋转），而改变颜色的操作不会影响到用户对树的query操作（即不要lock），另外很多树，如AVL树，2-3树,2-4树都可以转化成红黑树，红黑树能达到O(logn)高度，但是不像AVL树那样严格要求左右子树高度差必需相差不超过1。可以说RB树是目前为止高度要求最灵活的准平衡BST。准平衡是相对完全二叉树来说的，AVL树(比如Fibonacci树)也不是完美平衡的。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，做一个哈希表，性能可能会更好一些。

红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组（“关联数组”是一种具有特殊索引方式的数组。不仅可以通过整数来索引它，还可以使用字符串或者其他类型的值（除了NULL）来索引它。）。

补充：

1、常见数据结构

线性：数组，链表，队列，堆栈，块状数组（数组+链表），hash表，双端队列，位图（bitmap）
树：堆（大顶堆、小顶堆），trie树（字母树or字典树），后缀树，后缀树组，二叉排序/查找树，B+/B-，AVL树，Treap，红黑树，splay树，线段树，树状数组
图：图
其它：并查集

2、常见算法

（1） 基本思想：枚举，递归，分治，模拟，贪心，动态规划，剪枝，回溯
（2） 图算法：深度优先遍历与广度优先遍历， 最短路径，最小生成树，拓扑排序
（3） 字符串算法：字符串查找，hash算法，KMP算法
（4） 排序算法：冒泡，插入，选择，快排，归并排序，堆排序，桶排序
（5） 动态规划：背包问题，最长公共子序列，最优二分检索树
（6） 数论问题：素数问题，整数问题，进制转换，同余模运算，
（7） 排列组合：排列和组合算法
（8） 其它：LCA与RMQ问题