本文仅适合了解二叉搜索树,但不了解红黑树底层原理的同学阅读哦。
本篇文章不会带你从头到尾实现红黑树,但会带你深入理解红黑树是怎么实现平衡的,怎么通过旋转变换实现保持平衡,以及实现平衡过程中的细节应该怎么处理等。
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
其中第三点和第四点是控制红黑树平衡的关键,与AVL树不同的是,红黑树不再关注高度,只关注颜色,只要控制住了颜色就控制住了高度。
维持二叉搜索树的平衡,旋转处理是必要的,因此红黑树的节点也需要指向其父节点。
enum Colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv, colour col = RED)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(col)
{}
};
上面我们将节点的默认颜色设置为红色,为什么不是黑色呢?
新增节点默认设置为红色或黑色都可能会破坏红黑树的性质,默认为红色对红黑树的性质影响最小,就算修改也更为容易。另外红黑树主要还是以黑色节点为主,在红黑树中黑色节点通常都是通过变色而来的,而红色节点往往都是新增的。
虽然新增节点默认为红色,但根节点必须是黑色。
bool Insert(const pair<K, V>& kv)
{
Node* pcur = _root;
Node* parent = nullptr;
if (pcur == nullptr)//当前还没有节点
{
_root = new Node(kv);
_root->_col = BLACK;//根节点必须是黑色的
return true;
}
//...
}
插入一个红色节点,其父亲是红色时才需要处理, 当父亲是红色时其爷爷一定是黑色,不然在插入新节点之前红黑树就已经有问题了。
所以处理过程的关键是看叔叔,大体可以分为两种情况:
其中g
表示grandfather
,p
表示parent
,u
表示uncle
。a,b,c,d,e
为红黑子树。
| 情况一:g为黑,p为红,u存在且为红 | 处理方法:变色,继续向上调整
上图中pcur
可能为新增节点,也可能之前为黑,是经过变色而来的。
//当父节点存在且为红时需要调整
while (parent && parent->_col == RED)
{
if (parent == grandfather->_left)
{
uncle = grandfather->_right;
}
else
{
uncle = grandfather->_left;
}
if (uncle && uncle->_col == RED)//情况一:u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
if (grandfather->_parent == nullptr)
{
grandfather->_col = BLACK;
return true;
}
pcur = grandfather;
parent = pcur->_parent;
grandfather = parent->_parent;
}
//...
}
| 情况二:g为黑,p为红,u存在且为黑 / u不存在 | 处理方法:旋转 + 变色
单旋:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
if (subLR)
{
subLR->_parent = parent;
}
Node* parentparent = parent->_parent;
parent->_parent = subL;
if (parentparent == nullptr)
{
_root = subL;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subL;
}
else
{
parentparent->_right = subL;
}
}
subL->_parent = parentparent;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* parentparent = parent->_parent;
parent->_parent = subR;
if (parentparent == nullptr)
{
_root = subR;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subR;
}
else
{
parentparent->_right = subR;
}
}
subR->_parent = parentparent;
}
双旋:
//当父节点存在,且颜色为红,需要往上更新
while (parent && parent->_col == RED)
{
if (parent == grandfather->_left)
{
uncle = grandfather->_right;
}
else
{
uncle = grandfather->_left;
}
//情况一:u存在且为红
else //情况二:u存在且为黑 / 情况三:u不存在
{
if (parent == grandfather->_left
&& pcur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else if (parent == grandfather->_left
&& pcur == parent->_right)
{
RotateL(parent);
RotateR(grandfather);
pcur->_col = BLACK;
grandfather->_col = RED;
}
else if (parent == grandfather->_right
&& pcur == parent->_left)
{
RotateR(parent);
RotateL(grandfather);
pcur->_col = BLACK;
grandfather->_col = RED;
}
else if (parent == grandfather->_right
&& pcur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_cocl = RED;
}
break;
}
}
总结:
不管是变色还是旋转,始终都要保持插入新节点前后各路径上黑色节点的数量。
检测红黑树的性质,主要检测红黑树的根节点是否为黑色、任意一个红色节点的父节点不是红色、任意节点到根节点的路径上黑色节点的数量相等。 其中检测任意节点到根节点的路径上黑色节点数量相等可以用递归处理,先算出某条路径上黑色节点的数量,通过递归与每条路径上黑色节点的数量最对比,如果与某条路径上黑色节点的数量不相等则红黑树异常。
bool IsValidRBTree()
{
Node* pRoot = _root;
if (nullptr == pRoot)
{
return true;
}
//检测根节点是否满足情况
if (BLACK != pRoot->_col)
{
cout << "违反性质二:根节点必须为黑色" << endl;
return false;
}
//获取任意一条路径中黑色节点的个数
size_t blackCount = 0;
Node* pcur = pRoot;
while (pcur)
{
if (BLACK == pcur->_col)
blackCount++;
pcur = pcur->_left;
}
//检测是否满足红黑树的性质,k用来记录路径中黑色节点的个数
size_t k = 0;
return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
//走到nullptr后,判断k和black是否相等
if (nullptr == pRoot)
{
cout << k << endl;
if (k != blackCount)
{
cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
//统计黑色节点的个数
if (BLACK == pRoot->_col)
{
k++;
}
//检测当前节点与其双亲是否都为红色
Node* pParent = pRoot->_parent;
if (pParent && RED == pParent->_col && RED == pRoot->_col)
{
cout << "违反性质三:没有连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(pRoot->_left, k, blackCount) &&
_IsValidRBTree(pRoot->_right, k, blackCount);
}
红黑树相对AVL树并没有那么严格地要求平衡,仅通过颜色控制最长路径中节点个数不会超过最短路径节点个数的两倍就行。
当AVL树不平衡时仅通过旋转来处理,红黑树不平衡时可以变色、变色+旋转处理,显然红黑树插入、删除过程更有优势,而AVL树查找过程更有优势。而set和map底层、Linux内核等都使用红黑树实现。
本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~