【C++】实现红黑树

一、认识红黑树

1.1 概念

红黑树是一个二叉搜索树，与AVL树相比，红黑树不再使用平衡因子来控制树的左右子树高度差，而是用颜色来控制平衡，颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色，就可以确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的规则：

• 根节点是黑色的
• 不能有连续的红色节点
• 从某个节点出发，每条路径上的黑色节点的数量相同

1.2 定义

红黑树也是三叉链结构（左指针、右指针和父亲指针），有一个新的存储位来记录节点的颜色，这里实现的红黑树是kv模型。

enum Colour
{RED,//红色BLACK//黑色
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr),_kv(kv),_col(RED)//默认的新节点都是红色的{}
};

二、实现红黑树

2.1 插入

红黑树的插入的与普通二叉搜索树的插入逻辑是一样的，不同的是插入新节点后要进行变色处理，符合前面的规则才行。
红黑树的插入一共分为两大类：

1. 新插入的节点的父节点是黑色的，插入结束
2. 新插入的节点的父节点是红色的，要变色处理

也就是说要看新插入的节点的父节点的颜色来确定是否本次插入结束。但是有个问题，新插入的节点说什么颜色的？其实看图就可以知道，插入的新节点必须是红色的，因为如果插入的是黑色节点，那么必然会导致每条路径上的黑色节点数量不相同，违反规则。

接下来看红黑树插入节点时是怎样变色的：
首先按照前面插入的两大类，如果插入节点的父节点是黑色的，就不需要进入变色调整；反之，如果插入节点的父节点存在且是红色的，说明此时有连续的红色节点，要变色处理。

这里需要定义几个节点的名字，方便叙述和画图：

• c（cur）——当前新插入的节点
• p（parent）——插入节点的父节点
• g（grandfather）——父节点的父节点
• u（uncle）——叔叔节点，父节点的另一边的节点

这4个节点主要看叔叔节点，根据叔叔节点分为两种情况。

情况一：叔叔存在且为红
p和u要变成黑色，g变成红色。如果g不是根节点，要向上更新，把g当成c；如果g是根节点，要把g变成黑色的，因为根节点必须是黑的。

1️⃣g是根节点

注意：不管p或者u是g的左边还是右边都是一样的，c在p的左边/右边都是一样的操作，不影响。

2️⃣g不是根节点

情况二：叔叔不存在或者叔叔存在且为黑

情况二里面又有4种变色方式（其实与其说是变色方式，不如直接说是旋转方式不同然后根据旋转情况来变色）

1️⃣p是g的左孩子，c是p的左孩子
进行右单旋，p变黑，g变红


上图的c不是新增，表示的是当它的叔叔节点u存在且为黑时的c不是新增。

注意：
这里u存在或者不存在也有两种情况，第一张图的c是新增的节点，u必然是不存在的，如果存在，会导致每条路径的黑色节点数量不相同；同理，第二张图的c刚开始是黑色的节点，它有自己的子树，是通过后面的向上变色处理才变红的，所以第二张图的u是必须存在的。总之一句话，u存不存在要符合规则

后面就以u不存在的情况处理
2️⃣p是g的右孩子，c是p的右孩子
进行左单旋，p变黑，g变红

3️⃣p是g的左孩子，c是p的右孩子
先左单旋§，再右单旋(g)，g变红，c变黑

4️⃣p是g的右孩子，c是p的左孩子
先右单旋§，再左单旋(g)，g变红，c变黑

代码：

//插入
bool Insert(const pair<K, V>& kv)
{//为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点都是黑色的，特殊处理return true;}//非空Node* cur = _root;Node* parent = nullptr;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){Node* grandfather = parent->_parent;//爷爷节点//父节点在爷爷节点的左边，那么叔叔节点在右边if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一：叔叔存在且为红if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle->_col = parent->_col = BLACK;cur = grandfather;//爷爷不是根，向上更新parent = cur->_parent;}//情况二：叔叔不存在/存在且为黑else{//单旋if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;//变色grandfather->_col = RED;}//左右双旋 // cur == parent->_rightelse{RotateL(parent);//先左单旋RotateR(grandfather);//再右单旋grandfather->_col = RED;//变色cur->_col = BLACK;}}}else//父节点在右边，叔叔在左边{Node* uncle = grandfather->_left;//情况一：叔叔存在且为红if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle->_col = parent->_col = BLACK;cur = grandfather;//爷爷不是根，向上更新parent = cur->_parent;}//情况二：叔叔不存在/存在且为黑else{//单旋if (cur == parent->_right){RotateL(grandfather);//左单旋parent->_col = BLACK;//变色grandfather->_col = RED;}//右左双旋 // cur == parent->_leftelse{RotateR(parent);//先右单旋RotateL(grandfather);//再左单旋grandfather->_col = RED;//变色cur->_col = BLACK;}break;//经过情况二后跳出}}}_root->_col = BLACK;//统一处理，根必须是黑的return true;
}//左单旋
void RotateL(Node* parent)
{RotateSize++;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;//不为空if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;//处理parent如果为根if (parent == _root){_root = subR;subR->_parent = nullptr;}//不为根，处理与ppnode的连接else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}
}//右单旋
void RotateR(Node* parent)
{RotateSize++;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//不为空if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}
}

2.2 与AVL树对比

红黑树与AVL树都是平衡二叉树，那为什么现实中绝大部分是使用红黑树，很少使用AVL树？下面我们来作数据对比，从两者的旋转次数、插入时间、平衡状态和高度来作分析。

测试代码：

RBTree<int, int> t1;
AVLTree<int, int> t2;const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));for (size_t i = 0; i < N; i++)
{v.push_back(rand() + i);
}size_t begin1 = clock();
for (auto e : v)
{t1.Insert(make_pair(e, e));
}
size_t end1 = clock();size_t begin2 = clock();
for (auto e : v)
{t2.Insert(make_pair(e, e));
}
size_t end2 = clock();
//旋转次数
cout << "RBTree RoateSize:" << t1.getRotateSize() << endl;
cout << "AVLTree RoateSize:" << t2.getRotateSize() << endl;
//插入时间
cout << "RBTree Insert:" << end1 - begin1 << endl;
cout << "AVLTree Insert:" << end2 - begin2 << endl;
//平衡状态
cout << "RBTree IsBalance:" << t1.IsBalance() << endl;
cout << "AVLTree IsBalance:" << t2.IsBalance() << endl;
//树的高度
cout << "RBTree Height:" << t1.Height() << endl;
cout << "AVLTree Height:" << t2.Height() << endl;
//树的节点个数
cout << "RBTree Size:" << t1.Size() << endl;
cout << "AVLTree Size:" << t2.Size() << endl;

插入一千万个数据，运行结果：

可以发现，红黑树的旋转次数比AVL树少，插入时间相差不大，两种树都是平衡的，红黑树的高度略高一些。

总结：
由于高度上红黑树不会高出多少，所以搜索效率影响不大。从树的高度可知，AVL树是极致追求平衡的，所以要频繁的进行旋转，这也导致旋转次数明显比红黑树多，因此在旋转上开销较大，不及红黑树的性能更优越些，同时红黑树实现比较简单，所以实际运用中红黑树更多。