红黑树
1. 二叉查找树
1.1 特征
左子树上所有节点均小于或等于他的根节点的值
右子树上所有节点均大于或等于他的根节点的值
左右子树也一定分别为二叉查找树
1.2 时间复杂度
二叉查找树增、删、查时间复杂度在O(Log2n)到O(n)之间。
如果二叉排序树是平衡的，近似于折半查找，其查找效率为O(Log2n)。
如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。
为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。
初始状态：
查找：
1.3 缺点
如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。
2. 平衡二叉树
2.1 定义和特征
平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
-
左右两个子树都是一棵平衡二叉树。
这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
805461-20160127214903223-1113949071 (1).jpg
2.2 自平衡
平衡二叉树能自平衡，依靠左旋、右旋两种操作。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
2.3 缺点
频繁旋转会使插入和删除牺牲掉O(logN)左右的时间。
3. 红黑树
3.1 定义和特征
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
- 性质1：每个节点要么是黑色，要么是红色。
- 性质2：根节点是黑色。
- 性质3：每个叶子节点（NIL）是黑色。
- 性质4：每个红色结点的两个子结点一定都是黑色。
- 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质5又可以推出：
- 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点
红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。
3.2 自平衡
红黑树能自平衡，依靠左旋、右旋、变色三种操作。
变色：结点的颜色由红变黑或由黑变红。
红黑树总是通过旋转和变色达到自平衡。
并且红黑树增、删、查时间复杂度均为O(Logn)。
3.3 优点
跟别的平衡树比，可以通过变色，少做几次旋转。
节点的红、黑色使得红黑树的平衡不用太过严格，只需要黑色层数平衡即可。
每一个红黑树也是一个特化的二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。
恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次 。
红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。
3.4 红黑树和平衡二叉树的比较
红黑树与AVL的比较：
- 平衡的严格性
平衡二叉树为强严格，要求左右两棵子树的高度差的绝对值不超过1。
由此得出平衡二叉树从根到叶子的最长的可能路径不多于最短的可能路径+1。
红黑树为弱严格，只要求每个叶子结点的路径都包含数量相同的黑结点，即要求每棵子树的黑色节点层数相同。
由此得出，红黑树的从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
因为性质4导致了路径不能有两个毗连的红色节点就。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
- 自平衡方式
平衡二叉树的自平衡方式是左旋或右旋。
红黑树的自平衡方式是变色、左旋或右旋。
通过变色可以少做几次旋转。
AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
3.5 查找
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异。
3.6 插入
插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。
查找插入的父结点很简单，跟查找操作区别不大。
插入位置已经找到，把插入结点放到正确的位置就可以啦，但插入结点是是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。
3.7 插入案例
例如上面标准的红黑树，插入值为21的节点：
下面展示的是红黑树的部分：
插入节点21：
为了符合红黑树的规则，会把节点红变黑或者黑变红。因为21和22的连接不符合规则4，所以把22红变黑：
这样还是不符合规则5，经过一系列变色。
具体步骤如下：
- (01) 将“父节点”设为黑色
- (02) 将“叔叔节点”设为黑色
- (03) 将“祖父节点”设为“红色
- (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作
得到如下图：
局部的红黑树放到全局仍然不满足红黑树规则：
此时变色已经无法解决问题了，只能通过旋转。
经过旋转、再变色等一系列操作，得到如下图：
