C++简单实现红黑树

目录

一、概念

二、红黑树的性质

三、红黑树的定义

四、红黑树的插入操作

情况一（叔叔节点存在且为红色）——变色+向上调整：

情况二（叔叔节点不存在或为黑色）——旋转+变色：

2.1叔叔节点不存在

2.2叔叔节点为黑色

插入的代码实现：

五、红黑树的验证

六、红黑树完整代码

---

一、概念

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

二、红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点）

三、红黑树的定义

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响{}pair<K, V> _kv;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _parent;Colour _col;
};

C++STL中的set和map底层就是使用红黑树实现的，而map是存放键值对的，所以我们给红黑树的节点中的值存放一个键值对，以及左右孩子的指针和指向父节点的指针，还有一个存放颜色的标记。

四、红黑树的插入操作

红黑树的插入首先和普通二叉搜索树的插入操作一样，新建一个节点，左节点的值小于根，右节点的值大于根，找到位置进行插入。插入后应如果破坏了红黑树的性质，就需要进行调整。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：

我们给出一个约定：cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点

情况一（叔叔节点存在且为红色）——变色+向上调整：

将p和u改成黑色，将g改为红色

此时有三种情况：

1、g没有父亲节点，直接变成黑色就可以，插入结束；

2、g有父亲节点，且父亲为黑色，插入结束；

3、g有父亲节点，且父亲为红色（违反了红色节点不能连续的性质），需要向上调整。

情况二（叔叔节点不存在或为黑色）——旋转+变色：

2.1叔叔节点不存在

如果cur在parent的左边——右旋：

cur在parent的右边——先左旋再右旋：

2.2叔叔节点为黑色

如果cur在parent的左边——右旋：

cur在parent的右边——先左旋再右旋：

以上插入操作是p在g节点左边的情况，p在g节点右边的情况与以上插入过程类似，仅仅是镜像翻转一下。

插入的代码实现：

左旋代码：

void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

右旋代码：

void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

插入代码：

    bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//插入Node* cur = _root;Node* parent = cur;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 (grandfather->_left == parent){Node* uncle = grandfather->_right;//叔叔存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在或者为黑色——旋转+变色else{//右单旋即可if (parent->_left == cur){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//先左单旋，后右单旋else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}//叔叔在左else{Node* uncle = grandfather->_left;//uncle存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//uncle不存在或为黑色——旋转+变色else{//左单旋即可if (parent->_right == cur){RotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}//先右单旋，再左单旋else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

五、红黑树的验证

    bool isBalance(){return _isBalance(_root);}bool checkcolour(Node* root, int benckmark, int blackcount){if (root == nullptr){if (blackcount != benckmark)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED)return false;if (root->_col == BLACK)++benckmark;return checkcolour(root->_left, benckmark, blackcount)&& checkcolour(root->_right, benckmark, blackcount);}bool _isBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;//求树中最左路径黑色节点的个数while (cur){if (cur->_col == BLACK)++blackcount;cur = cur->_left;}return checkcolour(_root, 0, blackcount);}

六、红黑树完整代码

#pragma once#include <iostream>
#include <vector>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响{}pair<K, V> _kv;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _parent;Colour _col;
};
/*
* 红黑树插入思路——关键在于uncle节点：
* 分为两大类：
* 一、如果uncle存在且为红色——仅仅变色即可
* 
*	       g(黑)                            g(红)     
*     p(红)     u(红)    ------->       p(黑)      u(黑) ------->继续向上更新
*  c(红)                            c(红)
* 
* 
* 二、如果uncle不存在或为黑色——旋转加变色
* 
* 情况一：       g(黑)                              p(红)
*            p(红)    NULL/黑  ------->       c(红)       g(黑)
*         c(红)
* 
*        仅仅右旋即可，g变成红色; p变成黑色;  break;
* 
* 情况二：       g(黑)                                  g(黑)                c(红)
*			 p(红)    NULL/黑  ------->   先左旋     c(红)    ------->   p(红)    g(黑) 
*               c(红)                             p(红)
* 
*        c变成黑色，g变成红色，break;
* 
* 情况三：情况一的对称图形
* 情况四：情况二的对称图形
* 
*/
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}void InOrder(){cout << "InOrder: ";_InOrder(_root);cout << endl;}bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//插入Node* cur = _root;Node* parent = cur;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 (grandfather->_left == parent){Node* uncle = grandfather->_right;//叔叔存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在或者为黑色——旋转+变色else{//右单旋即可if (parent->_left == cur){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//先左单旋，后右单旋else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}//叔叔在左else{Node* uncle = grandfather->_left;//uncle存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//uncle不存在或为黑色——旋转+变色else{//左单旋即可if (parent->_right == cur){RotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}//先右单旋，再左单旋else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}bool isBalance(){return _isBalance(_root);}private:bool checkcolour(Node* root, int benckmark, int blackcount){if (root == nullptr){if (blackcount != benckmark)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED)return false;if (root->_col == BLACK)++benckmark;return checkcolour(root->_left, benckmark, blackcount)&& checkcolour(root->_right, benckmark, blackcount);}bool _isBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;while (cur){if (cur->_col == BLACK)++blackcount;cur = cur->_left;}return checkcolour(_root, 0, blackcount);}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}
private:Node* _root;int blackcount = 0;
};

测试：

运行结果：

之后更新红黑树的应用，用红黑树封装map和set。