＜C++＞红黑树
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
文章目录
1. 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
2. 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的则它的两个孩子结点是黑色的
- 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
思考为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍
最短路径全黑如果没有全黑的就是红节点最少的那条路径
最长路径一黑一红间隔
并且对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点。可以得出其最长路径中节点个数不会超过最短路径节点个数的两倍
3. 红黑树节点定义
enum Colour
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _col(RED)// 选择更好搞定的
{}
};
思考在节点的定义中为什么要将节点的默认颜色给成红色的
- 新增节点是红色可能破坏规则3【如果一个节点是红色的则它的两个孩子结点是黑色的】
- 新增节点是黑色一定破坏规则4【对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点】并且规则4很难维护要牵扯到更多节点
4. 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
-
按照二叉搜索的树规则插入新节点
-
检测新节点插入后红黑树的性质是否造到破坏
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
1️⃣情况一: cur为红p为红g为黑u存在且为红
将g改为黑色的原因为了不破坏规则4【对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点】。这棵树有可能是局部子树原本它的两条路径上都有1个黑结点如今将u和p变黑这两条路径上就分别多了一个黑结点违反规则4此时把g改为黑色能避免这种问题。
解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。
不关心左右关系p、u是g的左还是右不影响cur是p的左还是右也没关系因为只变色不旋转
2️⃣情况二: cur为红p为红g为黑u不存在/u存在且为黑
u有两种情况
- 如果u不存在。右只有一个黑左也要只有一个黑左不能有新的黑左的高度不能大于2所以cur是新增红结点。变色新根变黑对向上的数结点没影响了g变红维持黑的数量
- 如果u存在且为黑。cur一定不是新增否则cur插入前该树不符合规则4。由规则3得cur原本是黑的是由情况一的处理方式变成红色的
p为g的左孩子cur为p的左孩子则进行右单旋转相反
p为g的右孩子cur为p的右孩子则进行左单旋转
p、g变色–p变黑g变红
3️⃣情况三: cur为红p为红g为黑u不存在/u存在且为黑
情况三和情况二的区别
p是g的左cur是p的左是情况二——单旋
p是g的左cur是p的右是情况三——双旋
u有两种情况
- 如果u不存在。右只有一个黑左也要只有一个黑左不能有新的黑左的高度不能大于2所以cur是新增红结点。变色新根变黑对向上的数结点没影响了g变红维持黑的数量
- 如果u存在且为黑。cur一定不是新增否则cur插入前该树不符合规则4。由规则3得cur原本是黑的是由情况一的处理方式变成红色的
就只是跟情况二的左右关系交换了一下
p为g的左孩子cur为p的右孩子则针对p做左单旋转
相反p为g的右孩子cur为p的左孩子则针对p做右单旋转
则转换成了情况2
//按搜索二叉树规则插入
//更新平衡因子旋转使其平衡
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
return false;
}
cur = new Node(kv);
cur->_col = RED;
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 存在连续红色节点
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;// parent是红的一定存在grandparent
if (parent == grandfather->_right)// 区分左右
{
Node* uncle = grandfather->_left;
// 情况一
if (uncle && uncle->_col == RED)// 叔叔存在且为红
{
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 向上处理
cur = grandfather;
parent = cur->_parent;
}
else// 叔叔不存在 或者 叔叔存在且为黑
{
// 情况二直线
// g p
// p -> g c
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况三折线
// g c
// p -> g p
// c
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_right;
// 情况一
if (uncle && uncle->_col == RED)// 叔叔存在且为红
{
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 向上处理
cur = grandfather;
parent = cur->_parent;
}
else// 叔叔不存在 或者 叔叔存在且为黑
{
// 情况二直线
// g p
// p -> c g
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况三折线
// g c
// p -> p g
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;// 情况一改变根之后一定要记得把根变为黑
return true;
}
5. 红黑树的验证
红黑树的检测分为两步
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质
bool _IsValidRBTree(Node* root, size_t k, const size_t blackCount)
{
if (nullptr == root)
{
if (blackCount != k)
{
cout << "违反性质四每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
if (BLACK == root->_col)
++k;
// 检查连续红节点遇到红色节点检查父亲
if (RED == root->_col && root->_parent && RED == root->_parent->_col)
{
cout << "违反性质三存在连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(root->_left, k, blackCount)
&& _IsValidRBTree(root->_left, k, blackCount);
}
bool IsBalanceTree()
{
// 检查规则
Node* pRoot = _root;
if (pRoot == nullptr)
return true;
if (pRoot->_col != BLACK)
{
cout << "根节点不是黑的" << endl;
return false;
}
// 检查每个路径黑节点数量求最左路径比较基准值
size_t blackCount = 0;
Node* pCur = pRoot;
while (pCur)
{
if (BLACK == pCur->_col)
blackCount++;
pCur = pCur->_left;
}
size_t k = 0;
return _IsValidRBTree(pRoot, k, blackCount);
}
6. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多
7. 红黑树模拟实现STL中的map与set
链接https://gitee.com/symng/cpp/tree/master/map_set/map_set