一、红黑树的定义
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。(说它是接近平衡因为它并没有像AVL树的平衡因子的概念,它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构,进而提升整体的性能)
红黑树的性质:
1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 如果一个节点是红色的,则它的两个孩子结点是黑色的。
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。
为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
由性质4可知,红黑树的根节点到其叶子结点的所有路径上黑色节点的个数相同,那么一条路径上如果没有红色节点,则该路径为最短路径。
由性质3可知,红黑树的红色节点不连续,那么在一条路径上间隔插入红色节点,则该路径为最长路径。
得出结论:最短路径为全黑色节点,最长路径为一黑一红节点。所以,最长路径中节点个数不会超过最短路径节点个数的两倍。最短路径和最长路径可能在一颗红黑树上并不存在,如上图中就不存在最短路径。
二、红黑树的基本操作实现
红黑树同样是二叉查找树的演变,因此红黑树和AVL树一样,查找、遍历操作基本和二叉查找树一样。而红黑树的插入和删除操作与AVL树相比,需要对节点的颜色进行调整,也使用了旋转操作。
红黑树节点定义:
enum Colour {//枚举类型,定义红黑树颜色
RED,
BLACK
};
template<class k,class v>
struct RBTreeNode
{
RBTreeNode<k, v>* _left;
RBTreeNode<k, v>* _right;
RBTreeNode<k, v>* _parent;
pair<k, v> _kv;
Colour _col;
RBTreeNode(const pair<k, v>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
红黑树节点的结构与AVL树节点类似,这里用节点的颜色来替换平衡因子。
2.1 红黑树的插入操作
插入中需要用到的节点概念:
- parent:父亲节点
- uncle:叔叔节点( parent 的兄弟节点)
- grand:祖父节点( parent 的父节点)
红黑树的节点有颜色之分,那么新插入节点的颜色是红色还是黑色呢?
当插入节点的颜色是黑色,新节点所在路径上的黑色节点个数+1。要保持每条路径上黑色节点个数相同,需要对其他路径一一调整,这样操作是非常繁琐的。
当插入节点的颜色是红色,所有路径上的黑色节点个数均不变。当新节点的父亲是黑色时,插入新节点,依然符合红黑树性质,无需调整。当新节点的父亲是红色时,进行调整。
得出结论:新插入节点默认颜色为红色。
2.1.1 叔叔节点(uncle)存在且为红
新插入节点cur的父亲为黑,插入后依然符合红黑树性质,无需调整。新插入节点cur的父亲为红,并且爷爷节点(grandparent)为黑(红黑树的红色节点不连续),叔叔节点(uncle)存在且为红。
此时对该子树进行操作,将parent节点变为黑色,grandparent节点变为红色,这样就能保证该子树中每条路径中黑色节点相同,并且没有连续的红色节点。然后更新cur、parent节点,parent = cur->_parent,cur=grandparent,沿插入路径向上调整,直到该树中没有连续的红节点。如下图所示:
2.1.2 叔叔节点(uncle)不存在或存在且为黑
新插入节点cur的父亲为红,并且爷爷节点(grandparent)为黑(红黑树的红色节点不连续),叔叔节点(uncle)不存在或存在且为黑。
在插入cur节点前,该树各路径上黑色节点个数已经不同,不满足红黑树的性质。说明cur节点不是新插入的节点,且cur以前是黑色节点,经过第一种情况的颜色调整后,cur节点变为红色。此时需要旋转操作,并更改颜色。这里不对旋转做详细叙述,参考数据结构——AVL树详解-CSDN博客。
右单旋:当parent节点时grandparent节点的右孩子,且cur节点是parent节点的右孩子
旋转后将grandparent节点变为红色,parent变为黑色。
右单旋:当parent节点时grandparent节点的左孩子,且cur节点是parent节点的左孩子
旋转后将grandparent节点变为红色,parent变为黑色。
左右双旋:当parent节点时grandparent节点的左孩子,且cur节点是parent节点的右孩子
旋转后将grandparent节点变为红色,cur变为黑色。
右左双旋:当parent节点时grandparent节点的右孩子,且cur节点是parent节点的左孩子
旋转后将grandparent节点变为红色,cur变为黑色。
插入代码实现具体实现如下:
bool Insert(const pair<k, v>& kv)
{
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
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;
}
}
cur = new Node(kv); // 在cur位置插入红色节点
if (parent->_kv.first < kv.first) {//连接cur节点到红黑树
parent->_right = cur;
}
else {
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//1:当叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
//2:叔叔不存在或者存在且为黑,由第一种情况调整而来
//旋转+变色
if (cur == parent->_left)
{
// g
// p u
// c
//此时路径上黑色节点不相同,且有连续的红色节点,不满足最长路径是最短路径的两倍
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else {
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
// 情况一:叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
// 情况二:叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
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 true;
}
三、红黑树的验证
红黑树的检测分为两步:
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质:根节点是否为黑色,各路径黑色节点个数是否相同,红色节点是否连续出现。
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);
}
先判断根节点,根节点为空或者根节点为红色,直接返回false。按照中序遍历,找到最左路径,遇到黑色节点refBlackNum++,最后得到最左路径的黑色节点个数。调用Check函数,传入根节点和refBlackNum。文章来源:https://www.toymoban.com/news/detail-849599.html
bool Check(Node* cur, int blackNum, int refBlackNum)
{//传blackNum,每次走到黑色节点++,为nullptr回到上一层调用走右子树,此时blackNum还是上一层的值
if (cur == nullptr) {
if (refBlackNum != blackNum) {
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (cur->_col == RED && cur->_parent->_col == RED) {
cout << "存在连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
++blackNum;
return Check(cur->_left, blackNum, refBlackNum) && Check(cur->_right, blackNum, refBlackNum);
}
当cur==nullptr,说明当前路径已走完,判断这条路径黑色节点个数blackNum是否和refBlackNum(标准值)是否相等。不为空时,判断当前节点是否为红色,如果cur为红色,再判断其父亲是否为红色(&&避免判断根节点的parent)。如果是黑色节点,blackNum++,最后递归左子树与右子树。blackNum为传值,每次遇到黑色节点++,为nullptr回到上一层调用遍历右子树,此时blackNum还是上一层的值。文章来源地址https://www.toymoban.com/news/detail-849599.html
四、红黑树的模拟实现
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include<vector>
#include<iostream>
#include<time.h>
using namespace std;
enum Colour {//枚举类型,红黑树颜色
RED,
BLACK
};
template<class k,class v>
struct RBTreeNode
{
RBTreeNode<k, v>* _left;
RBTreeNode<k, v>* _right;
RBTreeNode<k, v>* _parent;
pair<k, v> _kv;
Colour _col;
RBTreeNode(const pair<k, v>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _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;
}
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;
}
}
cur = new Node(kv); // 在cur位置插入红色节点
if (parent->_kv.first < kv.first) {//连接cur节点到红黑树
parent->_right = cur;
}
else {
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//1:当叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
//2:叔叔不存在或者存在且为黑,由第一种情况调整而来
//旋转+变色
if (cur == parent->_left)
{
// g
// p u
// c
//此时路径上黑色节点不相同,且有连续的红色节点,不满足最长路径是最短路径的两倍
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else {
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
// 情况一:叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
// 情况二:叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
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 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->_parent = subR;
if (parent == _root)//考虑parent是该树的根节点
{
_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;
}
}
size_t Size()
{
return _Size(_root);
}
size_t _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left)
+ _Size(root->_right) + 1;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
int GetRotateSize()
{
return rotateSize;
}
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);
}
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;
}
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);
}
bool Check(Node* cur, int blackNum, int refBlackNum)
{//传blackNum,每次走到黑色节点++,为nullptr回到上一层调用走右子树,此时blackNum还是上一层的值
if (cur == nullptr) {
if (refBlackNum != blackNum) {
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (cur->_col == RED && cur->_parent->_col == RED) {
cout << "存在连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
++blackNum;
return Check(cur->_left, blackNum, refBlackNum) && Check(cur->_right, blackNum, refBlackNum);
}
private:
Node* _root = nullptr;
int rotateSize = 0;
};
五、红黑树和AVL树的比较
- AVL树的时间复杂度虽然优于红黑树,但是对于现在的计算机,cpu太快,可以忽略性能差异。
- 红黑树的插入删除比AVL树更便于控制操作。
- 红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)。
到了这里,关于数据结构——红黑树详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!