【C++】手撕红黑树
相信大家肯定听过在C++大名鼎鼎的两颗树，这两颗树分别是AVL树和红黑树，学过的小伙伴听到都是瑟瑟发抖，像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大，正所谓难度越大动力就越大，那本篇我们学习这两棵树的一颗树--红黑树。⭐主体。
·
> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：能直接手撕红黑树。
> 毒鸡汤：行到水穷处，坐看云起时。。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言
相信大家肯定听过在C++大名鼎鼎的两颗树，这两颗树分别是AVL树和红黑树，学过的小伙伴听到都是瑟瑟发抖，像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大，正所谓难度越大动力就越大，那本篇我们学习这两棵树的一颗树--红黑树。
⭐主体
学习红黑树咱们按照下面的图解：
🌙红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍，因而是接近平衡的。
🌙红黑树的性质
红黑树有以下五点性质：
- 每个结点不是红色就是黑色。
- 根结点是黑色的。
- 如果一个结点是红色的，则它的两个孩子结点是黑色的。
- 对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。
- 每个叶子结点都是黑色的（此处的叶子结点指定是空结点）。
问题探讨：
红黑树如何确保从根到叶子的最长可能路径不会超过最短可能路径的两倍？
问题分析：
红黑树第三条性质说明红黑树不能存在连续（父子相连）的红结点，可以存在连续的黑结点，又由于第四条性质每个路径上的黑结点个数都相同 ，所以对于最短路径来说一定是都是黑色结点，对于最长路径来说一定是黑色红色相间的路径，所以最长路径不超过最短路径长度的二倍
图解分析：
🌙红黑树的结点
三叉链结构，对比AVL数节点的定义，把平衡因子替换成节点颜色，采用枚举的方式：
编写代码：
// 定义红黑树结点
template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left; // 左
RBTreeNode<K, V>* _right; // 右
RBTreeNode<K, V>* _parent; // 父亲
Color _col;
pair<K, V> _kv; //存储的键值对
RBTreeNode(const pair<K,V>& kv) // 初始化列表
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};代码分析：
为什么构造结点时，默认将结点的颜色设置为红色？
- 如果默认颜色为黑，那么在插入中插入一个黑结点一定会让该路径上的黑结点数量加1，从而与其他路径上黑结点数量造成不一致，而一定会影响该棵红黑树
- 如果默认颜色为红，那么在插入中插入一个红结点，可能新插入结点的父结点为黑色结点则没有影响，也可能新插入结点的父结点为红结点，由于不能存在连续的（父子相连的）红色结点，而对该棵树造成影响
- 所以默认为红色比较黑色来说是好的
🌙红黑树的插入
红黑树插入结点的逻辑分为三步：
- 按二叉搜索树的插入方法，找到待插入位置。
- 将待插入结点插入到树中。
- 若插入结点的父结点是红色的，则需要对红黑树进行调整。
红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。
情况一：插入结点的叔叔存在，且叔叔的颜色是红色。（cur为红，p为红，g为黑，u存在且为红）
分析：
- 此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。
- 但调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。
- 但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进而进行不同的调整操作。
图解：
情况二：cur为红，p为红，g为黑，u不存在/u为黑，gpc在同一侧
探讨：
如果u结点不存在，则cur一定是新增结点，因为如果cur不是新增结点：则cur和p一定有一个节点时黑色，就不满足每条路径都有相同的黑色结点的性质。
如果u结点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色，在其子树调整过程中变为了红色
分析：
- 如果p为g的左孩子，cur为p的左孩子，则进行右单旋转
- 如果p为g的右孩子，cur为p的右孩子，则进行左单旋转
①u不存在，cur为新增节点，进行右单旋
图解：
②u结点存在且为黑：
情况二： cur为红，p为红，g为黑，u不存在/u为黑，gpc不在同一侧
分析：
- p为g的左孩子，cur为p的右孩子，对p做左单旋转，
- p为g的右孩子，cur为p的左孩子，对p做右单旋转，
说明：
- 这时候我们就需要进行双旋了
图解：
编写代码：
// 插入结点
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr) // 若红黑树为空叔，则插入结点直接作为根结点
{
_root = new Node(kv);
_root->_col = BLACK; // 根结点必须是黑色
return true; // 插入成功
}
// 1.采用二叉搜索树的方法找插入位置
Node* parent = nullptr;
Node* cur = _root;
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;
}
}
// 2.将待插入结点插入到树中
cur = new Node(kv); // 根据所给值构造一个结点（必须是红色）
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 3.若插入结点的父结点是红色的，则需要对红黑树进行调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent; // parent是红色其父结点一定存在
// parent为父的左孩子
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红色
{
// 颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况二：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)// cur == parent->_left
{
RotateR(grandfather); // 右单旋
// 颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else // cur == parent->_right
{
RotateL(parent); // 左单旋
RotateR(grandfather); // 右单旋
// 颜色调整
cur->_col = BLACK;
grandfather->_col = RED;
}
break; // 子树旋转后，该子树的根变为黑色，无需往上处理
}
}
else // parent是父的右孩子
{
Node* uncle = grandfather->_left;
// 情况一：叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况二：叔叔不存在或者存在且为黑
{
if (cur == parent->_right)
{
// 右左双旋
RotateL(grandfather);
// 颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
// 根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
_root->_col = BLACK;
return true;
}
// 左单旋
void RotateL(Node* parent)
{
++rotateSize;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
// 右单旋
void RotateR(Node* parent)
{
++rotateSize;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}🌙红黑树的查找
红黑树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：
- 若树为空树，则查找失败，返回nullptr。
- 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
- 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
- 若key值等于当前结点的值，则查找成功，返回对应结点。
// 查找元素
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return NULL;
}🌙红黑树的验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质
步骤一代码：
// 中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}步骤二代码：
// 判断是否为红黑树
bool Check(Node* cur, int blackNum, int refBlackNum)
{
if (cur == nullptr)
{
if (refBlackNum != blackNum)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
//cout << blackNum << endl;
return true;
}
if (cur->_col == RED && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "存在连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
++blackNum;
return Check(cur->_left, blackNum, refBlackNum)
&& Check(cur->_right, blackNum, refBlackNum);
}
bool IsBalance()
{
if (_root && _root->_col == RED)
return false;
int refBlackNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
refBlackNum++;
cur = cur->_left;
}
return Check(_root, 0, refBlackNum);
}🌙红黑树与AVL树比较
红黑树与AVL树比较：
-
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )
-
红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数
-
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多
🌙全部代码
#include<iostream>
#include<assert.h>
#include<time.h>
using namespace std;
enum Color // 采用枚举定义颜色
{
RED, // 0 为红色
BLACK, // 1 为黑色
};
// 定义红黑树结点
template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left; // 左
RBTreeNode<K, V>* _right; // 右
RBTreeNode<K, V>* _parent; // 父亲
Color _col;
pair<K, V> _kv; //存储的键值对
RBTreeNode(const pair<K,V>& kv) // 初始化列表
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};
// 主体
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
// 插入结点
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr) // 若红黑树为空叔，则插入结点直接作为根结点
{
_root = new Node(kv);
_root->_col = BLACK; // 根结点必须是黑色
return true; // 插入成功
}
// 1.采用二叉搜索树的方法找插入位置
Node* parent = nullptr;
Node* cur = _root;
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;
}
}
// 2.将待插入结点插入到树中
cur = new Node(kv); // 根据所给值构造一个结点（必须是红色）
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 3.若插入结点的父结点是红色的，则需要对红黑树进行调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent; // parent是红色其父结点一定存在
// parent为父的左孩子
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红色
{
// 颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况二：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)// cur == parent->_left
{
RotateR(grandfather); // 右单旋
// 颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else // cur == parent->_right
{
RotateL(parent); // 左单旋
RotateR(grandfather); // 右单旋
// 颜色调整
cur->_col = BLACK;
grandfather->_col = RED;
}
break; // 子树旋转后，该子树的根变为黑色，无需往上处理
}
}
else // parent是父的右孩子
{
Node* uncle = grandfather->_left;
// 情况一：叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况二：叔叔不存在或者存在且为黑
{
if (cur == parent->_right)
{
// 右左双旋
RotateL(grandfather);
// 颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
// 根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
_root->_col = BLACK;
return true;
}
// 左单旋
void RotateL(Node* parent)
{
++rotateSize;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
// 右单旋
void RotateR(Node* parent)
{
++rotateSize;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
// 中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
// 判断是否为红黑树
bool Check(Node* cur, int blackNum, int refBlackNum)
{
if (cur == nullptr)
{
if (refBlackNum != blackNum)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
//cout << blackNum << endl;
return true;
}
if (cur->_col == RED && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "存在连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
++blackNum;
return Check(cur->_left, blackNum, refBlackNum)
&& Check(cur->_right, blackNum, refBlackNum);
}
bool IsBalance()
{
if (_root && _root->_col == RED)
return false;
int refBlackNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
refBlackNum++;
cur = cur->_left;
}
return Check(_root, 0, refBlackNum);
}
// 计算红黑树结点个数
size_t Size()
{
return _Size(_root);
}
size_t _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left)
+ _Size(root->_right) + 1;
}
// 查找元素
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return NULL;
}
// 计算红黑树高度
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int Height()
{
return _Height(_root);
}
int GetRotateSize()
{
return rotateSize;
}
private:
Node* _root = nullptr;
int rotateSize = 0;
};
void TestRBTree1()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRBTree2()
{
srand(time(0));
const size_t N = 100000;
RBTree<int, int> t;
for (size_t i = 0; i < N; i++)
{
size_t x = rand();
t.Insert(make_pair(x, x));
}
cout << t.IsBalance() << endl;
}
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
58
0- 0
已为社区贡献4条内容
所有评论(0)