红黑树
红黑树
，是一种
二叉搜索树
，但
在每个结点上增加一个存储位表示结点的颜色，可以是
Red
或
Black
。 通过对
任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍
，因而是
接近平衡
的
对比AVL树的严格平衡（左右子树高度差不超过1），需要更多的旋转才能控制这个高度
红黑树是近似平衡（最长路径不超过最短路径的2倍）
降低了插入和旋转的次数，
所以在经常进行增删的结构中性能比
AVL
树更优，而且红黑树实现比较简单，所以实际运用中红
黑树更多
红黑树的性质
1.
每个结点不是
红色
就是黑色
2.
根节点
是
黑色
的
3.
如果一个节点是红色的，则它的两个孩子结点是黑色的 ，即
不能出现连续的红节点
父子节点：黑+黑 黑+红 红+黑
4.
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
即
每条路径都包含相同数量的黑节点
5.
每个叶子结点都是黑色的
(
此处的叶子结点指的是空结点
)
即NIL节点，方便数路径，不容易出错
红黑树的插入
新增节点的颜色默认给红色
因为新增节点若为黑色节点，插入后会影响所有路径（红黑树的性质规定每条路径必须有相同数量的黑色节点）
而新增插入红色节点只会影响父节点，（父子节点的组合：黑+黑，黑+红，红+黑）
（若父节点为黑，则无影响，若父节点为红，则有连续的红节点，需要调整，下面会讲）
红黑树节点的设计：
enum Colour
{
RED,
BLACK
};
template<class T> // T可以是set的K，可以是map的pair<K,V>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)//新增节点默认给红色
{}
};
红黑树是在二叉搜索树的基础上加上其平衡限制条件，故而红黑树的插入分为两步：
1 插入新增节点
2 判断新增节点插入后是否需要调整红黑树
（新增节点可能会导致连续红节点的出现，破坏了红黑树的规则）
什么时候需要调整红黑树：出现了连续的红节点，即新增节点的父节点为红色节点时
（新增节点默认为红，若父节点为黑，则没有违反红黑树的任何规则，插入完成后无需处理）
约定
:cur
为当前节点，
p
为父节点，
g
为祖父节点，
u
为叔叔节点
红黑树的调整关键看叔叔节点
情况一
:
cur
为红，
p
为红，
g
为黑，
u存在且为红
（因为在cur插入之前，没有违反红黑树的任何规则，所以当p为红时，g一定为黑，不可能出现连续的红色节点）
解决方式
：将
p,u
改为黑，
g
改为红，然后把
g
当成
cur
，继续向上调整
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
在这种情况下，单纯变色无法解决问题，需要旋转+变色
解决方案：旋转（单选/双旋）+变色
需要
单旋
时的情况：
p
为
g
的左孩子，
cur
为
p
的左孩子，则进行右单旋
p
为
g
的右孩子，
cur
为
p
的右孩子，则进行左单旋
p
、
g
变色
--
p变黑，g变红
需要双旋时的情况：
p
为
g
的左孩子，
cur
为
p
的右孩子，则进行左右双旋
（先对p节点所在子树左单旋，再对g节点所在子树右单旋）
p
为
g
的右孩子，
cur
为
p
的左孩子，则进行右左双旋
（先对p节点所在子树右单旋，再对g节点所在子树左单旋）
cur，g变色--
cur变黑，g变红
代码实现：
pair<Node*, bool> Insert(const T& data)
{
//插入一个红色节点
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(cur, false);
}
}
//新增节点给红色
cur = new Node(data);
Node* newnode = cur;
if (kot(parent->_data)>kot(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//红黑树调整--有连续的红节点
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
// p u
// c
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//uncle存在且为红--变色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或者存在且为黑--旋转+变色
{
if (cur == parent->_left)//右单旋
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//左右双旋
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//parent == grandfather->_right
{
// g
// u p
// c
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//uncle存在且为红--变色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或者存在且为黑--旋转+变色
{
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 make_pair(newnode, true);
}
需要用到的左单旋 右单旋：（在AVL数的代码实现中有具体讲解）
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node*parentParent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
红黑树的验证
1. 验证
其是否满足二叉搜索树
(
中序遍历是否为有序序列
)
2. 验证
其是否满足红黑树的性质
bool IsBalance()
{
//检查根节点
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, refVal, blacknum);
}
bool Check(Node* root, const int refVal,int blacknum)
{
if (root == nullptr)
{
if (blacknum != refVal)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)//节点为黑色--统计
{
blacknum++;
}
if(root->_col == RED && root->_parent->_col == RED)//节点为红色--检查
{
cout << "有连续的红色节点" << endl;
return false;
}
return Check(root->_left, refVal, blacknum)
&& Check(root->_right, refVal, blacknum);
}
红黑树模拟实现map与set
代码：
MyMap.h
#pragma once
#include"RBTree.h"
namespace djx
{
template<class K,class V>
class map
{
public:
struct MapKeyOfT//获取关键字K，map存储的是pair<K,V>
{
const K& operator()(const pair<K, V>&kv)
{
return kv.first;
}
};
// 对类模板取内嵌类型，加typename告诉编译器这里是类型
typedef typename RBTree<K, pair<const K, V> ,MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V> ,MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
V& operator[](const K&key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;//ret.first是迭代器，能够找到节点
}
pair<iterator, bool> insert(const pair<K, V>&kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V> ,MapKeyOfT> _t;//封装红黑树
};
}
MySet.h
#pragma once
#include"RBTree.h"
namespace djx
{
template<class K>
class set
{
public:
struct SetKeyOfT//仿函数，返回关键字K，set存储的就是K
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename RBTree<K, K,SetKeyOfT>::const_iterator iterator;//set中的元素不可被修改，所以普通迭代器就用const_iterator来实现
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin()const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
RBTree.h
#pragma once
// set ->key
// map ->key/value
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode//节点
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
{}
};
template<class T,class Ref,class Ptr>
struct __TreeIterator//迭代器
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{}
Ref operator* ()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
//顺序：左 中 右
if (_node->_right)//这颗子树没有走完--找右子树的最左节点
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//这颗子树已经走完--找一个祖先（这个子树是它左孩子的祖先）
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return s._node != _node;
}
bool operator==(const Self& s)
{
return s._node == _node;
}
};
template<class K,class T,class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T&, T*> iterator;
typedef __TreeIterator<T, const T&, const T*> const_iterator;
iterator begin()//红黑树中序序列得到有序序列，begin()可设计成最左节点的迭代器
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin()const
{
Node* cur = _root;
while (cur&& cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
//返回值不能是pair<iterator, bool>，因为set的普通迭代器实际也是const_iterator，set设计insert时要返回的pair<iterator, bool> 实际是pair<const_iterator, bool> ，而封装红黑树，复用红黑树的Insert（返回值若是pair<iterator, bool>，红黑树的普通迭代器就是普通迭代器，那么因为普通迭代器iterator不能转成const_iterator，所以代码会报错）
设计成pair<Node*, bool>就很好，节点指针Node*可以通过const_iterator迭代器的构造函数完成转变
pair<Node*, bool> Insert(const T& data)
{
//插入一个红色节点
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(cur, false);
}
}
//新增节点给红色
cur = new Node(data);
Node* newnode = cur;
if (kot(parent->_data)>kot(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//红黑树调整--有连续的红节点
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
// p u
// c
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//uncle存在且为红--变色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或者存在且为黑--旋转+变色
{
if (cur == parent->_left)//右单旋
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//左右双旋
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//parent == grandfather->_right
{
// g
// u p
// c
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//uncle存在且为红--变色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或者存在且为黑--旋转+变色
{
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 make_pair(newnode, true);
}
iterator Find(const K& key)
{
//...
return end();
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node*parentParent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
bool IsBalance()//红黑树的验证
{
//检查根节点
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, refVal, blacknum);
}
bool Check(Node* root, const int refVal,int blacknum)
{
if (root == nullptr)
{
if (blacknum != refVal)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)//节点为黑色--统计
{
blacknum++;
}
if(root->_col == RED && root->_parent->_col == RED)//节点为红色--检查
{
cout << "有连续的红色节点" << endl;
return false;
}
return Check(root->_left, refVal, blacknum)
&& Check(root->_right, refVal, blacknum);
}
int Height()
{
return _Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
size_t Size()
{
return _Size(_root);
}
size_t _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
private:
Node* _root = nullptr;
};
处理设计红黑树Insert函数返回值的细节：
