C++ 红黑树
目录
1.红黑树的概念
红黑树
，是一种
二叉搜索树
，但
在每个结点上增加一个存储位表示结点的颜色，可以是
Red
或
Black
。 通过对
任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍
，因而是接近平衡的。
2. 红黑树的特性
在讲解红黑树性质之前，先简单了解一下几个概念：
- parent：父节点
- sibling：兄弟节点
- uncle：叔父节点（ parent 的兄弟节点）
- grand：祖父节点（ parent 的父节点）
首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：
- 节点是红色或黑色
- 根是黑色
- 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
- 红色节点的子节点都是黑色 1.红色节点的父节点都是黑色 2.从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
根据上面的特性，我们来分辨一下下面的是不是红黑树
上面这棵树首先很容易就能知道是满足性质1-4条的，关键在于第5条性质，可能乍一看好像也是符合第5条的，但实际就会陷入一个误区，直接将图上的最后一层的节点看作叶子节点，这样看的话每一条从根节点到叶子结点的路径确实都经过了3个黑节点。
但实际上，在红黑树中真正被定义为叶子结点的，是那些空节点
3.红黑树的效率
红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。
查找操作时，它和普通的相对平衡的二叉搜索树的效率相同，都是通过相同的方式来查找的，没有用到红黑树特有的特性。
但如果插入的时候是有序数据，那么红黑树的查询效率就比二叉搜索树要高了，因为此时二叉搜索树不是平衡树，它的时间复杂度O(N)。
插入和删除操作时，由于红黑树的每次操作平均要旋转一次和变换颜色，所以它比普通的二叉搜索树效率要低一点，不过时间复杂度仍然是O(logN)。总之，红黑树的优点就是对有序数据的查询操作不会慢到O(logN)的时间复杂度。
4.红黑树节点的定义
enum color
{
RED,
BLACK
};
template <class k,class v>
struct RBTreeNode
{
RBTreeNode* left;
RBTreeNode* right;
RBTreeNode* _parent;
color col;
pair<k, v> kv;
RBTreeNode(const pair<k,v> kv)
:left(nullptr)
,right(nullptr)
,_parent(nullptr)
,col(RED)
,kv(kv)
{}
};这里思考一下为什么把节点默认颜色为红色呢
红黑树的结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了
与根节点进行区分，将头结点给成黑色，并且让头结点的
Parent
域指向红黑树的根节点，
Left
域指向红黑树中最小的节点，
Right
域指向红黑树中最大的节点，如下：
5.红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点
template<class ValueType>
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;
};
2.
检测新节点插入后，红黑树的性质是否造到破坏
因为
新节点的默认颜色是红色
，因此：如果
其双亲节点的颜色是黑色，没有违反红黑树任何
性质
，则不需要调整；但
当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点
，此时需要对红黑树分情况来讨论：
约定
: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
while (parent && parent->col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->left) 当parent是grandparent的左子树时
{
Node* uncle = grandparent->right;
if (uncle && uncle->col == RED) 当叔叔存在且叔叔为红色
{
parent->col = uncle->col = BLACK;
if (grandparent == root)
{
grandparent->col = BLACK;
return true;
}
else
{
grandparent->col = RED;
cur = grandparent;
parent = cur->_parent;
}
}
else 叔叔不存在时
{
if (cur = parent->left)
{
RotateR(grandparent);
parent->col = RED;
grandparent->col = BLACK;
}
else
{
RotateL(parent);
RotateR(grandparent);
cur->col = BLACK;
grandparent->col = RED;
}
break;
}
}
else //parent=grandparent->right
{
Node* uncle = grandparent->left;
if (uncle && uncle == RED)
{
parent->col = uncle->col = BLACK;
if (grandparent == root)
{
grandparent->col = BLACK;
return true;
}
else
{
grandparent->col = RED;
cur = grandparent;
parent = cur->_parent;
}
}
else
{
if (cur == parent->right)
{
RotateL(grandparent);
parent->col = BLACK;
grandparent->col = RED;
}
else
{
RotateR(parent);
RotateL(grandparent);
cur->col = BLACK;
grandparent->col = RED;
}
break;
}
}
}
}
root->col = BLACK;
return true;这里涉及的旋转问题在上一章讲AVL树提到过
RotateR（左单旋） RotateL（右单旋）
6.红黑树的验证
红黑树的检测分为两步：
1. 检测其是否满足二叉搜索树 ( 中序遍历是否为有序序列 )2. 检测其是否满足红黑树的性质
bool check(Node* root, int blacknum, const int refval)
{
if (root == nullptr)
{
if (blacknum != refval)
{
cout << "存在黑色结点数量不相等路径" << endl;
return false;
}
return true;
}
if (root->col == RED && root->_parent->col == RED)
{
return false;
}
if (root->col == BLACK)
{
blacknum++;
}
return check(root->left, blacknum, refval) && check(root->right, blacknum, refval);
}
bool IsValidRBTRee()
{
if (root == nullptr)
{
return true;
}
if (root->col == RED)
return false;
int refval = 0; //参考值
Node* cur = root;
while (cur)
{
if (cur->col == BLACK)
{
refval++;
}
cur = cur->left;
}
int blacknum = 0;
return check(root, blacknum, refval);
}7.红黑树和AVL树的对比
- AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
- 红黑树的插入删除比AVL树更便于控制操作
- 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）
原文地址：https://blog.csdn.net/puppy_1mo/article/details/142486645
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！