柚子快报邀请码778899分享：c++ 【数据结构】红黑树
文章目录
1, 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树的结构5. 红黑树的插入操作6. 红黑树的验证7. 红黑树与 AVL 树的比较8. 红黑树的应用
1, 红黑树的概念
红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。
2. 红黑树的性质
每个节点不是红色就是黑色；根节点是黑色的；如果一个节点是红色的，则它的两个孩子节点是黑色的；对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；每个叶子节点都是黑色的（此处的叶子节点指的是空节点）。
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
3. 红黑树节点的定义
// 节点的颜色
enum Color { RED, BLACK };
// 红黑树节点的定义
template
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode
RBTreeNode
RBTreeNode
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
};
思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
4. 红黑树的结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头节点，因为根节点必须为黑色，为了与根节点进行区分，将头节点给成黑色，并且让头节点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，pRight 域指向红黑树中最大的节点，如下：
5. 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
按照二叉搜索树的树规则插入新节点： template
class RBTree
{
//……
bool Insert(const ValueType& data)
{
PNode& pRoot = GetRoot();
if (nullptr == pRoot)
{
pRoot = new Node(data, BLACK);
// 根的双亲为头节点
pRoot->_pParent = _pHead;
_pHead->_pParent = pRoot;
}
else
{
// 1. 按照二叉搜索的树方式插入新节点
// 2. 检测新节点插入后，红黑树的性质是否造到破坏，
// 若满足直接退出，否则对红黑树进行旋转着色处理
}
// 根节点的颜色可能被修改，将其改回黑色
pRoot->_color = BLACK;
_pHead->_pLeft = LeftMost();
_pHead->_pRight = RightMost();
return true;
}
private:
PNode& GetRoot() { return _pHead->_pParent; }
// 获取红黑树中最小节点，即最左侧节点
PNode LeftMost();
// 获取红黑树中最大节点，即最右侧节点
PNode RightMost();
private:
PNode _pHead;
};
检测新节点插入后，红黑树的性质是否遭到破坏： 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三：不能有连在一起的红色节点，此时需要对红黑树分情况来讨论： 约定：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。
情况一：cur 为红，p 为红，g 为黑，u 存在且为红 cur 和 p 均为红，违反了性质三，此处能否将 p 直接改为黑？ 解决方式：将 p，u 改为黑，g 改为红，然后把 g 当成 cur，继续向上调整。 情况二：cur 为红，p 为红，g 为黑，u 不存在 / u 存在且为黑 p 为 g 的左孩子，cur 为 p 的左孩子，则进行右单旋转；相反， p 为 g 的右孩子，cur 为 p 的右孩子，则进行左单旋转； p、g 变色 – p 变黑，g 变红。 情况三：cur 为红，p 为红，g 为黑，u 不存在 / u 存在且为黑 p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 做左单旋转；相反， p 为 g 的右孩子，cur 为 p 的左孩子，则针对 p 做右单旋转； 则转换成了情况 2。 针对每种情况进行相应的处理即可。 bool Insert(const ValueType& data)
{
// ...
// 新节点插入后，如果其双亲节点的颜色为空色，则违反性质3：不能有连在一起的红色结点
while (pParent && RED == pParent->_color)
{
// 注意：grandFather一定存在
// 因为pParent存在，且不是黑色节点，则pParent一定不是根，则其一定有双亲
PNode grandFather = pParent->_pParent;
// 先讨论左侧情况
if (pParent == grandFather->_pLeft)
{
PNode unclue = grandFather->_pRight;
// 情况三：叔叔节点存在，且为红
if (unclue && RED == unclue->_color)
{
pParent->_color = BLACK;
unclue->_color = BLACK;
grandFather->_color = RED;
pCur = grandFather;
pParent = pCur->_pParent;
}
else
{
// 情况五：叔叔节点不存在，或者叔叔节点存在且为黑
if (pCur == pParent->_pRight)
{
_RotateLeft(pParent);
swap(pParent, pCur);
}
// 情况五最后转化成情况四
grandFather->_color = RED;
pParent->_color = BLACK;
_RotateRight(grandFather);
}
}
else
{
// 右侧请大家自己动手完成
}
}
// ...
}
6. 红黑树的验证
红黑树的检测分为两步：
检测其是否满足二叉搜索树（中序遍历是否为有序序列）；检测其是否满足红黑树的性质。
bool IsValidRBTree()
{
PNode pRoot = GetRoot();
// 空树也是红黑树
if (nullptr == pRoot)
return true;
// 检测根节点是否满足情况
if (BLACK != pRoot->_color)
{
cout << "违反红黑树性质二：根节点必须为黑色" << endl;
return false;
}
// 获取任意一条路径中黑色节点的个数
size_t blackCount = 0;
PNode pCur = pRoot;
while (pCur)
{
if (BLACK == pCur->_color)
blackCount++;
pCur = pCur->_pLeft;
}
// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
size_t k = 0;
return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{
//走到null之后，判断k和black是否相等
if (nullptr == pRoot)
{
if (k != blackCount)
{
cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
// 统计黑色节点的个数
if (BLACK == pRoot->_color)
k++;
// 检测当前节点与其双亲是否都为红色
PNode pParent = pRoot->_pParent;
if (pParent && RED == pParent->_color && RED == pRoot->_color)
{
cout << "违反性质三：没有连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(pRoot->_pLeft, k, blackCount)
&& _IsValidRBTree(pRoot->_pRight, k, blackCount);
}
7. 红黑树与 AVL 树的比较
红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(
l
o
g
2
N
log_2 N
log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
8. 红黑树的应用
C++ STL 库 – map / set、multi_map / multi_set；Java 库；Linux 内核；其他一些库；…
END
柚子快报邀请码778899分享：c++ 【数据结构】红黑树
推荐链接
您阅读本篇文章共花了：
发表评论