红黑树的介绍与实现

前言

前面我们介绍了AVL树，AVL树是一棵非常自律的树，有着严格的高度可控制！但是正它的自律给他带来了另一个问题，即虽然他的查找效率很高，但是插入和删除由于旋转而导致效率没有那么高。我们上一期的结尾说过经常修改的话就不太适合AVL树了，而红黑树更加适合！OK，本期就来介绍一下赫赫有名的红黑树！

本期内容介绍

什么是红黑树

红黑树的实现

红黑树的效率分析以及应用

什么是红黑树？

红黑树是1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的 " 红黑树 "。

红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位表示结点的颜色，可以是红色或是黑色；通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径比其他的路径长出两倍，因而是接近平衡的！

OK，这就是一棵红黑树：

最长节点的路径就是一黑一红的交替，最短的就是两黑：

红黑树的性质

1、每个结点要么是红色，要么是黑色

2、根节点是黑色

3、如果一个结点是红色，则它的两个孩子结点是黑色

4、对于任意一个节点，从该结点到其所有的后代叶子结点的简单路径上，均包含相同的黑色结点

5、每个叶子结点就是黑色的（此处的叶子结点指的是空节点）

上面的这5条性质就是限制红黑树平衡的规则！其中4最重要的下来是3，基本所有的操作都是围着4进行的！！！

红黑树的实现

OK，上面介绍了红黑树是一种二叉搜索树，只不过是在每个结点添加了一个存储颜色的颜色位，所以它的大框架还是和搜索树一样的，所以我们就先搭一个框架出来！

enum Col//颜色
{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;//数据域Col _col;//颜色RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//新插入的节点默认是红色{}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr),_size(0){}private:Node* _root;//根节点size_t _size;//节点的数量
};

思考：新插入的节点应该是红色还是黑色？为什么？

新插入的节点一定是红色！

因为新插入的节点是红色可能违反性质3，但一定不违反性质4！

如果新插入的是黑色，一定违反性质4，也就是在部分子路径上增加了黑色节点。所以插入的新节点一定是红色，即使红色违反了性质3也是比较好控制的！

OK，这里依旧是采用的三叉链，原因是方便找父亲：

红黑树的插入

上面介绍了，红黑树的本质是一种二叉搜索树，所以先不管它的颜色和高度如何调节，先把搜索树的那一套给整出来：

bool Insert(const pair<K, V>& kv)
{Node* cur = _root;//当前节点Node* parent = nullptr;//插入位置的父亲//第一次插入if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点是黑色return true;}//寻找插入的位置while (cur){if (cur->_kv.first < kv.first)//插入节点的key比当前节点的key大{parent = cur;cur = cur->_right;//去右边找}else if(cur->_kv.first > kv.first)//插入节点的key比当前节点的key小{parent = cur;cur = cur->_left;//去左边找}else{return false;//插入的节点存在}}//找到插入位置cur = new Node(kv);//链接if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//颜色和高度调整//....return true;
}

OK，还是先来验证一下当前的逻辑对不对，所以走个中序看看是不是有序即可：由于中序要根节点，而类外面是无法访问的，所以我们还是和以前一样搞成子函数或提供get和set方法；这里就搞成子函数了：

中序遍历

void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);
}

OK，没问题，下面我们就来讨论一下红黑树的维持平衡的方式:变色和旋转！

红黑树的变色和旋转

由于新插入的节点一定是红色的，此时分为两种情况，1、父亲为黑 2、父亲为红

如果父亲为黑，不违反任何性质，插入结束；

如果父亲为红，看看叔叔，此时叔叔有三类情况：1、叔叔存在且为红 2、叔叔不存在 3、叔叔存在为黑

如果，叔叔存在且为红：变色（将父亲和叔叔变黑色，将爷爷变红色），继续更新

如果，叔叔不存在或存在且为黑，旋转 + 变色（如果孩子是父亲的左/右，先对孩子父亲进行左/右旋，在对爷爷进行左/右）

OK，这里看着可能会有些迷，看看下面的导图会很清楚：

OK，理解了上述的表达，下面我来画图解释一下：

parent是黑色插入结束

parent为红，叔叔存在且为红（变色）

父亲和叔叔变黑，爷爷变红，继续向上更新

这里只画了parent在爷爷的左边的情况，如果parent在爷爷的右边和这个是一样的！

parent为红，叔叔不存在会存在为黑（变色 + 旋转）

如果parent在爷爷的左，且cur在父亲的左，对爷爷进行右单旋；

如果parent在爷爷的左，且cur在父亲的右，先对parent左单旋，在对爷爷进行右单旋；

如果parent在爷爷的右，且cur在父亲的右，对爷爷进行左单旋；

如果parent在爷爷的右，且cur在父亲的左，先对parent右单旋，在对爷爷进行左单旋；

