文章目录
- 红黑树
- 概念
- 性质(条件限制)
- 节点的定义
- 红黑树的结构
- 红黑树的插入
- cur为红,p为红,g为黑,u存在且为红
- cur为红,p为红,g为黑,u不存在或u为黑,插入到p对应的一边
- cur为红,p为红,g为黑,u不存在或u存在且为黑,插入到与p相反的一边
- 示例代码
- 红黑树的验证
- 红黑树与AVL树的比较
- 完整代码
红黑树
概念
和AVL树一样,红黑树也是一种二叉搜索树,是解决二叉搜索树不平衡的另一种方案,他在每个节点上增加一个存储位,用于表示节点的颜色,是Red或者Black
红黑树的核心思想是通过一些着色的条件限制,达到一种最长路径不超过最短路径的两倍的状态
所以说红黑树并不是严格平衡的树,而是一种近似平衡
例如
性质(条件限制)
红黑树一共有五条性质,由此来保证最长路径不超过最短路径的两倍
- 每个节点都有颜色,不是黑色就是红色
- 根节点是黑色的
- 如果一共节点是红色,那么他的子节点一定是黑色(不会出现两个红色节点连接的情况)
- 对于每个节点,以这个节点到所有后代的任意路径上,均包含相同数目的黑色节点
- 每个叶子节点(空节点)是黑色的(为了满足第四条性质,某些情况下如果没有第五条第四条会失效)
节点的定义
// 颜色
enum Color {
RED,
BLACK
};
template<class T>
struct RBTreeNode {
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
{}
};
我们定义颜色时,使用枚举类型,可以方便且明了的看到颜色
除此之外我们默认插入节点是红色的,因为一旦插入节点是黑色,就会违反第四条规则,如果要满足的话,就要走到每一条路径上插入对应的黑色节点,代价巨大
当插入节点是红色时,有可能会违反第三条规则,但是我们可以通过变色,旋转等操作在局部进行改变,这样就能使之仍然满足条件
红黑树的结构
为了后续利用红黑树封装map和set,我们对红黑树增加一个头节点,为了和根节点进行区分,我们将头节点赋为黑色,并且让头节点的parent指向根节点,left指向红黑树的最小节点,right指向最大节点,如图
红黑树的插入
红黑树插入时也是按照二叉搜索树的规则进行插入,并在此基础上加上平衡条件,因此插入也就分为两步
- 按照二叉搜索树的规则插入新节点
- 插入节点后检测规则是否被破坏
因为插入红节点时只有可能破坏第三条规则,因此我们只需要判断父节点是否为红色即可
然后我们分情况讨论
为了方便叙述,我们约定cur为插入节点,p为父节点,g为祖父节点,u为叔叔节点
cur为红,p为红,g为黑,u存在且为红
画出来是这样的
这时我们需要将g改为红色,p和u改为黑色即可,这样既能保证红色不连续,黑色数量一致,如图
但是如果g是是子树,那么g一定有父节点,当g的父节点也是红色时,也就同样需要向上调整了
cur为红,p为红,g为黑,u不存在或u为黑,插入到p对应的一边
画出来是这样的
u的情况有两种
- u节点不存在,说明cur一定是新插入的节点,因为要保证左右两个路径的黑色节点的数量相同
- u节点存在,说明cur节点是由下至上调整的红色,原因也是左右路径的黑色节点要相同
对于这两种情况的调整方法是相同的,如果p是g的左节点,cur为p的左节点,则右单旋,如果p是g的右节点,cur为p的右节点,则左单旋
同时p要变成黑色,g要变成红色
变成如下状态
那么因为最上面的根节点颜色没有变化,也就不需要继续向上调整了
cur为红,p为红,g为黑,u不存在或u存在且为黑,插入到与p相反的一边
如图
这种情况需要针对p进行单旋,如果p为g的左节点,cur为p的右节点,则对p左单旋,反之则为右单旋,此时就会变成第二种情况,再继续处理即可
第一次处理的结果如下
示例代码
template<class K, class T, class KeyOfT>
class RBTree {
typedef RBTreeNode<T> Node;
public:
pair<Node*, bool> Insert(const T& data) {
// 插入根节点直接返回
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;
// 平衡二叉树找到插入位置
while (cur) {
if (kot(cur->_data) < kot(data)) {
parent = cur;
cur = cur->_right;
} else if (kot(cur->_data) > kot(data)) {
parent = cur;
cur = cur->_left;
} else {
return make_pair(cur, false);
}
}
// 新建节点
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
// 连接父节点
if (kot(parent->_data) < kot(data)) {
parent->_right = cur;
cur->_parent = parent;
} else {
parent->_left = cur;
cur->_parent = parent;
}
// 如果父节点存在且父节点为红色则需要调整
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
// g
// p u
// c
// 判断u是否存在和他的颜色
Node* uncle = grandfather->_right;
// 如果存在且为红色
if (uncle && uncle->_col == RED) {
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 向上调整
cur = grandfather;
parent = cur->_parent;
} else {
// 如果不存在或u为黑色,需要判断同侧还是异侧
// 如果是同侧
if (cur == parent->_left) {
// g
// p
// c
RotateR(grandfather); // 右旋
// 调整颜色
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else { // p = g->r
Node* uncle = grandfather->_left;
// g
// u p
// c
// 判断u是否存在和他的颜色
// 如果存在且为红色
if (uncle && uncle->_col == RED) {
// 变色
parent->_col = BLACK;
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 {
// g
// u p
// c
//
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(newnode, true);
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
else {
if (parentParent->_left == parent) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent) {
_root = subL;
subL->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
private:
Node* _root = nullptr;
};
红黑树的验证
红黑树要验证需要验证两个部分
- 检测是否中序遍历是有序序列
- 检测是否满足红黑树的性质
这里我们就不讲红黑树的删除了,完成红黑树的验证之后就算作已经完成了任务,接下来会使用红黑树模拟实现map和set
红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树,但是红黑树不追求绝对的平衡,降低了插入和旋转的次数,因此性能比AVL更优,而且红黑树比AVL树的实现更加简单,所以实际中运用红黑树更多
完整代码
#pragma once
#include<utility>
#include<iostream>
using namespace std;
// 颜色
enum Color {
RED,
BLACK
};
template<class T>
struct RBTreeNode {
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED) {}
};
template<class K, class T, class KeyOfT>
class RBTree {
typedef RBTreeNode<T> Node;
public:
pair<Node*, bool> Insert(const T& data) {
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;
// 平衡二叉树找到插入位置
while (cur) {
if (kot(cur->_data) < kot(data)) {
parent = cur;
cur = cur->_right;
} else if (kot(cur->_data) > kot(data)) {
parent = cur;
cur = cur->_left;
} else {
return make_pair(cur, false);
}
}
// 新建节点
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
// 连接父节点
if (kot(parent->_data) < kot(data)) {
parent->_right = cur;
cur->_parent = parent;
} else {
parent->_left = cur;
cur->_parent = parent;
}
// 如果父节点存在且父节点为红色则需要调整
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
// g
// p u
// c
// 判断u是否存在和他的颜色
Node* uncle = grandfather->_right;
// 如果存在且为红色
if (uncle && uncle->_col == RED) {
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 向上调整
cur = grandfather;
parent = cur->_parent;
} else {
// 如果不存在或u为黑色,需要判断同侧还是异侧
// 如果是同侧
if (cur == parent->_left) {
// g
// p
// c
RotateR(grandfather); // 右旋
// 调整颜色
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else { // p = g->r
Node* uncle = grandfather->_left;
// g
// u p
// c
// 判断u是否存在和他的颜色
// 如果存在且为红色
if (uncle && uncle->_col == RED) {
// 变色
parent->_col = BLACK;
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 {
// g
// u p
// c
//
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(newnode, true);
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
else {
if (parentParent->_left == parent) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent) {
_root = subL;
subL->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void InOrder() {
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root) {
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_data << ' ';
_InOrder(root->_right);
}
bool Check(Node* root, int blacknum, const int refVal) {
if (root == nullptr) {
if (blacknum != refVal) {
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << "存在连续的红节点" << endl;
return false;
}
if (root->_col == BLACK) {
++blacknum;
}
return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);
}
bool IsBalance() {
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
int refVal = 0; // 参考值
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) {
++refVal;
}
cur = cur->_left;
}
int blacknum = 0;
return Check(_root, blacknum, refVal);
}
int Height() {
return _Height(_root);
}
int _Height(Node* root) {
if (root == nullptr)
return 0;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH + rightH;
}
size_t Size() {
return _Size(_root);
}
size_t _Size(Node* root) {
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_data < key) {
cur = cur->_right;
}
else if (cur->_data > key) {
cur = cur->_left;
}
else {
return cur;
}
}
return nullptr;
}
private:
Node* _root = nullptr;
};