C++数据结构：手撕红黑树

目录

一. 红黑树的概念及结构

二. 红黑树节点的定义

三. 红黑树节点的插入

3.1 初步查找插入节点的位置并插入节点

3.2 红黑树结构的调整

3.3 红黑树节点插入完整版代码

四. 红黑树的结构检查

4.1 检查是否为搜索树

4.2 检查节点颜色是否满足要求

附录：红黑树完整版代码

---

一. 红黑树的概念及结构

在我之前的博客C++数据结构：手撕AVL树_【Shine】光芒的博客-CSDN博客中对AVL树的结构及插入节点操作进行了分析，AVL树要求以每个节点为根节点的子树的左右子树高度差不超过1，以此来保证搜索树查找数据的时间复杂度为O(logN)。

但是，AVL树对高度差的要求过于严格，会导致在插入节点的过程中频繁进行旋转，造成数据插入效率低下。为了权衡插入数据与查找数据的效率，一种新的数据结构 -- 红黑树 被提出。相比于AVL树，红黑树对高度差的要求适当进行了放松，红黑树要求：最长路径的节点数目不超过最短路径的两倍。

红黑树的每个节点为红色或黑色，通过一定的规则控制节点颜色，来达到最长路径节点数目不超过最短路径节点数目两倍的要求，这也是红黑树名称的由来。

图1.1 红黑树的结构图

一颗结构正确的红黑树，要么为空树，要么满足一下几个条件：

1. 每个节点为红色或者黑色。
2. 根节点为黑色。
3. 如果一个节点为红色，那么它的两个根节点一定为黑色，即：红黑树中没有连续的红色节点，但是，可以有连续的黑色节点。
4. 对于每个节点，从该节点到其后代叶子结点的路径上，黑色节点的数目相同，即：每条路径的黑色节点数目相同。
5. 叶子节点都为黑色节点。（注意：这里的叶子节点是指NULL节点）

为什么满足上面几条规则就能保证最长路径不超过最短路径两倍？

• 极限最短：一条路径上全为黑色。
• 极限最长：一黑一红间隔排布。

规则4要求每条路径上黑色节点数目相同，那么极限最短路径和极限最长路径肯定具有相同数目的黑色节点，假设每条路径上黑色节点数目为N，那么极限最短路径有N个节点，极限最长路径有2N个节点，这样就满足了红黑树的路径长度的要求。

二. 红黑树节点的定义

红黑树的节点应当被定义为一个三叉链，具有三个红黑树节点指针，分别为：指向左孩子节点的指针_left、指向右孩子节点的指针_right，指向父亲节点的指针_parent。这里存储父亲节点指针的目的是为了在插入数据后检查红黑树结构是否正确以及进行变色及旋转操作。

同时，还应当定义Color枚举常量，使用_col来表示节点颜色，并存储一键值对kv来表示节点数据。

代码2.1：（红黑树节点）

//枚举常量 -- 红色、黑色
enum Color
{RED,BLACK
};//定义红黑树节点
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;std::pair<K, V> _kv;   //每个节点存储的键值对Color _col;   //节点颜色RBTreeNode(const std::pair<K, V>& kv)   //节点构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){ }
};

三. 红黑树节点的插入

3.1 初步查找插入节点的位置并插入节点

红黑树节点插入位置的查找与普通搜索二叉树和AVL树均一致，流程为：

• 如果当前位置为nullptr，那么该位置为插入节点的位置。
• 如果当前节点值大于要插入的值，到该节点的左子树去查找。
• 如果当前节点值小于要插入的值，到该节点的右子树去查找。
• 如果当前节点值等于要插入的值，则插入失败。（二叉搜索树一般不允许存在相同的节点）。

当查找到插入位置后，判断是插入到了其父亲节点的左孩子位置还是右孩子位置，将新节点与其父亲节点进行连接。

注意：新插入的节点应初步设置为红色。因为：红黑树要求每条路径上黑色节点数目相同，而如果给定新插入的节点为黑色，那么根节点的另一颗没有插入数据的子树中也要想办法增加黑色节点数目或旋转来满足结构要求，这样后期调整红黑树结构就会变得复杂。而初步设定节点为红色，只是有可能存在连续红色节点，只需调整新节点所在子树节点的颜色或进行简单旋转即可。

3.2 红黑树结构的调整

