目录
红黑树的概念
红黑树的性质
红黑树的查找效率
红黑树的实现
红黑树的定义
红黑树节点的插入
红黑树的平衡调整
判断红黑树是否平衡
红黑树整体代码
测试代码
上期我们学习了AVL树的模拟实现，在此基础上，我们本期将学习另一个数据结构------红黑树。我们知道，AVL树的插入伴随着节点的旋转，那么红黑树是否在插入节点时也要进行旋转呢？这便是我们本期要学习的内容。
红黑树的概念
红黑树和AVL树一样，也是一种二叉搜索树，红黑树的每一个节点存储一个数据，表示该节点的颜色，为红色或者黑色。通过红黑树的性质作为约束，红黑树的最长路径的长度不会超过最短路径长度的二倍。红黑树图示如下。
红黑树的性质
- 红黑树的节点，不是红色就是黑色。
- 红黑树的根节点一定是黑色的。
- 红黑树中，如果一个节点是红色的，那么它的孩子节点一定是黑色的。（也就是说，红黑树中不能出现连续的两个红色节点）
- 红黑树的任意一个节点到其所有叶子节点的所有路径上的黑色节点的个数一定是相同的。
- 红黑树的叶子节点一定是黑色的。（这个叶子节点不是传统意义的叶子节点，而是如上图所示的NIL空节点）
Q1:为什么通过红黑树的上述性质作为约束，能够保证红黑树的最长路径的长度不超过最短路径长度的2倍呢？
A1:其实决定上述条件的是红黑树性质中的3和4条。假设红黑树的每个路径的黑色节点的个数是4，极端情况下，红色树的最短路径就是4个黑色节点，最长路径就是1黑1红，总共4组，8个节点，所以就可以推出，红黑树的最长路径的长度不超过最短路径长度的2倍。
红黑树的查找效率与AVL树的比较
再学习AVL树时，我们知道了AVL树理想条件下其实就是一颗完全二叉树，所以对于有N个节点的完全二叉树，它的高度为logN，所以对于AVL树而言，它的查找效率是logN。
对于红黑树而言，假设红黑树的每条路径的黑色节点的个数为X，所以红黑树的高度h的范围为X<=h<=2X。假设红黑树的节点的个数为N，则N的范围为2^X-1<=N<=2^2X-1,从而得到X的取值范围为1/2logN<=X<=logN。所以对于具有N个节点的红黑树而言，红黑树的高度最高为2logN，红黑树也是搜索二叉树，所以红黑树的查找效率为2logN。
通过上述比较，不难看出，红黑树的查找效率远不及AVL树，所以我们应该是经常使用AVL树的。嗯？真的是我们想的这样吗，真的是AVL树的使用更为广泛吗？
实际上并不是这样，AVL树的查找效率固然很高，但是查找效率高的同时带来的代价也是很大的，因为AVL是高度平衡的二叉树，有时候插入一个元素往往需要旋转多次，但是对于红黑树而言，只要插入的节点的颜色不违反红黑树的性质，我们是不用进行旋转的。我们可以认为，AVL树和红黑树在插入节点时，AVL树中插入节点更容易违反性质，所以AVL插入元素时旋转的概率是远远比红黑树要高的，所以即使AVL树的查找效率更高，但是对于以数亿次运算的CPU看来，logN和2logN几乎是没有差异的，所以一般情况下，我们应用红黑树的场景更多。
红黑树的实现
红黑树的定义
代码如下。
//枚举类型，代表红黑树节点的颜色。
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){}};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}private:Node* _root;};红黑树节点的插入
查找合适的位置进行节点的插入，代码如下。
//如果当前红黑树为空，则直接插入即可if (_root == nullptr){_root = new Node(pair);_root->_col = BLACK;return true;}//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入Node* cur = _root;Node* parent = _root->_parent;while (cur){if (cur->_kv.first > pair.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < pair.first){parent = cur;cur = cur->_right;}else{return false;printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");}}cur = new Node(pair);cur->_col = RED;cur->_parent = parent;if (cur->_kv.first > parent->_kv.first){parent->_right= cur ;}else{parent->_left= cur ;}红黑树的平衡调整
在插入一个结点时，为了对整个红黑树的影响最小，一般我们插入的都是红色节点。但是在插入红色节点时，可能会遇到很多情景，大致分为三种。
我们将插入的节点称为cur节点，将cur节点的父亲称为parent节点，将cur节点的叔叔称为uncle节点，将cur节点的祖父称为grandfather节点。在此基础上我们展开分析。
情景1：uncle节点存在且为红。
代码如下。
情景2和3，uncle节点存在为黑色或者uncle节点不存在。
代码如下。
while (parent&& parent->_col == RED){Node* grandfather = parent->_parent;//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡if (parent == grandfather->_right){Node* uncle = grandfather->_left;if (uncle&& uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_right;if (uncle&& uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}判断红黑树是否平衡
代码如下。
bool IsBalance(){if (_root && _root->_col == RED){cout<<"根节点的颜色是红色，不符合红黑树的性质";return false;}int banchmark = 0;//选取最左侧的路径的黑色节点的个数为基准值Node* left = _root;while (left){if (left->_col == BLACK){banchmark++;}left = left->_left;}int blackcount = 0;return _IsBalance(_root, banchmark, blackcount);}bool _IsBalance(Node* root, int banchmark, int blackcount){if (root == nullptr){if (banchmark != blackcount){return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout<<"出现两个连续的红节点，不符和红黑树的性质" << endl;return false;}if (root->_col == BLACK){blackcount++;}return _IsBalance(root->_left, banchmark, blackcount) && _IsBalance(root->_right,banchmark, blackcount);}
红黑树整体代码
红黑树实现代码如下。
#include<time.h>
#include<iostream>
#include<vector>
using namespace std;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){}};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}//红黑树节点的插入bool Insert(const pair<K, V>& pair){//如果当前红黑树为空，则直接插入即可if (_root == nullptr){_root = new Node(pair);_root->_col = BLACK;return true;}//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入Node* cur = _root;Node* parent = _root->_parent;while (cur){if (cur->_kv.first > pair.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < pair.first){parent = cur;cur = cur->_right;}else{return false;printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");}}cur = new Node(pair);cur->_col = RED;cur->_parent = parent;if (cur->_kv.first > parent->_kv.first){parent->_right= cur ;}else{parent->_left= cur ;}//调整平衡while (parent&& parent->_col == RED){Node* grandfather = parent->_parent;//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡if (parent == grandfather->_right){Node* uncle = grandfather->_left;if (uncle&& uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_right;if (uncle&& uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//强制性的让根节点为黑色，符合红黑树的性质_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_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 (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == NULL)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root;};测试代码
void TestRBTree()
{RBTree<int, int> t;vector<int> v;srand(time(0));int N = 10;for (int i = 0; i < N; ++i){v.push_back(rand());}for (auto e : v){t.Insert(make_pair(e, e));}t.InOrder();cout<< t.IsBalance() << endl;}运行结果如下。
运行结果符合预期。
以上便是红黑树的所有内容，较于AVL树，红黑树的应用较为广泛，后续的容器map和set以及哈希结构都是使用红黑树实现的。这些都是我们下几期要重点研究的。
本期内容到此结束^_^