红黑树的理解与实现（详解）

相关的数据结构：

搜索二叉树-CSDN博客

AVL树的创建与检测-CSDN博客

个人主页：敲上瘾-CSDN博客

个人专栏：游戏、数据结构、c语言基础、c++学习、算法

目录

一、红黑树规则：

二、红黑树的插入

1.变色

2.单旋+变色

3.双旋+变色

三、红黑树的验证

四、源码：

---

一、红黑树规则：

红黑树规则（重点！）：

• 每个结点不是红⾊就是⿊⾊。
• 根结点是⿊⾊的。
• 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点。
• 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点。
   

        红黑树的性质都由以上4点规则决定的，其中的一个性质：红黑树最长路径的节点数量一定不会大于最短路径的两倍。这使得红黑树虽然不是完全平衡但高度差没有那么大，查找效率依旧是longN级别的。

        红黑树为什么能实现最长路径不会超过最短路径的两倍呢？我们可以想一想如果其中任意一条路径有n个黑节点，最短路径的颜色是如何分布，最长路径颜色又是如何分布的呢？其实很简单根据第4条规则我们可以最短的路径的节点不可能低于n个，（即最少的时候为n个黑节点）。又由第3条规则可以知道最长的路径的节点数不可能超过2n个，（即最多的时候为n个黑节点，n个红节点）。

        所以我们要实现一个红黑树只需要维护以上4条规则即可。

二、红黑树的插入

        因为红黑树也是一棵二叉搜索树，所以我们先按二叉搜索树的逻辑将节点进行插入，需要注意插入的是红色节点，因为黑色节点维护起来非常的困难。

（1）如果该新节点的父亲为黑节点，不用再做调整，直接返回。

（2）如果不是则需要分情况进行更新：

        在这里我们是因为父亲为红节点才进行更新的，因为在插入之前已经保证这是一棵红黑树，又因为父亲为红色，所以爷爷一定为黑色。

        而我们要做的就是把新节点的父亲更新成黑色，如何更新如何分情况呢关键就在于叔叔是否存在以及叔叔的颜色。接下来就以父亲为爷爷的左孩子为例进行讲解，父亲为爷爷的右孩子同理。

说明：下图中假设我们把新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为
g(grandfather)，p的兄弟标识为u（uncle）。

1.变色

 叔叔u存在且为红：

        该情况比较简单，因为要保持每条路径的黑节点的个数相同，所以直接将g的黑色分配给p和u，而g变为红色即可。如上图：

        但是有个问题g的父亲是完全有可能是红节点的，照这样的话又出现了两个连续的红色节点，所以再以g作为新的c节点，g的父亲作为新的p节点，然后更新g，最后循环进行调整就可以解决。

如下x是通过变色更新上来的节点：

2.单旋+变色

 叔叔u不存在或为黑：

        当叔叔u不存在或为黑，我们发现无论如何变色都是无法调整得当的，所以这就需要旋转+变色操作了。

该情况又可以细分为两种情况：

• c和p在g的同一侧，需要单旋+变色
• c和p在g的不同侧，需要双旋+变色

首先来分析第一种情况：

如下：以g为旋转点进行右旋，然后将p更新为黑色，c和g为红色。

关于旋转请参考：AVL树的创建与检测-CSDN博客 

3.双旋+变色

 叔叔u不存在或为黑并且c和p在g的不同侧我们进行双旋+变色，如下：

注意：因为考虑要使根节点为黑色，防止在调整过程将根节点改为黑色，所以在每次调整过后直接将根节点更新为黑色。

三、红黑树的验证

        红黑树的验证并不用去验证高度差，也不用去验证最长路径的节点数是不是小于最短路径的两倍，因为即使这一些条件都满足也不一定是红黑树，想要验证红黑树只需要验证是否满足红黑树的规则即可，只要满足了那些规则，那么红黑树的性质自然就有了。

• 规则1就不用验证因为这是必然的
• 规则2也是比较简单一个if语句就解决。
• 规则3的验证：遍历整棵树，当遍历到红色节点时判断它的父亲是否为黑色，不是则违反规则。
• 规则4的验证：任意选择一条路径（如一直往左走）并记录其中的黑节点数目（记为count），然后遍历整棵树的所有路径并记录黑节点数目，然后在路径结束后与count比较，如果不相等则违反规则。

四、源码：

#pragma once
#include<iostream>
using namespace std;
enum Color{red, black};
template<class T>
struct RBNode
{RBNode(T key):data(key),color(red),left(nullptr),right(nullptr),prev(nullptr){}T data;enum Color color;RBNode<T>* left;RBNode<T>* right;RBNode<T>* prev;
};
template<class T>
class RBTree
{
public:typedef RBNode<T> Node;RBTree():root(nullptr){}bool insert(T data){Node* newNode = new Node(data);if (root == nullptr){root = newNode;root->color = black;return true;}Node* cur = root;Node* parent = root;while (cur){parent = cur;if (newNode->data.first <= cur->data.first)cur = cur->left;else cur = cur->right;}if (newNode->data.first <= parent->data.first)parent->left = newNode;else parent->right = newNode;newNode->prev = parent;//需要调整cur = newNode;Node* grandfather = parent->prev;Node* uncle = nullptr;while (parent&&parent->color == red){grandfather = parent->prev;if (parent == grandfather->left){uncle = grandfather->right;if (uncle && uncle->color == red){grandfather->color = red;parent->color = uncle->color = black;cur = grandfather;parent = cur->prev;}else{if (cur == parent->left){ReverseR(grandfather);parent->color = black;grandfather->color = red;}else{ReverseL(parent);ReverseR(grandfather);cur->color = black;parent->color = grandfather->color = red;}}}else{uncle = grandfather->left;if (uncle && uncle->color == red){grandfather->color = red;parent->color = uncle->color = black;cur = grandfather;parent = cur->prev;}else{if (cur == parent->right){ReverseL(grandfather);parent->color = black;grandfather->color = red;}else{ReverseR(parent);ReverseL(grandfather);cur->color = black;parent->color = grandfather->color = red;}}}}root->color = black;return true;}void ReverseR(Node* parent){Node* subL = parent->left;Node* subLR = subL->right;parent->left=subLR;subL->right = parent;//Node* pparent = parent->prev;subL->prev = pparent;if (pparent == nullptr) root = subL;else{if (pparent->left == parent) pparent->left = subL;else pparent->right = subL;}if (subLR) subLR->prev = parent;parent->prev = subL;}void ReverseL(Node* parent){Node* subR = parent->right;Node* subRL = subR->left;parent->right = subRL;subR->left = parent;//Node* pparent = parent->prev;subR->prev = pparent;if (pparent == nullptr) root = subR;else{if (pparent->left == parent) pparent->left = subR;else pparent->right = subR;}if (subRL) subRL->prev = parent;parent->prev = subR;}bool IsBalanceTree(){if (root == nullptr) return true;if (root->color == red) return false;int count = 0;Node* cur = root;while (cur){if (cur->color == black) count++;cur = cur->left;}return Check(root, 0, count);}bool Check(Node* root,int path,const int refNum){if (root == nullptr) return path == refNum;if (root->color == red && root->prev->color == red) return false;if (root->color == black) path++;return Check(root->left, path, refNum) && Check(root->right, path, refNum);}
private:Node* root;
};