红黑树结构调整主要涉及到四个节点，通过观察下面四个节点的颜色，进行分类讨论，采取不同的方法调整红黑树结构：

1. cur节点 -- 新插入的节点。
2. p节点 -- 父亲节点，p = cur->_parent。
3. g节点 -- 祖父节点，g = p->_parent。
4. u节点 -- 叔叔节点，与p具有共同父亲节点的节点。u->_parent = p->_parent = g。

图3.1 红黑树结构调整所涉及到的节点示意图

如果p节点为黑色节点，则红黑树已经满足结构要求，不需要再进行调整，如果p节点为红色，那么则会存在连续的红色节点，要进行调整。对于如何调整，分为两大种情况及数种细分情况进行讨论：

1. cur为红，p为红，g为黑，u存在且为红。
2. cur为红，p为红，g为黑，u不存在或u存在且为黑。

由此可以看出，u的颜色是如何调整的关键所在。

情况一：cur为红，p为红，g为黑，u存在且为红。

将p节点和u节点变为黑色，将g节点变为红色，然后将cur节点更新为g节点，将p节点更新为更新为g->_parent节点，继续向上调整。

图3.2  cur为红，p为红，g为黑，u存在且为红时红黑树调整示意图

 情况二：cur为红，p为红，g为黑，u不存在或u存在且为红。

• 情况2.1：节点cur为p的左子节点，p为g的左子节点  -- 右单旋 + 变色

先对g节点进行右单旋操作，然后将p节点变为黑色，g节点变为红色。

图3.3  右单旋 + 变色 示意图

•  情况2.2：节点cur为p的右子节点，p为g的右子节点 -- 左单旋 + 变色

先对g节点进行左单旋操作，然后将p节点变为黑色，g节点变为红色。

图3.4 左单旋 + 变色 示意图 

•  情况2.3：节点cur为p的右子节点，p为g的左子节点 -- 左右双旋 + 变色

先对p节点进行左单旋，然后对g节点进行右单旋，最后将cur节点变为黑色，将g节点变为红色。

图3.5  左右双旋 + 变色 示意图

•  情况2.4：节点cur为p的左子节点，节点p为g的右子节点 -- 右左双旋 + 变色

先对p节点进行右单旋，然后对g节点进行左单旋，最后将cur节点变为黑色，将g节点变为红色。 

图3.6  右左双旋 + 变色 示意图

