1.红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。
实际当中进行搜索一般使用红黑树，和AVL树相比较并不是质的变化。
那么AVL树和红黑树有什么区别呢？
AVLTREE：
- 二叉搜索树
- 每个子树的左右高度不超过1
AVLTREE是严格平衡。
红黑树：最长路径最多是最短路径的2倍。
红黑树是近似平衡。
那为什么近似平衡比严格平衡好呢?
考虑最坏情况，AVLTREE查找
l
o
g
(
N
)
log(N)
log(N)次，而红黑树查找
2
∗
l
o
g
(
N
)
2*log(N)
2∗log(N)次。而这种情况没有什么效率区别，而AVLTREE构建的旋转比红黑树多。综合而言红黑树的效率并不比AVLTREE树差，但是旋转比AVLTREE少。
2.红黑树的性质与原理
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么满足前4个性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍呢？（严格来说主要规则是第三条规则和第四条规则）
如果一个节点是红色的，则它的两个孩子结点是黑色的 -> 树中没有连续的红色节点（可以红黑相间或者连续黑）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 -> 每条路径上都包含相同数量的黑色节点
最短路径：全部由黑色结点构成。
既然第四点说对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。我们大可以先把每条路径上的黑色节点全部抽离出来构造成一棵树，此时必然是满二叉树。此时不能再追加黑色节点，只能追加红色节点，不加红色节点的话就是此时路径就是最短的。
最长路径：在全部由黑色结点构成的树上添加红色节点进行构造最长路径。
由于红色是不能连续的，因此只能间隔。构造出的最长路径为一黑一红的状态，而这条最长路径的黑的数量和最短路径的黑的数量相同，因此最多为2倍状态。
因此假设黑色结点有N个，则最短路径长度为
O
(
l
o
g
N
)
O(logN)
O(logN),最长路径长度为
2
∗
O
(
l
o
g
N
)
2*O(logN)
2∗O(logN)。
那么第五点怎么理解？是针对如这种情况下满足第四点的条件。
Tips:正常红黑树中，不一定有全黑的最短路径和一黑一红最长路径
3.红黑树节点的定义
enum Color
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode(const pair<K,V>& kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(key_value),
_col(RED)
{}
RBTreeNode<K,V>* _left;
RBTreeNode<K,V>* _right;
RBTreeNode<K,V>* _parent;
pair<K,V> _kv;
Color _col;
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
RBTree()
:_root(nullptr)
{ }
pair<Node*,bool> Insert(const pair<K,V>& kv)
{
}
private:
Node* _root;
}
4.红黑树的插入
只要控制了这四条规则
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
就能控制住红黑树的近似平衡。
- 插入新节点的颜色是黑的好，还是红的好？
插入红色破坏规则3，插入黑色破坏规则4。
插入红色节点，因为红色节点可能破坏规则三，影响不大。
插入黑色节点，一定破坏规则4，并且影响其他路径，影响面很大。
比如在一个路径上插入黑色节点，那么和剩下的路径中都冲突了。而破坏规则三只破坏一个分叉。
因此插入新节点的时候插入红色节点。
对插入情况进行讨论：
parent颜色是黑色，不需要调整，插入完成。（结束了）parent颜色是红色，违反了规则3，需要处理。（关键看叔叔）
如果parent是红色的，则grandfather一定是黑的。这时候看uncle。
对违反规则3的情况进行讨论：
注意：以下看到的图，可能是一颗完整的树，也可能是一棵子树
4.1情况一
情况一：cur为红，p为红，g为黑，u存在且为红。
情况一对叔叔的讨论是叔叔存在且为红。
处理方案：p和u变黑，g变红。处理后如果g是root，则变回黑处理结束。->如果g的父亲是红，则继续往上处理
g变红的原因：因为当前部分可能是在子树中。比如这种情况，如果g不变红，该子树的两个路径就会各自多出一个黑色，与子树外的路径造成了规则4的冲突。
这时候要考虑如果到g的父亲如果是黑色的，就没有问题了。
不然如果g的父亲是红，此时就出现了两个红色的，要继续往上处理。
对于情况一来说，即使换个方向，依然能够变色处理完成。
4.2情况二
情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑
处理方式：单旋+变色
情况二的u存在且为黑理论上是从情况1处理后变化得到的。
因此u存在且为黑需要以情况一的处理一次后为基础。
- u不存在的情况
红黑树中但凡触发旋转一定是最长路径超过了最短路径的二倍
- u存在且为黑的情况
情况二方向反了进行另一种单旋+变色。
4.3情况三
红黑树中但凡触发旋转一定是最长路径超过了最短路径的二倍
情况三是情况二的变形，不同的是情况二是直线，是单旋；情况三是曲线，是双旋。
情况三方向反了进行另一种双旋+变色。
情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑
注意下图p左端的黑色节点是一定要存在的，不然没法满足每条路径的黑色节点个数相同的规则
4.4代码实现
对于上述三种情况反旋的图。见小结部分
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
RBTree()
:_root(nullptr)
{ }
void Destroy(Node* root)
{
if(root == nullptr ) return ;
Destroy(root -> _left );
Destroy(root -> _right);
delete root;
}
~RBTree()
{
Destroy(root);
_root = nullptr;
}
//拷贝构造和operator[]赋值
Node* Find(const K& key)
{
Node* cur = _root;
while( cur )
{
if( cur -> _kv.first > key)
{
cur = cur -> _left;
}
else if( cur -> _kv.first < key)
{
cur = cur -> _right;
}
else{
return cur;
}
}
return nullptr;
}
void RotateR(Node* parent)
{
Node* subL = parent -> _left;
Node* subLR = subL -> _right;
parent -> _left = subLR;
if( subLR ) subLR -> _parent = parent;
subL -> _right = parent ;
Node* grandParent = parent -> _parent;
parent -> _parent = subL;
if( parent == _root )
{
_root = subL;
_root -> _father = nullptr;
}
else{
if( grandParent -> _left == parent )
{
grandParent -> _left = subL;
}
else{
grandParent -> _right =subL;
}
subL -> _father = grandParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent -> _right;
Node* subRL = subR -> _left;
parent -> _right = subRL;
if( subRL != nullptr ) {
subRL -> _parent =parent ;
}
subR -> _left = parent;
Node* grandparent = parent -> _parent;
parent -> _parent = subR;
if( parent == _root )
{
_root = subR;
_root -> _parent = nullptr;
}
else{
if(grandparent -> _left == parent)
{
grandparent -> _left = subR;
}
else{
grandparent -> _right = subR;
}
subR -> _parent = grandparent;
}
subR -> _bf = parent -> _bf =0;
}
pair<Node*,bool> Insert(const pair<K,V>& kv)
{
if(_root == nullptr)
{
_root = new Node(kv);
_root = BLACK;
return make_pair(_root,true);
}
Node* parent = nullptr;
Node* cur = _root;
while(cur)
{
if( cur -> _kv.first < kv.first)//如果实现的是multimap这里使用的是<=
{
parent = cur ;
cur = cur -> _right;
}
else if( cur -> _kv.first > kv.first)
{
parent =cur ;
cur = cur -> _left;
}
else{
return make_pair(cur ,false);
}
}
Node* newnode = new Node(kv);
newnode -> _col = RED;
if( parent -> _kv.first < kv.first)
{
parent -> _right = newnode;
newnode -> _parent = parent;
}
else{
parent -> _left = newnode ;
newnode -> _parent = parent;
}
cur = newnode;
//如果父亲存在，且颜色为红色，则需要处理
while( parent && parent -> _col ==RED)
{
//关键看叔叔
Node* grandfather = parent -> _parent ; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红
if(parent == grandfather -> _left)
{
Node* uncle = grandfather -> _right;
//情况一：uncle存在且为红
if( uncle && uncle -> _col ==RED)
{
parent -> _col = uncle -> _col = BLACK;
grandfather -> _col = RED;
//继续往上处理
cur = grandfather;
parent = cur -> _parent;
}
else{ //情况 2+3 uncle不存在/uncle存在且为黑
if( cur == parent -> _left ) // 情况2: 单旋
{
RotateR(grandfather);
grandfather -> _col = RED;
parent -> _col = BLACK;
}
else{ //情况三:双旋
RotateL(parent);
RotateR(grandfather);
cur -> _col = BLACK;
grandfather -> _col = RED;
}
break;//旋转完就整棵树变成红黑树了
}
}
else// parent == grandfather -> _right;
{
Node* uncle = grandfather -> _left;
if(uncle && uncle -> _col == RED)//情况一:叔叔存在且为红
{
uncle -> _col = BLACK;
parent -> _col = BLACK;
grandfather -> _col =RED;
cur = grandfather ;
parent = cur -> _father;
}
else{//情况二+三:叔叔存在且为黑或者不存在
if( cur == parent -> _right )//情况二:单旋+变色
{
RotateL(grandfather);
grandfather -> _col =RED;
parent -> _col =BLACK;
}
else{
RotateR(parent);
RotateL(grandfather);
cur -> _col = BLACK;
grandfater -> _col = RED;
}
break;//旋转完必定搞定
}
}
}
_root -> _col = BLACK;
return make_pair(newnode ,true);
}
private:
Node* _root;
}
4.5小结
新增节点(红色) ps：插入红色只会影响当前路径
1、如果插入节点父亲如果是黑色，插入结束
2、如果插入节点父亲如果是红色，那么违反不能连续有红色节点的规则
先讨论
/
/
/的情况，再讨论曲线，接着讨论\的情况，最后讨论曲线。
每种大情况通过对叔叔的讨论分为三种情况来处理：关键看叔叔。如果要旋转则当前情况一定是最长路径的长度>2*最短路径的长度
5.红黑树的检查
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的 –>每条路径上的黑色节点数量相等
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
红黑树平衡的关键点在这几点规则，我们重点检查1、2、3规则。
第一点规则进入的时候就可以检查
对于第二点来说，如果检查儿子有一些麻烦，考虑只有一个儿子，两个儿子，没有儿子；不如遍历的时候检查父亲和当前是不是都是红色，因为红色节点理论上是有父亲的。
对于第三点来说，如果不开额外的空间就使用
O
(
N
2
)
O(N^2)
O(N2)的做法递归。或者开
O
(
n
)
O(n)
O(n)的空间来存下每条路径的黑色节点数量。我们尝试
O
(
n
)
O(n)
O(n)时间复杂度+
O
(
1
)
O(1)
O(1)空间复杂度，利用一个搜出来的标准值。
bool CheckBalance()
{
if( _root == nullptr )
{
return true;
}
if( _root == RED )
{
cout<< " 根节点是红色的 " <<endl;
return false;
}
int blackNum =0 ;//找最左路径做黑色节点数量的参考值
Node* left = _root ;
while(left)
{
if( left -> _col == BLACK)
{
blackNum ++;
}
left = left -> _left;
}
int count = 0;
return _CheckBalance(_root , blackNum,count )
}
bool _CheckBalance(Node* root ,int blackNum ,int count)
{
if( root == nullptr )
{
if( count != blackNum )
{
cout<<" 黑色节点的数量不相等 "<<endl;
return false;
}
return true;
}
//检查规则二
if(root -> _col == RED && root -> _parent -> _col == RED ) return false;
if(root -> _col == BLACK ) count ++;
return _CheckBalance(root -> _left , blackNum ,count ) && _CheckBalance( root -> _right ,blackNum ,count );
}
#include"RBTree.h"
void TestRBTree()
{
int a[] = { 16 , 3, 7 ,11 ,9 ,26 ,18, 14 ,15};
RBTree<int,int> t;
for(auto e:a)
{
t.insert(make_pair(a,a));
}
t.InOrder();
cout<< t.CheckBlance()<<endl;
}
int main()
{
return 0;
}
6.红黑树的删除
只讲原理不讲实现。同AVL。
- 如果左为空右为空，直接删
- 如果左右都不为空，找替代结点删除。
实际删除的结点一定满足左为空或右为空。
可以了解：http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html