红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是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
情况二:cur为红,parent为红,grandfather为黑(固定),u不存在/u存在且为黑(单旋+变色)
处理:
说明:uncle的情况有两种
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);
}