C++中红黑树实现详解
**
因为本人之前一直写的是电子笔记，对自己学会的东西作一个总结，所以基本都是文字，本来想全发成博客的形式，发现全发成博客比较花费时间，而且一直发博客质量不是很好，而且通过发博客学到的东西也会变少，所以准备先把笔记发出来，后续再将它们改成博客的形式，争取2天至少改一篇博客，觉得我总结的还行的可以先关注我，后续会发成博客形式，内容也会更加完善 **
红黑树有五条规定，但最重要的只有三条：
1.根节点必须是黑色
2.黑节点可以接红节点也可以接黑节点，但红节点必须接黑节点
3.在红黑树中，每条路径都要包含相同数目的黑色节点
其实红黑树的这些性质都是在保证，任何一条路径都不能是最短路径的两倍还要多，因为红色只能连黑色，而每条路径上的黑色节点是相同的个数，所以就算每个黑节点下连红色的节点，也最多是两倍，保证它的原因是，为了让这个二叉搜索树平衡，不会造成单链情况，同时又要比AVL树简单，然后根节点必须为黑色的原因是这样的红黑树比节点是红色的红黑树要简单
再构建红黑树时我们一般默认连的是红节点，因为连红节点简单，连完以后就不用管了（大不遇到调整的情况下）而直接连黑色的话的，就破坏了平衡，每一条路径都要再加一个黑色的节点，这样很恶心
因为我们一般连的都是红节点，那么就可能遇到两个红节点在一起的情况，让样就不满足规则了，所以要调整，但是怎么调整，就要看叔叔节点了，（因为现个红色节点要连在一起，它的上层节点一定是黑的，所以这里暂时将那个黑节点叫做祖父节点，它的左孩子叫父亲节点，它的右孩子叫叔叔节点）
文章图片
如果叔叔节点也是红色的那就好办了，我们的原则是对刚插入的节点为红色，不进行变色，因为这样太麻烦，所以调整父亲，叔叔，祖父，因为父亲和叔叔都是红色的，而祖父只有它们两个节点，所以它的路径只有这两个，它上面的黑色节点数，是不会变的，所以将祖父变成红色，那么其它两个路径都要增加一个黑色节点，这时刚好父亲，和叔叔都是红的，所以直接变为黑色就好了，因为它俩相当于平行的两个节点，是同一级别的，所以不会产生问题，这时叶了节点的父亲节点是黑色，满足要求
但是当叔叔节点是黑色或不存在时，情况就又发生了变化
文章图片
这 时就不能只单纯的通过调色来解决问题，因为叔叔节点本来就是黑色，如果把父亲节点调黑，祖父节点调红那就相当于给右边多加了一个黑节点，是不行的，所以这时就要旋转了，旋转的方法和之前的AVL树的旋转方法一样，原因是既然必需要进行调整，还不能破坏结构，用之前的方法不仅可以降低高度而且还能使黑节点得到平衡，一箭双雕
在进行右旋转后父亲节点变成了祖父节点，是红色而祖父节点带领着叔叔节点变成了父亲节点的右孩子，父亲节点的右孩子变成了祖父节点的左孩子，但是这样显然不满足我们红黑树的性质，所以要进行变色，变色的原理是原来受祖父节点影响的现在都要进行改变，因为父亲节点现在是祖父节点，所以在它的左孩子上必须有一个黑节点，而且因为它的左孩子是红色的，所以父亲节点必须进行变色为黑色，满足左孩子的需要，因为它原来的右孩子变成了祖父节点的左孩子，但是祖父节点现在还是黑色的，因为右孩子原来上边只有一个祖父节点是黑的，现在多了一个父亲节点也黑的所以它的上面多了黑节点，又因为祖父节点的左孩子原来上边也只有一个黑 节点是祖父节点 ，现在又多了一个黑结点，所以父亲节点和祖父节点，这两个节点不能连在一起，所以要进行变色，但是因为父亲节点的左孩子要求它必须是黑的，所以只有将祖父节点变为红色，才能满足要求，这是一个从下往上找关系的一种变色方式，这就是左左情况下的 旋转
然后就是右右的情况和它差不多，要进行左旋，完成旋转后，将父亲节点改为黑色，祖父结点改为红色就好了
【C++中红黑树实现详解】接下来是进行两次旋转的情况：
出现这种情况，和AVL树的处理情况一样，只需要进行相应的左旋右旋就行了，但是变色就有所不同了，就右左的情况为例：
这是最下层是左边高所以要进行右旋，但是因为这里不用像AVL树一样考虑平衡因子，所以简单了很多，因为发生右左这种情况，一定是最下层的两个节点为红色，所以进行右旋时，只是将原来的右左情况变为了右右的情况，又因为它俩都是红的进行旋转后只是将它俩的上下级关系换了一下，不会影响黑节点，所以就可以像刚才那种右右的情况进行旋转和变色，这时调色时记得调的刚插入进来的节点，因为它经过第一次旋转变为了父亲节点
左右的情况和它一样变化成左左的情况就行了
文章图片
#include
#include
using namespace std;
enum Color
{ BLACK,
RED
};
template
struct RBTNode
{ typedef RBTNode Node;
Node* _pLeft = nullptr;
Node* _pRight = nullptr;
Node* _pParent = nullptr;
pair _kv;
Color _color = RED;
};
template
class RBTree
{public:
typedef RBTNode Node;
typedef Node* pNode;
typedef Node* PNode;
RBTree()
{_header = new Node;
_header->_pParent = nullptr;
_header->_pLeft = _header;
_header->_pRight = _header;
} bool Insert(const pair& kv)
{if (_header->_pParent == nullptr)
{pNode root = new Node;
root->_kv = kv;
root->_color = BLACK;
root->_pParent = _header;
_header->_pParent = root;
_header->_pLeft = root;
_header->_pRight = root;
return true;
}
pNode cur = _header->_pParent;
pNode parent = nullptr;
while (cur)
{if (kv.first > cur->_kv.first)
{parent = cur;
cur = cur->_pRight;
}
else if (kv.first < cur->_kv.first)
{parent = cur;
cur = cur->_pLeft;
}
else
{return false;
}
}pNode newNode = new Node;
newNode->_kv = kv;
if (kv.first > parent->_kv.first)
{parent->_pRight = newNode;
}
else
{parent->_pLeft = newNode;
}
newNode->_pParent = parent;
cur = newNode;
//调平衡
while (cur != _header->_pParent && cur->_pParent->_color == RED)
{pNode parent = cur->_pParent;
pNode gParent = parent->_pParent;
if (gParent->_pLeft == parent)
{pNode uncle = gParent->_pRight;
if (uncle && uncle->_color == RED)
{parent->_color = uncle->_color = BLACK;
gParent->_color = RED;
cur = gParent;
}
else
{if (cur == parent->_pRight)
{RotateL(parent);
swap(parent, cur);
}
RotateR(gParent);
parent->_color = BLACK;
gParent->_color = RED;
break;
}
}
else
{if (gParent->_pRight == parent)
{pNode uncle = gParent->_pLeft;
if (uncle && uncle->_color == RED)
{parent->_color = uncle->_color = BLACK;
gParent->_color = RED;
cur = gParent;
}
else
{if (cur == parent->_pLeft)
{RotateR(parent);
swap(parent, cur);
}
RotateL(gParent);
parent->_color = BLACK;
gParent->_color = RED;
break;
}
}}
}
_header->_pParent->_color = BLACK;
_header->_pLeft = leftMost();
_header->_pRight = rightMost();
return true;
} void RotateR(Node* parent)
{Node* subL = parent->_pLeft;
Node* subLR = subL->_pRight;
//单向连接subL,parent,subLR
subL->_pRight = parent;
parent->_pLeft = subLR;
//向上连接subLR
if (subLR)
{subLR->_pParent = parent;
}
//subL, parent->parent双向连接
if (parent != _header->_pParent)
{Node* gParent = parent->_pParent;
if (gParent->_pLeft == parent)
{gParent->_pLeft = subL;
}
else
{gParent->_pRight = subL;
}
subL->_pParent = gParent;
}
else
{subL->_pParent = _header;
_header->_pParent = subL;
}
//向上连接parent,subL
parent->_pParent = subL;
} void RotateL(Node* parent)
{Node* subR = parent->_pRight;
Node* subRL = subR->_pLeft;
subR->_pLeft = parent;
parent->_pRight = subRL;
if (subRL)
{subRL->_pParent = parent;
}
if (parent != _header->_pParent)
{Node* gParent = parent->_pParent;
if (gParent->_pLeft == parent)
{gParent->_pLeft = subR;
}
else
{gParent->_pRight = subR;
}
subR->_pParent = gParent;
}
else
{subR->_pParent = _header;
_header->_pParent = subR;
}
parent->_pParent = subR;
}
pNode leftMost()
{pNode cur = _header->_pParent;
while (cur && cur->_pLeft)
{cur = cur->_pLeft;
}
return cur;
}
pNode rightMost()
{pNode cur = _header->_pParent;
while (cur && cur->_pRight)
{cur = cur->_pRight;
}
return cur;
} void _Inorder(pNode root)
{if (root)
{_Inorder(root->_pLeft);
cout << root->_kv.first << "-->" << root->_kv.second << endl;
_Inorder(root->_pRight);
}
}
void Inorder()
{_Inorder(_header->_pParent);
return;
}
bool IsValidRBTree()//判断红黑树是否正确
{PNode pRoot = _header->_pParent;
// 空树也是红黑树
if (nullptr == pRoot)
return true;
// 检测根节点是否满足情况
if (BLACK != pRoot->_color)
{cout << "违反红黑树性质二：根节点必须为黑色" << endl;
return false;
}
// 获取任意一条路径中黑色节点的个数
size_t blackCount = 0;
PNode pCur = pRoot;
while (pCur)
{if (BLACK == pCur->_color)
blackCount++;
pCur = pCur->_pLeft;
}
// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
size_t k = 0;
return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{//走到null之后，判断k和black是否相等
if (nullptr == pRoot)
{if (k != blackCount)
{cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
// 统计黑色节点的个数
if (BLACK == pRoot->_color)
k++;
// 检测当前节点与其双亲是否都为红色
PNode pParent = pRoot->_pParent;
if (pParent && RED == pParent->_color && RED == pRoot->_color)
{cout << "违反性质三：没有连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&
_IsValidRBTree(pRoot->_pRight, k, blackCount);
}
private:
pNode _header;
};
void testRBTree2()
{ srand(time(nullptr));
int n;
cin >> n;
RBTree rb;
while (n--)
{int num = rand();
cout << num << " ";
rb.Insert(make_pair(num, num));
}
cout << "IsValidRBTree: " << rb.IsValidRBTree() << endl;
}void testRBTree()
{ RBTree rbtree;
rbtree.Insert(make_pair(0, 0));
rbtree.Insert(make_pair(10, 0));
rbtree.Insert(make_pair(2, 0));
rbtree.Insert(make_pair(8, 0));
rbtree.Insert(make_pair(9, 0));
rbtree.Insert(make_pair(4, 0));
rbtree.Inorder();
cout << "IsValidRBTree: " << rbtree.IsValidRBTree() << endl;
}int main()
{ testRBTree2();
system("pause");
return 0;
}
推荐阅读
- 他玩王者荣耀都不带我开黑，这种男朋友还值得爱吗
- c/c++|20165223 学习基础和C语言基础调查
- C++操作.json文件的超详细新手教程
- C++基于boost|C++基于boost asio实现sync tcp server通信流程详解
- 入埃及记（第三十日）
- C++中的计时/时间函数
- 黑云摧
- 黑科技|助力想象与创造再无边界，华为平板的“三位一体”只是起点
- 虎子是条狗
- 职场|被裁大厂员工绝处逢生： 人生未必一条路走到黑