终结B站没人能讲清楚红黑树的历史，不服等你来踢馆！-【码炫课堂收费课节选之-红黑树源码解析及手写红黑树】_哔哩哔哩_bilibili
B站的听课记录，并写下如下红黑树c++版本代码，该课程真的史诗级推荐！
/*RBtreeNode.h*****/
#pragma once
enum { RED = false, BLACK = true };
template<class K,class V >
class RBtreeNode
{
public:
// 红黑树的左右节点及父节点
RBtreeNode<K, V>* parent;
RBtreeNode<K, V>* left;
RBtreeNode<K, V>* right;
bool color;
// 创建key 和 value的值
K key;
V value;
/*构造函数**/
RBtreeNode();
RBtreeNode(RBtreeNode<K,V>* parent, RBtreeNode<K, V>* left, RBtreeNode<K, V>* right, K key, V value,bool color);
RBtreeNode(K key,V value, RBtreeNode<K, V>* parent);
void setVlue(K key,V value);
};
/*RBtreeNode.cpp*****/
#include "RBtreeNode.h"
// 默认构造函数，里面没有内容
template<class K,class V>
RBtreeNode<K, V>::RBtreeNode()
{
this->parent = nullptr;
this->left = nullptr;
this->right = nullptr;
// 主要是根节点为黑色，因此默认构造函数为黑色
this->color = BLACK;
}
template<class K, class V>
RBtreeNode<K, V>::RBtreeNode(RBtreeNode<K, V>* parent, RBtreeNode<K, V>* left, RBtreeNode<K, V>* right, K key, V value,bool color)
{
this->parent = parent;
this->left = left;
this->right = right;
this->key = key;
this->value = value;
this->color = color;
}
template<class K, class V>
RBtreeNode<K, V>::RBtreeNode(K key, V value, RBtreeNode<K, V>* parent)
{
this->key = key;
this->value = value;
this->parent = parent;
this->color = BLACK;
}
template<class K, class V>
void RBtreeNode<K, V>::setVlue(K key, V value)
{
this->key = key;
this->value = value;
}
/*RBtree.h*****/
#pragma once
#include "RBtreeNode.h"
using namespace std;
template<class K,class V>
class RBtree
{
private:
RBtreeNode<K,V>* root;
RBtreeNode<K, V>* rightof(RBtreeNode<K, V>* p) { return p->right; }; //获取右子
RBtreeNode<K, V>* leftof(RBtreeNode<K, V>* p) { return p->left; }; //获取左子
RBtreeNode<K, V>* parentof(RBtreeNode<K, V>* p) { return p->parent; }//获取父亲
// 默认空节点
RBtreeNode<K, V>* colorof(RBtreeNode<K, V>* p) { return p == nullptr ? p->color = BLACK : p->color = RED; } // 颜色更改
const RBtreeNode<K, V>* getRoot() { return root; }
void setRoot(RBtreeNode<K, V>* temp) { root = temp; }
void fixAfterput(RBtreeNode<K, V>* p);
void fixAfterdelete(RBtreeNode<K, V>* p); // 删除之后再修改
// 查找前继节点
RBtreeNode<K, V>* predecessor(RBtreeNode<K, V>* p);
RBtreeNode<K, V>* successor(RBtreeNode<K, V>* p);
public:
/*公有接口**/
void leftRotate(RBtreeNode<K, V>* p);
void rightRotate(RBtreeNode<K, V>* p);
void put(K key, V value);
// 删除节点操作
void deleteNode(RBtreeNode<K, V>* p);
};
/*RBtree.cpp*******/
#include "RBtree.h"
/**
* 围绕p左旋
* pf pf
* / /
* p pr(r)
* / \ ==> / \
* pl pr(r) p rr
* / \ / \
* rl rr pl rl
*
* @param p
*/
template<class K,class V>
void RBtree<K, V>::leftRotate(RBtreeNode<K, V>* p)
{
if (p != nullptr)
{
RBtreeNode<K, V>* r = p->right;
p->right = r->left;
if (r->left != nullptr)
{
r->left->parent = p;
}
r->parent = p->parent;
if (p->parent == nullptr)
{
r = root;
}
else if (p->parent->left == p)
{
p->parent->left = r;
}
else if (p->parent->right == p)
{
p->parent->right = r;
}
r->left = p;
p->parent = r;
}
}
/**
* 右旋
* pf pf
* \ \
* p (l)pl
* / \ => / \
*(l)pl pr ll p
* / \ / \
* ll lr lr pr
*
* @param p
*/
template<class K, class V>
void RBtree<K, V>::rightRotate(RBtreeNode<K, V>* p)
{
if (p != nullptr)
{
RBtreeNode<K, V>* l = p->left;
p->left = l->right;
if (l->right != nullptr)
{
l->right->parent = p;
}
l->parent = p->parent;
if (p->parent == nullptr)
{
l = root;
}
else if (p->parent->left == p)
{
p->parent->left = l;
}
else if (p->parent->right == p)
{
p->parent->right = l;
}
l->right = p;
p->parent = l;
}
}
// c++没有类型，貌似不能设置空值
template<class K, class V>
void RBtree<K, V>::put(K key, V value)
{
// 申明一个临时变量指向跟节点，通过根节点进行左右寻找
RBtreeNode<K, V>* p = root;
RBtreeNode<K, V>* dad; // 来一个临时变量指向父亲
int cmp; // 比较常量
// 1、第一种情况若没有根节点，则此插入元素便为根节点
if (p == nullptr)
{
root = new RBtreeNode<K, V>(key, value , nullptr);
return;
}
// 2、第二种情况不是根节点则先根据循环查找要插入节点的位置
do
{ // 直接通过比较大小的符号来比较key
dad = p;
if (key > p->key) // 更大向右边找
{
p = p->right; //向右边找
cmp = 1; // 更大为1
}
else if (key < p->key)//更小向左边找
{
p = p->left;//向左边找
cmp = -1; // 更小为-1
}
else if (key == p->key)//若找到相等的直接替代
{
p->setVlue(key,value);//替代
return;
}
} while (p != nullptr); // r一个个向下寻找，到最后寻找到空指针之后便退出循环
RBtreeNode<K, V>* e = new RBtreeNode<K, V>(key, value, dad);
// 找到之后便开始赋值
if (cmp == 1)
{
dad->right = e;
}
else if(cmp == -1)
{
dad->left = e;
}
// 调整函数
fixAfterput(e);
}
template<class K, class V>
void RBtree<K, V>::fixAfterput(RBtreeNode<K, V>* p)
{
p->color = RED; // 新加进来的元素是红色
while (p != nullptr && p != root && p->parent->color == RED)
{
// 判断左三右三的情况
// 用爷爷和爸爸查找
if (parentof(parentof(p))->left == parentof(p))
{
// 满足情况是左三
/*
* 左3分为两种情况
* 1、四节点
* 2、三节点
*/
RBtreeNode<K, V>* u = parentof(parentof(p))->right; // 令u为叔叔节点
if ( u->color == RED) // 叔叔节点为红色说明叔叔的存在，若为空节点系统将默认给黑
{
// 叔叔节点存在则进入四节点情况
// p
// / \
// a e
// \
// x（新节点）
// 直接变色
parentof(parentof(p))->color = RED;
u->color = BLACK;
parentof(p)->color = BLACK;
// 此时爷爷变红，因此要考虑爷爷和太爷爷之间的关系
// 因为这里直接变红了
p = parentof(parentof(p));
}
else // 若叔叔节点不存在则是三节点添加新节点的情况
{
// 叔叔节点添加新节点分为常规和特殊情况
// 特殊情况就是 e e
// / /
// j j
// \ /
// p p
// 需要先旋转处理成正常情况
if (p->parent->right == p)
{
p = p->parent;
leftRotate(p);
// 处理完以上步骤之后便成为了常规的左偏
}
// 需要旋转变色
parentof(parentof(p))->color = RED;
parentof(p)->color = BLACK;
p->color = RED;
// 此时注意应该要先变色再旋转
// 因为旋转之后父类就变了
rightRotate(parentof(parentof(p)));
// 旋转之后 j
// / \
// p e
}
}
else
{
// 否则就是右三的
/*
* 右3分为两种情况
* 1、四节点
* 2、三节点
*/
RBtreeNode<K, V>* u = parentof(parentof(p))->left; // 令u为叔叔节点
if (u->color == RED) // 不为空节点说明叔叔节点存在
{
// 叔叔节点存在则进入四节点情况
// 直接变色
parentof(parentof(p))->color = RED;
u->color = BLACK;
parentof(p)->color = BLACK;
// 此时爷爷变红，因此要考虑爷爷和太爷爷之间的关系
// 因为这里直接变红了
p = parentof(parentof(p));
}
else // 若叔叔节点不存在则是三节点添加新节点的情况
{
// 叔叔节点添加新节点分为常规和特殊情况
// 特殊情况就是 e e
// \ \
// j j
// \ /
// p p
// 需要先旋转处理成正常情况
if (p->parent->left == p)
{
p = p->parent;
rightRotate(p);
// 处理完以上步骤之后便成为了常规的左偏
}
// 需要旋转变色
parentof(parentof(p))->color = RED;
parentof(p)->color = BLACK;
p->color = RED;
// 此时注意应该要先变色再旋转
// 因为旋转之后父类就变了
leftRotate(parentof(parentof(p)));
// 旋转之后 j
// / \
// p e
}
}
}
root->color = BLACK;
}
// 前继节点-小于该节点的最大值
template <class K,class V>
RBtreeNode<K, V>* RBtree<K, V>::predecessor(RBtreeNode<K, V>* p)
{
if (p == nullptr)
{
return nullptr;
}
else if(p->left != nullptr) // 若左子不为0，先去左子
{
RBtreeNode<K, V>* node;
node = p->left;
//第一种情况 p
// /
// a
// \
// x
//也是不拐弯的情况
//因此找到左子之后无限向右循环
//来找到小于p值的最大值
while (node->right != nullptr)
{
node = node->right;
}
return node;
}
else
{
//没有左子，就是特殊情况
// a
// / \
// x b
// /
// c
// /
// p
RBtreeNode<K, V>* parentT = p->parent; // 创建指向父节点的临时变量
RBtreeNode<K, V>* node = p; // 创建临时变量node
while (parentT->left == node && parentT != nullptr) //一直到拐弯或者到了跟节点
{
node = parentT;
parentT = parentof(parentT);
}
return parentT;
}
}
// 后续节点-大于该节点的最小值
template <class K, class V>
RBtreeNode<K, V>* RBtree<K, V>::successor(RBtreeNode<K, V>* p)
{
if (p == nullptr)
{
return nullptr;
}
else if (p->right != nullptr)
{
RBtreeNode<K, V>* node;
node = p->right;
while (node->left != nullptr)
{
node = node->left;
}
return node;
}
else
{
RBtreeNode<K, V>* parentT = p->parent; // 创建指向父节点的临时变量
RBtreeNode<K, V>* node = p; // 创建临时变量node
while (parentT->right == node && parentT != nullptr) //一直到拐弯或者到了跟节点
{
node = parentT;
parentT = parentof(parentT);
}
return parentT;
}
}
/*删除操作：
*1、删除叶子节点直接删除
*2、被删除的节点有一个子节点，删除它之后使用子节点替代它
*3、被删除的节点有两个子节点，查找前继或后续节点来替代被删除节点
*/
template <class K,class V>
void RBtree<K, V>::deleteNode(RBtreeNode<K, V>* p)
{
// 有两个子节点的情况，先进行节点替换
if ( p->left != nullptr && p->right != nullptr)
{
// 使用后续节点
RBtreeNode<K, V>* p_successor = successor(p);
// 使用前继节点
// RBtreeNode<K, V>* p_predecessor = predecessor(p);
// 使用前继或者后续的值来替代原节点的值
p->key = p_successor->key;
p->value = p_successor->value;
p = p_successor; //指向要删除节点
}
// 节点替换后，情况3就变成了1和2两种情况，后继节点为便为2-3-4树的叶子节点
// 删除节点看看有没有左右子树
RBtreeNode<K, V>* replacement = p->left != nullptr ? p->left : p->right;
if (replacement != nullptr) // 删除节点有子树
{
replacement->parent = p->parent; //先把父亲绑上
if (p->parent == nullptr) // 说明p是根节点，用replacement来替代根节点
{
this->root = replacement;
}
else if (p == p->parent->left)
{
p->parent->left = replacement;
}
else if (p == p->parent->right)
{
p->parent->right = replacement;
}
// 若被删除颜色为黑色，因为破坏了平衡
// 所以此时需要调整
if (p->color == BLACK)
{
// 此时改颜色就好了
fixAfterdelete(replacement);
}
p->parent = nullptr;
p->left = nullptr;
p->right = nullptr;
}
else if (replacement == nullptr)//若没有子节点则说明替代节点为叶子节点
{
// 因为要保证黑色平衡，所以若删除节点是黑色要先调整
// 先听课，因为这里的操作我还不明白
if (p->color == BLACK)
{
fixAfterdelete(p);
}
//再删除
//这里多添加根节点的判断是因为经过fixAfterRemove()之后
//p可能变成根节点
if (p->parent != nullptr)
{
if (p == p->parent->left)
{
p->parent->left = nullptr;
}
else if (p == p->parent->right)
{
p->parent->right = nullptr;
}
p->parent = nullptr; // 双向清空
}
}
else if (p->parent == nullptr) // 删除节点就是根节点
{
this->root = nullptr;
}
}
template<class K,class V>
void RBtree<K, V>::fixAfterdelete(RBtreeNode<K, V>* p)
{
while (p != root && colorof(p)==BLACK) // p为根节点的时候直接退出循环
{
//先判断p是父节点的左子还是右子
if (p->parent->left == p) // 若是左子树
{
RBtreeNode<K, V>* rnode = p->parent->right;
if (rnode->color == RED)// 若兄弟为红色，说明该节点是假兄弟节点(其实一定会有兄弟的，所以不需要判断兄弟的有无(因为2-3-4树的性质))
{
// 当兄弟节点是红色的时候，其恰好为假兄弟节点
// 那么就需要做相应的处理，用以查找真正的兄弟节点
// 此时在2-3-4树中，其父节点为一黑一红的3节点，红色便为p的假兄弟节点
// 因为是三节点树故必须有三个子节点，当我自身父节点的右子节点为假兄弟节点时
// 说明其他两个子节点连接在红色的下面，此时只需要左旋即可
// x(黑)
// / \
// p(黑) 假兄弟节点（红）
// / \
// a(黑) b(黑) 其中a,b为真兄弟节点
rnode->parent->color = RED;
rnode->color = BLACK;
leftRotate(rnode->parent); //左旋
// 找到真正的兄弟节点
rnode = p->parent->right;
}
//找兄弟节点借，若兄弟节点没的借
if (rnode->left->color==BLACK && rnode->right->color== BLACK)
{
//没的借要进行递归
rnode->color = RED;
p = p->parent;
}
else //若兄弟节点有的借
{
if (rnode->right->color==BLACK)//若右节点空。则左节点一定有东西，此时需要旋转处理
{
//旋转前先变色
rnode->left->color = BLACK;
rnode->color = RED;
//旋转
rightRotate(rnode);
}
// 三四节点都要经历这种变色和旋转
rnode->color = rnode->parent->color;
rnode->parent->color = BLACK;
rnode->right->color = BLACK;
// 旋转
leftRotate(rnode->parent);
// 有的借之后便可以直接结束循环
p = root; //将指针赋给根节点结束循环
}
}else//若是右子节点
{
RBtreeNode<K, V>* lnode = p->parent->left;
if (lnode->color == RED)// 若兄弟为红色，其实一定会有兄弟的，所以不需要判断兄弟的有无(因为2-3-4树的性质)
{
lnode->parent->color = RED;
lnode->color = BLACK;
rightRotate(lnode->parent); //左旋
// 找到真正的兄弟节点
lnode = p->parent->left;
}
//找兄弟节点借，若兄弟节点没的借
if (lnode->right->color == BLACK && lnode->left->color == BLACK)
{
//情况复杂，等下再写
lnode->color = RED;
p = p->parent;
}
else //若兄弟节点有的借
{
if (lnode->left->color == BLACK)//若右节点空。则左节点一定有东西，此时需要旋转处理
{
//旋转前先变色
lnode->right->color = BLACK;
lnode->color = RED;
//旋转
leftRotate(lnode);
}
// 三四节点都要经历这种变色和旋转
lnode->color = lnode->parent->color;
lnode->parent->color = BLACK;
lnode->left->color = BLACK;
// 旋转
rightRotate(lnode->parent);
// 有的借之后便可以直接结束循环
p = root; //将指针赋给根节点结束循环
}
}
}
// 若为红色的情况则直接变黑
p->color = BLACK;
}版权声明：本文为qq_42138448原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。