红黑树的性质和定义
红黑树的性质
红黑树是一种平衡搜索二叉树。红黑树的每个节点存储了一个标记颜色的变量(红色或黑色)，通过对任意一条从根到叶子结点的路径中节点着色方式的限制，使树的最长路径不超过最短路径的两倍，因而红黑树处于一种近似平衡的状态。与AVL树相比，红黑的平衡条件更宽松，旋转的次数更少，因此在频繁插入删除的情况下，红黑树的性能比AVL树好。
红黑树具有以下性质：
- 根(_root)节点是黑色的；
- 每个节点不是黑色就是红色；
- 如果一个节点是红色的，那么它的两个孩子结点和父亲节点一定是黑结点。即不存在两个连续的红节点；
- 从每个节点到其所有叶子结点(nil节点)的路径中，黑色节点的数目相等；
- 每个叶子结点(nil)都是黑色的。
在红黑树中，叶子结点指的往往是空节点，逻辑上用nil进行标识，即认为空节点的颜色是黑色的。
根据上面的几条性质，可以得知在一棵红黑树中，从某个节点出发的最短路径中一定全部都是黑色节点，而最长路径一定是一黑一红相间(性质c)，再加上性质 d 的限制，可以证明红黑树的最长路径一定不超过最短路径的2倍。
红黑树的节点定义
为了便于找到节点的父节点，红黑树使用三叉链的形式设计，每个节点存储了有效数据、左右孩子指针和父节点指针，除此之外，红黑树的节点还记录了颜色信息。
将节点的颜色初始化为红色，是为了在插入新节点后尽量保持红黑树的性质，这点将会在讨论插入操作时说明。
//用枚举记录颜色信息
enum Color
{
RED,
BLACK
};
template<typename T>
struct RB_tree_node
{
typedef RB_tree_node<T> node;
T _data; //数据信息
node* _left;
node* _right;
node* _parent;
Color _color; //颜色信息
RB_tree_node(const T& data)
:_data(data),
_left(nullptr), _right(nullptr),
_parent(nullptr),
_color(RED) //将节点的颜色初始化为红色，是为了在插入新节点后尽量保持红黑树的性质
{ }
};红黑树的定义
红黑树的结构定义与二叉搜索树类似。
/*为了同时兼容Key模型和Key-Value模型，设计红黑树时提供三个模板参数。
当T为pair<>类型时，红黑树存储的数据为Key-Value模型，
Key和KeyOfT仿函数针对Key-Value模型，
便于使用和拿取pair<>中的Key*/
template<typename Key, typename T, typename KeyOfT>
class RB_tree
{
private:
typedef RB_tree_node<T> node;
/*…………*/
private:
node* _root;
};KeyOfT是一个仿函数，针对Key模型或Key-Value模型分别拿取有效数据的Key值。
//针对Key模型(set)
struct SetKeyOfT
{
const Key& operator()(const Key& key)
{
return key;
}
};
//针对Key-Value模型(map)
struct MapKeyOfT
{
//接受一个K-V键值对，返回kv.first
const Key& operator()(const std::pair<const Key, Value>& kv)
{
return kv.first;
}
};红黑树的构造和析构
构造红黑树时，将_root初始化为nullptr，析构时进行后序递归遍历析构。
template<typename Key, typename T, typename KeyOfT>
class RB_tree
{
private:
typedef RB_tree_node<T> node;
public:
RB_tree()
:_root(nullptr)
{ }
/*…………*/
~RB_tree()
{
_destroy(_root);
}
private:
/*…………*/
//后序遍历析构
void _destroy(node* root)
{
if (root == nullptr) {
return;
}
_destroy(root->_left);
_destroy(root->_right);
delete root;
root = nullptr;
}
/*…………*/
private:
node* _root;
};红黑树的迭代器
涉及红黑树的迭代器时，需要考虑迭代器类型、前进和后退、解引用和成员访问操作。
红黑树的迭代器属于双向迭代器，不具备随机定位能力，与list类似。为了满足迭代器的使用需求，需要对节点指针进行封装。由于这里实现的红黑树没有头结点，所以简单以nullptr作为end迭代器。
//与list的迭代器类似，Ref与Ptr模板参数用来区分普通迭代器和const迭代器
template<typename T, typename Ref, typename Ptr>
class __RB_tree_iterator
{
private:
typedef RB_tree_node<T> node;
typedef __RB_tree_iterator<T, Ref, Ptr> Self;
public:
__RB_tree_iterator(node* pnode)
:_node(pnode)
{ }
/*…………*/
node* _node; //对节点指针进行封装
};
template<typename Key, typename T, typename KeyOfT>
class RB_tree
{
private:
typedef RB_tree_node<T> node;
public:
typedef __RB_tree_iterator<T, T&, T*> iterator;
typedef __RB_tree_iterator<T, const T&, const T*> const_iterator;
public:
RB_tree()
:_root(nullptr)
{ }
//begin迭代器指向树中的最小节点，即最左节点
iterator begin()
{
node* leftMost = _root;
while (leftMost && leftMost->_left) {
leftMost = leftMost->_left;
}
return leftMost;
}
const_iterator begin() const
{
node* leftMost = _root;
while (leftMost && leftMost->_left) {
leftMost = leftMost->_left;
}
return leftMost;
}
//简单以nullptr作为end迭代器
iterator end()
{
return nullptr;
}
const_iterator end() const
{
return nullptr;
}
/*…………*/迭代器的解引用和元素访问接口直接返树节点的有效数据即可。
Ref operator*() const
{
return _node->_data;
}
Ptr operator->() const
{
return &(_node->_data);
}红黑树迭代器的前进操作其实走的是一个非递归中序遍历二叉树的过程，以迭代器遍历红黑树，得到的是一个升序序列。在前进的过程中，根据中序遍历顺序 “左子树 根 右子树” 分情况对节点指针进行调整即可。
Self& operator++()
{
node* cur = _node; //将当前节点视为“根”，优先向右子树走
node* parent = cur->_parent;
//当前节点的右子树不为空，寻找右子树的最小节点(最左节点)
if (cur->_right)
{
node* subLeft = cur->_right;
while (subLeft->_left) {
subLeft = subLeft->_left;
}
_node = subLeft;
}
else //右子树为空，说明所在子树的左子树、根、右子树都被走完，向上层的根走
{
while (parent)
{
//此时cur处于parent的左子树，parent为“上层的根”，即_node的下一个位置
if (cur == parent->_left) {
break;
}
else //继续寻找上层的根
{
cur = cur->_parent;
parent = parent->_parent;
}
}
_node = parent; //当parent最终为空时，说明整棵树被走完，返回nullptr作为end迭代器
}
return *this;
}红黑树的后退操作走的是中序遍历的逆过程，即“右子树 根 左子树”，其他细节与前进操作类似。
Self& operator--()
{
node* cur = _node; //视当前节点为根，向左子树寻找
node* parent = cur->_parent;
if (cur->_left) //左子树不为空
{
//向左寻找最大的节点(最右节点)
node* subRight = cur->_left;
while (subRight->_right) {
subRight = subRight->_right;
}
_node = subRight;
}
else //左子树为空，说明当前子树的右子树、根、左子树都被走完，向上层的根走
{
while (parent && cur == parent->_left)
{
//cur为parent的右子树，将_node直接调整为parent即可
if (cur == parent->_right) {
break;
}
else
{
cur = cur->_parent;
parent = parent->_parent;
}
}
_node = parent;
}
return *this;
}比较迭代器时只需要比较对应的_node即可。
bool operator==(const Self& it) const
{
return _node == it._node;
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}红黑树的元素操作
元素查找
查找元素时，以Key按照二叉搜索树的性质查找即可。
/*…………*/
iterator find(const Key& k) const
{
node* cur = _root;
KeyOfT kot; //实例化出一个仿函数对象
//按照二叉搜索树的性质进行遍历查找
while (cur)
{
if (k < kot(cur->_data)) {
cur = cur->_left;
}
else if (k > kot(cur->_data)) {
cur = cur->_right;
}
else {
return cur;
}
}
return nullptr;
}
/*…………*/插入操作
红黑树的插入操作分为两步：插入新节点，判断和调整平衡。插入新节点的过程与二叉搜索树的插入过程相同，按照二叉搜索树的性质找到合适的插入位置并插入即可。当插入节点后，如果树节点的着色情况破坏了红黑树的性质，则需要对树进行调整。
由性质d，如果插入的新节点的颜色是黑色，那么插入后，从根节点到该新节点的黑色节点数量就比其他路径多 1，使整个红黑树被破坏，所以为了在插入后尽量保持红黑树的性质，将新节点的颜色设置为红色。
std::pair<iterator, bool> insert(const T& data)
{
node* newNode = new node(data);
if (_root == nullptr)
{
_root = newNode;
_root->_color = BLACK;
return std::make_pair(_root, true);
}
KeyOfT kot;
node* cur = _root;
node* parent = nullptr;
//寻找合适的插入位置
while (cur)
{
if ((kot(data)) < (kot((cur->_data))))
{
parent = cur;
cur = cur->_left;
}
else if ((kot(data)) > (kot((cur->_data))))
{
parent = cur;
cur = cur->_right;
}
else {
return std::make_pair(cur, false);
}
}
//进行比较和节点链接
if (kot(data) < kot(parent->_data)) {
parent->_left = newNode;
}
else {
parent->_right = newNode;
}
newNode->_parent = parent;
/*…………*/红黑树的平衡调整
将新的红色节点插入到树中之后，如果新节点的父亲为红色，则需要对树进行调整。为了方便描述，假设新节点(当前调整的节点)为C，新节点的父亲节点为P，祖父节点为G，叔叔节点为U，下面大体分两种情况自下而上对树进行调整。
- U节点存在(不为空)且为红色。将 P 和 U 置为黑色，同时为了保证路径中黑色节点数目相等，将G置为红色。此时以G为根的子树已是一颗红黑树，继续向上判断和调整，不结束。
- U节点存在且为黑色，或者U不存在(为空)。此时需要以G为根对树进行旋转和变色，具体分为以下几种情况：
- P为G的左，且C为P的左，此时进行右单旋；
- P为G的左，且C为P的右，此时进行右双旋；
- P为G的右，且C为P的右，此时进行左单旋；
- P为G的右，且C为P的左，此时进行左双旋
完成旋转后，需要对树进行颜色调整，调整原则为，将旋转后的新根置为黑色，将新根的两个孩子节点置为红色，结束。
/*…………*/
//调整平衡
cur = newNode;
parent = cur->_parent;
while (parent && parent->_color == RED)
{
node* grandFather = parent->_parent;
if (parent == grandFather->_left)
{
node* uncle = grandFather->_right;
//U存在且为红色
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
grandFather->_color = RED;
//继续向上检查调整，直到parent的颜色为红色
cur = grandFather;
parent = cur->_parent;
}
else //uncle存在且为黑 或者 uncle不存在
{
if (cur == parent->_left)
{
RotateRight(grandFather); //右单旋
parent->_color = BLACK; //颜色调整
grandFather->_color = RED;
}
else if (cur == parent->_right)
{
//右双旋
RotateLeft(parent);
RotateRight(grandFather);
cur->_color = BLACK;
grandFather->_color = RED;
}
else {
assert(false);
}
break; //旋转后结束，停止调整
}
}
else //parent == grandFather->_right
{
node* uncle = grandFather->_left;
//U存在且为红色
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
grandFather->_color = RED;
//继续向上调整
cur = grandFather;
parent = cur->_parent;
}
else //U存在且为黑色 或者 U不存在
{
if (cur == parent->_right)
{
RotateLeft(grandFather); //左单旋
parent->_color = BLACK; //颜色调整
grandFather->_color = RED;
}
else if (cur == parent->_left)
{
//左双旋
RotateRight(parent);
RotateLeft(grandFather);
cur->_color = BLACK;
grandFather->_color = RED;
}
else {
assert(false);
}
break; //旋转后结束判断
}
}
}
_root->_color = BLACK; //保持_root的颜色为黑色
/*…………*/红黑树的合法性检验
为了方便测试，这里给出一个检验红黑树是否合法的接口，根据红黑树的性质对树进行检查。
/*…………*/
bool is_RB_tree() const
{
//_root是黑色的
//一个红色节点的父亲和两个孩子一定是黑色节点
//从任意节点开始的路径中黑色节点数量相等
if (_root->_color == RED) {
return false; //检查根节点的颜色
}
node* cur = _root;
int controlValue = 0;
//以最左路径中的黑色节点数量作为基准值，检查其他路径中的黑色节点数目
//是否与该基准值相等
while (cur)
{
if (cur->_color == BLACK) {
++controlValue;
}
cur = cur->_left;
}
int blackNum = 0;
//递归检查树的着色情况
return _is_RB_tree(_root, controlValue, blackNum);
}
private:
bool _is_RB_tree(node* root, int controlValue, int blackNum)
{
//认为空树平衡
if (root == nullptr) {
return true;
}
//存在两个连续的红色节点，false
if (root->_color == RED && root->_parent->_color == RED) {
return false;
}
//黑色节点数量 +1
if (root->_color == BLACK) {
++blackNum;
}
//判断该条路径中的黑色节点数量
if (root->_left == nullptr && root->_right == nullptr && blackNum != controlValue) {
return false;
}
//递归判断左右子树
return _is_RB_tree(root->_left, controlValue, blackNum) &&
_is_RB_tree(root->_right, controlValue, blackNum);
}
/*…………*/
