c++ 红黑树（带头结点）
想必在看到这篇文章的时候，你一定是带着问题去搜索的，一定是对红黑树已经有了初步大致的认识，已经知道了红黑树的性质与普通红黑树的功能与如何代码实现，但是莫一天突然看到了带头结点的红黑树，肯定是对此有一些疑惑的，或者来说在代码的实现上自己存在着某些疑惑。那么话不多说，就先给出红黑树（带头结点）的完整实现代码。然后再给出相应的详细解释。
代码的实现
#include<iostream>
#include<vector>
using namespace std;
enum Colour
{
RED,
BLACK,
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _pLeft;
RBTreeNode<T>* _pRight;
RBTreeNode<T>* _pParent;
T _data;
Colour _col;
RBTreeNode(const T& data = T(), Colour col = RED)
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _col(col)
{}
};
// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点
template<class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
RBTree()
{
_pHead = new Node;
_pHead->_pLeft = _pHead;
_pHead->_pRight = _pHead;
}
// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
// 注意：为了简单起见，本次实现红黑树不存储重复性元素
bool Insert(const T& data)
{
Node*& pRoot = GetRoot();
// 第一次插入结点
if (pRoot == nullptr)
{
pRoot = new Node(data, BLACK);
//
pRoot->_pParent = _pHead;
return true;
}
// 找待插入节点在二叉搜索树中的位置
// 并保存其双亲节点
else
{
Node* pCur = pRoot;
Node* pParent = nullptr;
while (pCur)
{
pParent = pCur;
if (data < pCur->_data)
pCur = pCur->_pLeft;
else if (data > pCur->_data)
pCur = pCur->_pRight;
else
return false;
}
// 插入新节点
pCur = new Node(data);
if (data < pParent->_data)
pParent->_pLeft = pCur;
else
pParent->_pRight = pCur;
pCur->_pParent = pParent;
//调整
// l pCur新节点默认颜色 : 红色
// 如果pParent的颜色是黑色的，满足红黑树性质
// 如果pParent的颜色是红色的，违反了性质三--不能有连在一起的
// ...
while (pParent != _pHead && pParent->_col == RED)//大前提
{
Node* grandfather = pParent->_pParent;
//parent在左
if (pParent == grandfather->_pLeft)
{
Node* uncle = grandfather->_pRight;
//Node* uncle = pParent->_pRight;//错误二
if (uncle && uncle->_col == RED)
{
//情景一：pCur->红，pParent->红，grandfather->黑，uncle存在且为红
// g
// p u
// c
//
//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
pParent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//
pCur = grandfather;
if (pCur == pRoot)
{
pCur->_pParent = _pHead;
}
pParent = pCur->_pParent;
}
else
{
if (pCur == pParent->_pLeft)
{
//情景二：pCur->红，pParent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
//
// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
RotateR(grandfather);
pParent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情景三：pCur->红，pParent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
// 解决：对p左单旋，后变为情景二。
RotateL(pParent);
RotateR(grandfather);
pCur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//情景大概反着来
{
//1 uncle
Node* uncle = grandfather->_pLeft;//错误一
//Node* uncle = pParent->_pRight;//错误一
if (uncle && uncle->_col == RED)
{
pParent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
pCur = grandfather;
/
if (pCur == pRoot)
{
pCur->_pParent = _pHead;
}
pParent = pCur->_pParent;
}
else
{
if (pCur == pParent->_pRight)//2
{
RotateL(grandfather);
pParent->_col = BLACK;
grandfather->_col = RED;
}
else//3
{
RotateR(pParent);
RotateL(grandfather);
pCur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
Node*& _root = GetRoot();
//最后
_root->_col = BLACK;
return true;
}
}
// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
Node* Find(const T& data)
{
Node* pCur = GetRoot();
while (pCur)
{
if (pCur->_data == data)
break;
else if (pCur->_data > data)
pCur = pCur->_pLeft;
else
pCur = pCur->_pRight;
}
return pCur;
}
// 获取红黑树最左侧节点
Node* LeftMost()
{
Node* pCur = GetRoot();
if (nullptr == pCur)
return _pHead;
while (pCur->_pLeft)
{
pCur = pCur->_pLeft;
}
return pCur;
}
// 获取红黑树最右侧节点
Node* RightMost()
{
Node* pCur = GetRoot();
if (nullptr == pCur)
return _pHead;
while (pCur->_pRight)
{
pCur = pCur->_pRight;
}
return pCur;
}
// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()
{
//1:是否存在 红-红
//每条路径黑色结点是否相同个数
//最长的不超过最短的二倍
//根，叶子为黑
Node* _root = GetRoot();
if (nullptr == _root)
return true;
if (_root->_col == RED)
return false;
Node* pCur = _root;
size_t refVal = 0;
while (pCur)
{
if (pCur->_col == BLACK)
refVal++;
pCur = pCur->_pLeft;
}
size_t blacknum = 0;
return _IsValidRBTRee(_root, blacknum, refVal);
}
private:
bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
{
if (pRoot == nullptr)
{
if (pathBlack != blackCount)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
Node* pParent = pRoot->_pParent;
if (pRoot->_col == RED)
{
if (pParent != _pHead && pRoot->_pParent->_col == RED)
{
cout << "有连续的红色节点" << endl;
return false;
}
}
if (pRoot->_col == BLACK)
{
++blackCount;
}
return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack)
&& _IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);
}
// 左单旋
void RotateL(Node* pParent)
{
Node*& _root = GetRoot();
Node* subR = pParent->_pRight;
Node* subRL = subR->_pLeft;
pParent->_pRight = subRL;
subR->_pLeft = pParent;
Node* parentParent = pParent->_pParent;
pParent->_pParent = subR;
if (subRL)
subRL->_pParent = pParent;
if (_root == pParent)
{
_root = subR;
subR->_pParent = nullptr;
}
else
{
if (parentParent->_pLeft == pParent)
{
parentParent->_pLeft = subR;
}
else
{
parentParent->_pRight = subR;
}
subR->_pParent = parentParent;
}
}
// 右单旋
void RotateR(Node* pParent)
{
Node*& _root = GetRoot();
Node* subL = pParent->_pLeft;
Node* subLR = subL->_pRight;
pParent->_pLeft = subLR;
if (subLR)
subLR->_pParent = pParent;
Node* parentParent = pParent->_pParent;
subL->_pRight = pParent;
pParent->_pParent = subL;
if (_root == pParent)
{
_root = subL;
subL->_pParent = nullptr;
}
else
{
if (parentParent->_pLeft == pParent)
{
parentParent->_pLeft = subL;
}
else
{
parentParent->_pRight = subL;
}
subL->_pParent = parentParent;
}
}
// 为了操作树简单起见：获取根节点
Node*& GetRoot()
{
return _pHead->_pParent;
}
private:
Node* _pHead;
};
对应的代码解释与红黑树（带头结点）的讲解
带头结点红黑树中头节点设计的解释
首先需要解释一点：本红黑树类内部只有一个私有成员：头节点。
我们知道set与map的底层就为红黑树，其就是由红黑树经过封装后得到的，那么封装这个过程其实存在着很多的细节，这些细节既复杂又多，这就使得如果直接进行封装步骤就很麻烦，那么对于此就出现了为了后序封装set与map，就出现了带头结点的红黑树。
对于带头结点的红黑树，如果对于此一点也不了解，那么其实对于一个刚学完红黑树的会存在很多的疑惑，就比如说带哨兵位的链表中，头节点是一个真是存在的一个结点，其与正常结点的区别就是其里面存储的信息是0或者空，其指针的设计与普通结点无异。如果还按照这样设计，那么红黑树的头节点也应该如此，那么这就会引出疑问
- 头节点的颜色如何设计？
- 头节点的三叉链如何设计？
- 头节点与根结点的具体关系如何设计？
问题1
第一个问题的答案无非是红或者黑，如果我们设计为红色，那么他要符合其中一个性质：其两个孩子全为黑色，这又怎么设计呢？因为头节点他仅有一个孩子，根节点。那么对此也只有可能设计为黑色。
问题2
对于头结点的三叉链怎么设计，我们要保证其三个指针全都设计合理，那么对此搜集了一些材料，得知其左指针与右指针全都指向自己。
其此设计的原因如下：
-
简化边界条件：在进行插入、删除等操作时，通常需要处理树的边界情况。通过让头节点的左右指针指向自己，可以避免处理空树的特殊情况，使得算法更加统一和简洁。
-
统一处理：在遍历树或查找节点时，头节点作为一个特殊的节点，可以统一处理所有节点的情况。无论是从头节点开始还是从其他节点开始，操作逻辑都可以保持一致。
-
避免空指针：如果头节点的左右指针指向空（NULL），在某些操作中可能会导致空指针异常。通过指向自己，可以确保在任何情况下都有一个有效的指针，减少了出错的可能性。
-
便于实现：在实现红黑树的各种操作时，特别是旋转和调整颜色等操作，使用头节点指向自己可以减少代码中的条件判断，使得实现更加简洁。
总之，这种设计使得红黑树的实现更加高效和易于维护。
那么对应的父亲结点也只能指向其根结点了。
代码实现的部分解释
其本代码实现的思路完全与不带头结点的红黑树的整体思路是完全一致的，跟上篇文章一样，插入总体分为两大类，第二类又分为四小情况。
针对于第一次插入，我们再进行第一次插入时，此时为特殊情况，我们要获取头节点的父亲指针指向的空间是否为空为标准进行判断是否为第一次插入，那么对于此，就要特殊设计一个函数GetRoot();
Node*& GetRoot()
{
return _pHead->_pParent;
}其余代码实现起来没什么难度，这里就不多说了，有疑惑的看上面的代码。
其余插入代码跟红黑树（普通）插入无疑，思路理清楚，整体实现起来还是不难的，我自己在写本代码的时候，就是先粘贴以前的注释，然后再一点一点写，不会的再去翻一翻以前的代码实现起来用了一个多小时。
代码注意事项
在写完代码的时候，在第一次测试的时候就遇到了指向空的报错，然后经过代码长达半个小时的调试与各处调整小细节，才调好了第一次解决了指向空的报错。
问题如下：
问题一
在此我们要写pParent != _pHead；
而不是写pParent这是因为根节点的pParent是空，如果还这样代码走下去，那么导致后面
这是因为我们没有把头节点当作头节点，而是把他当作根结点一样处理了，这肯定会导致错误。
问题二
这个问题结果过后，在代码看起来运行起来没有问题，但是对红黑树进行检测，还是存在着问题，他会报错
这个问题如果经过详细的一步一步进行代码调试也是可以发现的，就是没有添加如下代码部分，
这里的pRoot为：
其实就是如果跟换根节点要同时更换头节点的_pParent指针的指向。使其指向新的根节点。
我写这部分代码的时候遇见的就是这两个大问题，一些小问题就是一些代码拼写错误，还有一些书写问题，与旋转过后颜色调整错误，这些都是些小问题，经过简单调试就可以完成不用调试那么仔细。