红黑树
红黑树概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径中节点个数的两倍？
极限最短：全黑 极限最长：一黑一红
红黑树结构
enum Color
{
RED,
BLACK
};
template <class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V> *_parent;
RBTreeNode<K, V> *_left;
RBTreeNode<K, V> *_right;
pair<K, V> _kv;
Color _col;
RBTreeNode(const pair<K, V> &kv)
: _parent(nullptr), _left(nullptr), _right(nullptr), _kv(kv), _col(RED)
{
}
};
template <class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool insert(const pair<K, V> &kv)
{
}
private:
Node *_root = nullptr;
};红黑树操作
插入
红黑树的叔叔是关键 u存在且为红，变色继续向上处理 u不存在或存在且为黑，旋转（单旋+双旋）+变色
情况一：cur为红，parent为红，grandfather为黑（固定），uncle存在且为红
处理：p、u变黑，g变红，继续把g当成cur
- g不是根，往上继续处理
- g是根，再把g变成黑色
情况二：cur为红，parent为红，grandfather为黑（固定），u不存在/u存在且为黑（单旋+变色）
处理：
- g右单旋
- p变黑，g变红
说明：uncle的情况有两种
- 如果u节点不存在，那么cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有个节点颜色是黑色，就不满足性质4：每条路径黑色节点的个数相同。
- 如果u节点存在，那么cur节点原来的颜色一定是黑色的（保证性质4），现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改为红色。
u不存在
u存在且为黑
情况三：cur为红，parent为红，grandfather为黑（固定），u不存在/u存在且为黑（双旋+变色）
u不存在
u存在且为黑
插入代码：
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 (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
// 还得链接上
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 找到了应该插入的位置
while (parent && parent->_col == RED) // parent不为空并且颜色为红继续处理
{
Node *grandfather = parent->_parent;
// 如果父亲存在且颜色为红，那么祖父一定存在颜色为黑
assert(grandfather);
assert(grandfather->_col = BLACK);
// 先看parent是grandfather的左还是右
if (parent == grandfather->_left)
{
Node *uncle = grandfather->_right;
// 情况1、叔叔存在且为红，变色继续向上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况2、3：uncle不存在 存在且为黑
{
// 分两种
// 1、右单旋+变色
// g
// p u
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 先对p 左单旋，再对g 右单旋，最后变色
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // parent=grand->right
{
Node *grandfather = parent->_parent;
// 如果父亲存在且颜色为红，那么祖父一定存在颜色为黑
assert(grandfather);
assert(grandfather->_col = BLACK);
Node *uncle = grandfather->_left;
// 情况1、叔叔存在且为红，变色继续向上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况2、3：uncle不存在 存在且为黑
{
// 分两种
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}检查
- 根是黑色
- 没有连续的红节点
- 每条路径的黑色节点数量相同
bool is_balance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根节点不是黑色" << endl;
return false;
}
int bench_mark = 0;
return prev_check(_root, 0, bench_mark);
}
bool prev_check(Node *root, int bnum, int &bench_mark)
{
if (root == nullptr)
{
if (bench_mark == 0)
{
bench_mark = bnum;
return true;
}
if (bench_mark != bnum)
{
cout << "某条黑色节点的数量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++bnum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
return prev_check(root->_left, bnum, bench_mark) && prev_check(root->_right, bnum, bench_mark);
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-12-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。