3.3 红黑树节点插入完整版代码

	bool insert(const std::pair<K, V>& kv){//插入第一个节点if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;   //根节点为黑色return true;}//寻找节点插入的位置Node* parent = nullptr;   Node* cur = _root;while (cur){//如果cur节点的key值大于插入键值对的key，向左子树查找if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if(cur->_kv.first < kv.first)  //如果cur节点的key值小于插入键值对的key，向左子树查找{parent = cur;cur = cur->_right;}else  //相等表明节点已存在，插入失败{return false;}}//判断新节点是parent的左节点还是右节点，链接//默认新插入的节点为红色cur = new Node(kv);cur->_col = RED;cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//如果parent节点不为空且为红色，那么红黑树的结构在插入节点后被破坏，需要调整while (parent && parent->_col == RED){Node* grandParent = parent->_parent;   //祖父节点assert(grandParent);assert(grandParent->_col == BLACK);   //断言检查，如果祖父节点为空或为黑色，那么红黑树结构在节点插入之前就存在问题if (parent == grandParent->_left)  //插入在祖父节点的左子树{Node* uncle = grandParent->_right;//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}	else  //情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑{if (parent->_left == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//    g//  p   u//cRotateR(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行左右双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g//  p   u//   u RotateLR(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}else  //parent == grandParent->_right{Node* uncle = grandParent->_left;  //叔叔节点//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}else{//情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑if (parent->_right == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//   g// u   p//       cRotateL(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行右左双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g// u     p//     cRotateRL(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}}_root->_col = BLACK;   //根节点为黑色return true;}void RotateR(Node* parent)   //右单旋函数{Node* pNode = parent->_parent;    Node* pL = parent->_left;   //左子节点Node* pLR = pL->_right;   //左子节点的右子节点//将pLR节点托管给parent节点的左子节点parent->_left = pLR;if (pLR != nullptr){pLR->_parent = parent;}//将父亲节点托管给pL节点的右子节点pL->_right = parent;  parent->_parent = pL;//此时这颗进行旋转的子树的根节点变为了pL，pL要与pNode节点连接if (parent == _root){_root = pL;pL->_parent = nullptr;}else{pL->_parent = pNode;if (pNode->_left == parent){pNode->_left = pL;}else{pNode->_right = pL;}}}void RotateL(Node* parent)   //左单旋函数{Node* pNode = parent->_parent;Node* pR = parent->_right;    //右子节点Node* pRL = pR->_left;   //右子节点的左子节点//将pLR节点托管给parent节点的右子节点parent->_right = pRL;if (pRL != nullptr){pRL->_parent = parent;}//将parent节点托管给pR的左子节点pR->_left = parent;parent->_parent = pR;if (_root == parent){_root = pR;_root->_parent = nullptr;}else{pR->_parent = pNode;if (pNode->_left == parent){pNode->_left = pR;}else{pNode->_right = pR;}}}void RotateLR(Node* parent)  //左右双旋函数{RotateL(parent->_left);RotateR(parent);}void RotateRL(Node* parent)  //右左双旋函数{RotateR(parent->_right);RotateL(parent);}

四. 红黑树的结构检查

4.1 检查是否为搜索树

采用中序遍历，得到一串递增的数据即可证明为搜索树。

代码4.1：（中序遍历）

	//中序遍历函数void InOrder(){_InOrder(_root);std::cout << std::endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << " ";_InOrder(root->_right);}

4.2 检查节点颜色是否满足要求

需要进行以下两个方面的检查：

• 检查每条路径上的黑色节点数量是否相同。
• 检查是否不存在连续的红色节点。

检查每条路径上的黑色节点数目时，可以选取其中一条路径作为基准（一般为最左侧路径或最右侧路径），通过函数遍历每条路径，获取每条路径上的黑色节点数目，与基准路径的黑色节点数目进行比较，如果不相同，则不满足红黑树结构要求。

图4.1 基准路径的选择

红黑树要求红色节点的左右孩子节点必须为黑色，但是对孩子节点颜色进行检查较为繁琐，因此，当遇到红色节点时，检查其父亲节点是否为空或者为黑色即可，如果红色节点的父亲节点依旧为红色，则表明树中存在连续的红色节点，不满足红黑树结构要求。

代码4.2：（节点颜色检查）

	//红黑树检验函数bool IsRBTree(){//空树是合法的红黑树if (_root == nullptr){return true;}//检查根节点颜色if (_root->_col == RED){std::cout << "根节点颜色不是黑色" << std::endl;}int baseBlackNum = 0;   //基准黑色节点个数//以最左侧路径为基准，计算黑色节点个数，每条路径黑色节点数目都应该相同Node* cur = _root;while (cur){if (cur->_col == BLACK){++baseBlackNum;}cur = cur->_left;}bool blackNumTrue = PrevCheck(_root, 0, baseBlackNum);   //检查每条路径黑色节点数目是否相同bool colorTrue = CheckColor(_root);  //检查是否存在连续红色节点return blackNumTrue && colorTrue;}bool CheckColor(Node* root){if (root == nullptr){return true;}//如果本节点为红色且父亲节点也为红色，证明存在连续红色节点，结构错误if (root->_col == RED && root->_parent && root->_parent->_col == RED){std::cout << "存在连续的红色节点" << std::endl;return false;}return CheckColor(root->_left) && CheckColor(root->_right);}bool PrevCheck(Node* root, int blackNum, int baseBlackNum){if (root == nullptr){if (blackNum != baseBlackNum){std::cout << "每条路径上黑色节点的数目不同" << std::endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}return PrevCheck(root->_left, blackNum, baseBlackNum)&& PrevCheck(root->_right, blackNum, baseBlackNum);}

附录：红黑树完整版代码

//枚举常量 -- 红色、黑色
enum Color
{RED,BLACK
};//定义红黑树节点
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;std::pair<K, V> _kv;   //每个节点存储的键值对Color _col;   //节点颜色RBTreeNode(const std::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:bool insert(const std::pair<K, V>& kv){//插入第一个节点if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;   //根节点为黑色return true;}//寻找节点插入的位置Node* parent = nullptr;   Node* cur = _root;while (cur){//如果cur节点的key值大于插入键值对的key，向左子树查找if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if(cur->_kv.first < kv.first)  //如果cur节点的key值小于插入键值对的key，向左子树查找{parent = cur;cur = cur->_right;}else  //相等表明节点已存在，插入失败{return false;}}//判断新节点是parent的左节点还是右节点，链接//默认新插入的节点为红色cur = new Node(kv);cur->_col = RED;cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//如果parent节点不为空且为红色，那么红黑树的结构在插入节点后被破坏，需要调整while (parent && parent->_col == RED){Node* grandParent = parent->_parent;   //祖父节点assert(grandParent);assert(grandParent->_col == BLACK);   //断言检查，如果祖父节点为空或为黑色，那么红黑树结构在节点插入之前就存在问题if (parent == grandParent->_left)  //插入在祖父节点的左子树{Node* uncle = grandParent->_right;//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}	else  //情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑{if (parent->_left == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//    g//  p   u//cRotateR(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行左右双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g//  p   u//   u RotateLR(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}else  //parent == grandParent->_right{Node* uncle = grandParent->_left;  //叔叔节点//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}else{//情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑if (parent->_right == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//   g// u   p//       cRotateL(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行右左双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g// u     p//     cRotateRL(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}}_root->_col = BLACK;   //根节点为黑色return true;}//中序遍历函数void InOrder(){_InOrder(_root);std::cout << std::endl;}//红黑树检验函数bool IsRBTree(){//空树是合法的红黑树if (_root == nullptr){return true;}//检查根节点颜色if (_root->_col == RED){std::cout << "根节点颜色不是黑色" << std::endl;}int baseBlackNum = 0;   //基准黑色节点个数//以最左侧路径为基准，计算黑色节点个数，每条路径黑色节点数目都应该相同Node* cur = _root;while (cur){if (cur->_col == BLACK){++baseBlackNum;}cur = cur->_left;}bool blackNumTrue = PrevCheck(_root, 0, baseBlackNum);   //检查每条路径黑色节点数目是否相同bool colorTrue = CheckColor(_root);  //检查是否存在连续红色节点return blackNumTrue && colorTrue;}private:bool CheckColor(Node* root){if (root == nullptr){return true;}//如果本节点为红色且父亲节点也为红色，证明存在连续红色节点，结构错误if (root->_col == RED && root->_parent && root->_parent->_col == RED){std::cout << "存在连续的红色节点" << std::endl;return false;}return CheckColor(root->_left) && CheckColor(root->_right);}bool PrevCheck(Node* root, int blackNum, int baseBlackNum){if (root == nullptr){if (blackNum != baseBlackNum){std::cout << "每条路径上黑色节点的数目不同" << std::endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}return PrevCheck(root->_left, blackNum, baseBlackNum)&& PrevCheck(root->_right, blackNum, baseBlackNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << " ";_InOrder(root->_right);}void RotateR(Node* parent)   //右单旋函数{Node* pNode = parent->_parent;    Node* pL = parent->_left;   //左子节点Node* pLR = pL->_right;   //左子节点的右子节点//将pLR节点托管给parent节点的左子节点parent->_left = pLR;if (pLR != nullptr){pLR->_parent = parent;}//将父亲节点托管给pL节点的右子节点pL->_right = parent;  parent->_parent = pL;//此时这颗进行旋转的子树的根节点变为了pL，pL要与pNode节点连接if (parent == _root){_root = pL;pL->_parent = nullptr;}else{pL->_parent = pNode;if (pNode->_left == parent){pNode->_left = pL;}else{pNode->_right = pL;}}}void RotateL(Node* parent)   //左单旋函数{Node* pNode = parent->_parent;Node* pR = parent->_right;    //右子节点Node* pRL = pR->_left;   //右子节点的左子节点//将pLR节点托管给parent节点的右子节点parent->_right = pRL;if (pRL != nullptr){pRL->_parent = parent;}//将parent节点托管给pR的左子节点pR->_left = parent;parent->_parent = pR;if (_root == parent){_root = pR;_root->_parent = nullptr;}else{pR->_parent = pNode;if (pNode->_left == parent){pNode->_left = pR;}else{pNode->_right = pR;}}}void RotateLR(Node* parent)  //左右双旋函数{RotateL(parent->_left);RotateR(parent);}void RotateRL(Node* parent)  //右左双旋函数{RotateR(parent->_right);RotateL(parent);}private:Node* _root = nullptr;
};