OK，废话不多说直接上代码：

bool Insert(const pair<K, V>& kv)
{Node* cur = _root;//当前节点Node* parent = nullptr;//插入位置的父亲//第一次插入if (_root == nullptr){_root = new Node(kv);_size++;//插入成功节点数+1_root->_col = BLACK;//根节点是黑色return true;}//寻找插入的位置while (cur){if (cur->_kv.first < kv.first)//插入节点的key比当前节点的key大{parent = cur;cur = cur->_right;//去右边找}else if(cur->_kv.first > kv.first)//插入节点的key比当前节点的key小{parent = cur;cur = cur->_left;//去左边找}else{return false;//插入的节点存在}}//找到插入位置cur = new Node(kv);//链接if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = 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;parent->_col = uncle->_col = BLACK;//继续向上调整cur = grandfather;parent = cur->_parent;}else//叔叔不存在或存在但为黑 -> 变色 + 旋转{if (cur == parent->_left)//cur在父亲的左{//		   g//	   p		u// cRotateR(grandfather);//旋转parent->_col = BLACK;//变色grandfather->_col = RED;}else//cur在父亲的右{//		  g//	  p		  u//        cRotateL(parent);//旋转RotateR(grandfather);cur->_col = BLACK;//变色grandfather->_col = RED;}break;//旋转后不需要再向上更新了}}else//parent在爷爷的右{Node* uncle = grandfather->_left;//叔叔在父亲的左//叔叔存在且为红 -> 变色if (uncle && uncle->_col == RED){grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续向上调整cur = grandfather;parent = cur->_parent;}else//叔叔不存在或存在但为黑 -> 变色 + 旋转{if (cur == parent->_left)//cur在父亲的左 {//		  g//	  u		   p//        cRotateR(parent);//旋转RotateL(grandfather);cur->_col = BLACK;//变色grandfather->_col = RED;}else{//		  g//	  u		   p//                 cRotateL(grandfather);//旋转parent->_col = BLACK;//变色grandfather->_col = RED;}break;//旋转后不需要再向上更新了}}}_root->_col = BLACK;//保证根节点永远是黑色_size++;//插入成功节点数+1return true;
}

旋转

红黑树的旋转没有，AVL的复杂，只有左右单旋且没有平衡因子！整体的逻辑和AVL一样的，这里不在详细介绍了！

void RotateR(Node* parent)
{Node* subL = parent->_left;//父亲的左Node* subLR = subL->_right;//左子树的右Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接parent->_left = subLR;//将左子树的右给父亲的做if (subLR)subLR->_parent = parent;subL->_right = parent;//parent做左子树的右parent->_parent = subL;if (parent == _root)//parent是根{_root = subL;//此时的新根就是subLppNode = nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}
}void RotateL(Node* parent)
{Node* subR = parent->_right;//父亲的右Node* subRL = subR->_left;//右子树的左Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接parent->_right = subRL;//将右子树的左连接到parent的右if (subRL)subRL->_parent = parent;subR->_left = parent;//parent连接到subR的左parent->_parent = subR;if (parent == _root)//parent是根{_root = subR;//此时的新根就是subRppNode = nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}
}

OK，我们验证一下，判断一下是否是平衡的：

是否平衡

先获取任意一条路径的黑色节点，然后通过dfs进行检查每个结点是不是符合红黑树的规则！

如果出现连续的红色节点，不符合！判断方式：当出现红色节点时，检查其父节点是否是红色的，如果是则不符合！

如走到空了，检查该条路径的黑色节点和一开始求出的是否一致，不一致则不符合！

当前节点符合，去检查其左右！

bool IsBalance()
{if (_root && _root->_col == RED){return false;//根为红，一定不是红黑树}int black = 0;//获取任意一条路径的黑色节点（这里是最左路）Node* cur = _root;while (cur){if (cur->_col == BLACK){black++;}cur = cur->_left;}return Check(_root, black, 0);
}

bool Check(Node* root, const int black, int num)
{if (root == nullptr){//当走到叶子节点的时候和其他路径的黑色节点的个数不一样if (black != num){return false;}return true;}//存在连续的红色节点if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << " ：存在连续的红色节点" << endl;return false;}//遇到黑色节点++if (root->_col == BLACK){num++;}//当前节点符合红黑树，它的左右子树也要都符合return Check(root->_left, black, num) && Check(root->_right, black, num);
}

OK，验证一下：

OK，么有问题！下面把其他的接口补一下！

Size

由于我们提前记录了_size所以直接返回成员_size即可！

size_t Size()
{return _size;
}

Find

和以前的搜索树一样，大了去右边找，小了去左边找！

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key)//插入节点的key比当前节点的key大{cur = cur->_right;//去右边找}else if (cur->_kv.first > key)//插入节点的key比当前节点的key小{cur = cur->_left;//去左边找}else{return cur;//找到了}}return nullptr;//没找到
}

