- 主页/
- 浅析红黑树
1.了解红黑树
学习完AVL树，开始了红黑树的学习，关于红黑树，和AVL树是类似的，都是会在我们进行插入操作或者删除操作以后会进行一些操作，来使得整个二叉树保持一个平衡。
红黑树和AVL树的区别在于一个是依照平衡因子来维持整个树，而红黑树是利用颜色来限定平衡。
自从红黑树出现以后，AVL树就慢慢消失了，原因，会在后面讲解。
另外，最为重要的是在STL当中，有很多都应用了红黑树，比如：set, multiset, map, multimap
2.理解红黑树的特点
红黑树为了维持平衡，提出了4个条件。
每个节点只有黑色和红色两种区别
根节点一定是黑色。
不能出现连续的红色
每条路径上黑色节点的数目是相同的。
-每个叶子节点是黑的（这里的叶子节点这里可以理解为NUL节点和叶子节点）
通过这4个条件，就可以维持一棵红黑树的平衡。
3.红黑树节点结构
红黑的节点可以参考AVL树的节点，在AVL中，利用平衡因子维持平衡，在红黑树中，我们要利用颜色，所以，我们在这里给一个颜色。这个颜色当然只能有红的或者是黑的，所以我们在这里利用枚举来保存这个颜色。
enum color
{
BLACK,
RED
};
//红黑树的节点结构
template<typename K, typename V>
struct RBNode
{
typedef RBNode<K, V> Node;
RBNode(const K& key,const V& value)
: _left(NULL)
, _right(NULL)
, _parent(NULL)
, _key(key)
, _value(value)
, _color(RED)
{}
Node* _left;
Node* _right;
Node* _parent;
K _key;
V _value;
int _color;
};4.红黑树的插入算法
我们首先来看红黑树的插入算法，如果你看了我的前两篇文章，关于二叉搜索树的插入算法和AVL树的插入算法以后，我想你能很快有一个大致思路，红黑树，就是插入节点，然后进行调整颜色，调整颜色过程中有些会直接进行变化颜色，有些是要通过旋转变化颜色。
为了简化插入过程，我们需要考虑我们默认插入什么颜色的节点，在这里，你可以想一下，如果你默认插入黑色节点，是否能让每条路径上黑色的节点数目相同？所以，我们默认插入的节点应该是红色节点。
在这里，为了维持那几条规则，所以我们要维护的节点和parent节点，pparent节点和uncle节点。cur就是我们所插入的节点，或者因为插入所做出调整以后影响了上面节点的情况。
在这里，我给出红黑树插入所会遇到的大致几种情况：
下面我们所讨论的统一采用cur，parent，pparent，uncle这几种命名方式。另外，我们插入的cur节点或者向上回溯时的cur皆为红色。
插入根节点
插入节点为根节点的时候，根据第二条规则，我们的根节点为黑色，所以我们记得要对根节点设置为黑色。（注：为了方便其他情况，我们可以采用没种情况都对根节点设置为黑色。）
parent节点颜色为红色，uncle节点为红色。（只做变色调整，需要向上回溯）。
这个时候cur的颜色和parent的颜色都为红色，会发生问题，这个时候我们需要进行变色的调整，此时我们来看uncle，uncle为红色。
parent节点为红色，uncle节点为黑色。（旋转调整）
当parent为红色，uncle为黑色的时候，这个时候我们就需要进行旋转调整。
旋转当然分为四种情形：
1.左单旋转：
代码实现：
void _BRRolateL(Node *parent)
{
assert(parent);
Node *SubR = parent->_right;
Node *SubRL = SubR->_left;
parent->_right = SubRL;
if (SubRL)
SubRL->_parent = parent;
Node *ppnode = parent->_parent;
SubR->_left = parent;
parent->_parent = SubR;
if (ppnode == NULL)
{
_root = SubR;
SubR->_parent = NULL;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = SubR;
}
else
{
ppnode->_right = SubR;
}
SubR->_parent = ppnode;
}
}2.右单旋转：
代码实现：
void _BRRolateR(Node *parent)
{
assert(parent);
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
parent->_left = SubLR;
if (SubLR)
SubLR->_parent = parent;
Node *pparent = parent->_parent;
SubL->_right = parent;
parent->_parent = SubL;
if (pparent == NULL)
{
_root = SubL;
SubL->_parent = NULL;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = SubL;
SubL->_parent = pparent;
}
else
{
pparent->_right = SubL;
SubL->_parent = pparent;
}
}
}左右双旋转：
_BRRolateL(parent); std::swap(parent, cur); _BRRolateR(pparent); pparent->_color = RED; parent->_color = BLACK;
右左双旋转：
_BRRolateR(parent); std::swap(parent, cur); _BRRolateL(pparent); pparent->_color = RED; parent->_color = BLACK;
双旋转我采用了单旋转实现所以需要交换parent和cur。
这就是所有的关于插入算法旋转调整的情形。
接下来是插入算法的思路，和AVL树以及二叉搜索树的思路是类似的，都是先进行寻找，找到你所要插入的位置，然后创建节点，插入就好了。这里就不多说了，如果有疑问，可以去看我的AVL树的插入算法讲解和搜索二叉树的插入算法实现讲解。
代码实现：
bool Insert(const K& key, const V& value)
{ if (_root == NULL)
{
_root = new Node(key, value);
_root->_color = BLACK; return true;
}
Node *cur = _root;
Node *parent = NULL; while (cur)
{ if (cur->_key < key)
{ parent = cur;
cur = cur->_right;
} else if (cur->_key>key)
{ parent = cur;
cur = cur->_left;
} else
{ return false;
}
}
cur = new Node(key, value); if (parent->_key > key)
{ parent->_left = cur;
} else
{ parent->_right = cur;
}
cur->_parent = parent; //判断如果parent是根节点，那么直接结束
while (parent!=NULL)
{ //父亲是黑色，cur是红色，符合红黑树，退出
if (parent->_color == BLACK)
{
break;
} //父亲和cue都是红色的情况
Node* pparent = parent->_parent;
Node* uncle = NULL; //考虑parent 是左边的情况
if (pparent->_left == parent)
{
uncle = pparent->_right; //考虑叔叔是红色的情况
if (uncle&&uncle->_color == RED)
{
pparent->_color = RED;
uncle->_color = parent->_color = BLACK;
cur = pparent; parent = cur->_parent;
continue;
} //考虑叔叔不存在或者叔叔是黑色的情况
else if (uncle == NULL || uncle->_color == BLACK)
{ if (cur == parent->_left)
{
_BRRolateR(pparent);
pparent->_color = RED; parent->_color = BLACK;
} else
{
_BRRolateL(parent);
std::swap(parent, cur);
_BRRolateR(pparent);
pparent->_color = RED; parent->_color = BLACK;
}
break;
}
} //考虑parent是右边的情况
else
{
uncle = pparent->_left; if (uncle&&uncle->_color == RED)
{
pparent->_color = RED;
uncle->_color = parent->_color = BLACK;
cur = pparent; parent = cur->_parent;
} else if (uncle == NULL || uncle->_color == BLACK)
{ if (cur == parent->_right)
{
_BRRolateL(pparent);
pparent->_color = RED; parent->_color = BLACK;
} else
{ //_BRRolateRL(pparent);
_BRRolateR(parent);
std::swap(parent, cur);
_BRRolateL(pparent);
pparent->_color = RED; parent->_color = BLACK;
}
}
break;
}
}
_root->_color = BLACK; return true;
}5.红黑树的查找算法
关于红黑树而言，他的查找算法和二叉搜索树和AVL树的也几乎一样。
进行通过key实现查找就好了。
bool Find(const K& key)
{ if (_root == NULL) return false;
Node *cur = _root; while(cur)
{ if (cur->_key < key)
{
cur = cur->_right;
} else if (cur->_key>key)
{
cur = cur->_left;
} else
{ return true;
}
} return false;
}6.判断是否是和法红黑树
对于判端一棵树是否是红黑树，其实思路很简单，就是判断红黑树以及它的子树是否满足上述红黑树的特点就好了。
所以，总结下来也就是：
根节点为黑色
没有连续红色节点
每条路径上有相同的黑色节点数
当满足这三个条件的时候，我们就可以认为这棵树是合法的红黑树。
第一个条件好判断，直接可以进行判断，第二个和第三个需要进行递归。
第二个没有连续的红色节点我们的思路就是当这个节点为红色的时候，我们判断它和它的父节点是否颜色相同，如果相同就不是红黑树。
第三个条件的思路就是，因为你需要进行判断红黑树的每条路径黑节点数相同，所以首先你需要给出一个参考，然后每一条路径的黑色节点数和这个参考值进行比对就好了。如果有不相同的，那么就代表这个树不是红黑树。因为我们需要知道每条路径的，所以当一条路径算完以后，另一条路径与它相同的依然可以使用，所以我们进行传值调用。一条路径的结束，也就是找寻到了叶子节点。
bool IsRBTree()
{
//当为空树的时候，是红黑树
if (_root == NULL)
{
return true;
}
//当根节点是红色的时候，直接可以确定不是红黑树
if (_root->_color == RED)
{
return false;
}
//给出一个参考的路径的黑色节点的数目
size_t count = 0;
Node* cur = _root;
while (cur)
{
if (cur->_color == BLACK)
count++;
cur = cur->_left;
}
//k用来记录一条路径的黑色节点的数目，和count来进行比较
size_t k = 0;
return _IsRBTree(_root, count, k);
}//这里的k需要进行传值，因为这里你需要对每一条路径进行对比，所以在这里，你要找寻完一条路径以后，向上回溯，
bool _IsRBTree(Node* root, const size_t& count, size_t k)
{
if (root == NULL)
{
return true;
}
//当出现两个连续的红色节点的时候，可以确定不是红黑树
if (root->_parent&&root->_color == root->_parent->_color == RED)
{
return false;
}
//如果是黑色节点，k进行++
if (root->_color == BLACK)
{
k++;
}
//如果是叶子节点的话，进行判断k和count是否相等
if (root->_left == NULL&&root->_right == NULL)
{
//k和count不相等，那么就不是红黑树。
if (k == count)
return true;
else
return false;
}
//对节点的左右进行检查
return _IsRBTree(root->_left, count, k) && _IsRBTree(root->_right, count, k);
}作者：宇哲_安菲尔德
isaimawang
@ 赛码网
533869549