再来一组随机的测试用例：插入1亿个随机值，看看时间和是否平衡（注意这里一亿个节点在32位debug下可能内存空间不够，可以把他改成64的release地址空间大一点）

void Test()
{const int N = 100000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);//cout << v.back() << endl;}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();cout << "time :" << end2 - begin2 << endl;cout << t.IsBalance() << endl;
}

红黑树的删除：请参考这篇博客：红黑树的删除

全部源码

#pragma onceenum Col//颜色
{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;//数据域Col _col;//颜色RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//新插入的节点默认是红色{}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr),_size(0){}bool Insert(const pair<K, V>& kv){Node* cur = _root;//当前节点Node* parent = nullptr;//插入位置的父亲//第一次插入if (_root == nullptr){_root = new Node(kv);_size++;//插入成功节点数+1_root->_col = BLACK;//根节点是黑色return true;}//寻找插入的位置while (cur){if (cur->_kv.first < kv.first)//插入节点的key比当前节点的key大{parent = cur;cur = cur->_right;//去右边找}else if(cur->_kv.first > kv.first)//插入节点的key比当前节点的key小{parent = cur;cur = cur->_left;//去左边找}else{return false;//插入的节点存在}}//找到插入位置cur = new Node(kv);//链接if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = 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;parent->_col = uncle->_col = BLACK;//继续向上调整cur = grandfather;parent = cur->_parent;}else//叔叔不存在或存在但为黑 -> 变色 + 旋转{if (cur == parent->_left)//cur在父亲的左{//		   g//	   p		u// cRotateR(grandfather);//旋转parent->_col = BLACK;//变色grandfather->_col = RED;}else//cur在父亲的右{//		  g//	  p		  u//        cRotateL(parent);//旋转RotateR(grandfather);cur->_col = BLACK;//变色grandfather->_col = RED;}break;//旋转后不需要再向上更新了}}else//parent在爷爷的右{Node* uncle = grandfather->_left;//叔叔在父亲的左//叔叔存在且为红 -> 变色if (uncle && uncle->_col == RED){grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续向上调整cur = grandfather;parent = cur->_parent;}else//叔叔不存在或存在但为黑 -> 变色 + 旋转{if (cur == parent->_left)//cur在父亲的左 {//		  g//	  u		   p//        cRotateR(parent);//旋转RotateL(grandfather);cur->_col = BLACK;//变色grandfather->_col = RED;}else{//		  g//	  u		   p//                 cRotateL(grandfather);//旋转parent->_col = BLACK;//变色grandfather->_col = RED;}break;//旋转后不需要再向上更新了}}}_root->_col = BLACK;//保证根节点永远是黑色_size++;//插入成功节点数+1return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key)//插入节点的key比当前节点的key大{cur = cur->_right;//去右边找}else if (cur->_kv.first > key)//插入节点的key比当前节点的key小{cur = cur->_left;//去左边找}else{return cur;//找到了}}return nullptr;//没找到}void InOrder(){return _InOrder(_root);}size_t Size(){return _size;}bool IsBalance(){if (_root && _root->_col == RED){return false;//根为红，一定不是红黑树}int black = 0;//获取任意一条路径的黑色节点（这里是最左路）Node* cur = _root;while (cur){if (cur->_col == BLACK){black++;}cur = cur->_left;}return Check(_root, black, 0);}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateR(Node* parent){Node* subL = parent->_left;//父亲的左Node* subLR = subL->_right;//左子树的右Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接parent->_left = subLR;//将左子树的右给父亲的做if (subLR)subLR->_parent = parent;subL->_right = parent;//parent做左子树的右parent->_parent = subL;if (parent == _root)//parent是根{_root = subL;//此时的新根就是subLppNode = nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void RotateL(Node* parent){Node* subR = parent->_right;//父亲的右Node* subRL = subR->_left;//右子树的左Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接parent->_right = subRL;//将右子树的左连接到parent的右if (subRL)subRL->_parent = parent;subR->_left = parent;//parent连接到subR的左parent->_parent = subR;if (parent == _root)//parent是根{_root = subR;//此时的新根就是subRppNode = nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}bool Check(Node* root, const int black, int num){if (root == nullptr){//当走到叶子节点的时候和其他路径的黑色节点的个数不一样if (black != num){return false;}return true;}//存在连续的红色节点if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << " ：存在连续的红色节点" << endl;return false;}//遇到黑色节点++if (root->_col == BLACK){num++;}//当前节点符合红黑树，它的左右子树也要都符合return Check(root->_left, black, num) && Check(root->_right, black, num);}private:Node* _root;//根节点size_t _size;//节点的数量
};