自学内容网 自学内容网
自学内容网 > 正文

数据结构：红黑树

🕗 发布于 2024-10-14 14:51 数据结构  

前言

前面我们介绍了AVL树来解决搜索二叉树不平衡的问题，今天我们带来一种新的解决方案，同时，这种解决方案在实践中比AVL树更常用，这种数据结构就是红黑树

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

概念还是很抽象，我们直接看图来理解红黑树
在这里插入图片描述

一目了然，红黑树嘛，每个节点要么是黑色，要么是红色。

注意：红黑树并不像AVL树一样是绝对平衡的，红黑树是相对平衡的，红黑树通过让最长路径长度不超过最短路径长度的两倍来控制相对平衡。

红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 （不能出现连续红色节点）
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点（每条路径上黑色节点个数相同）
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

我们来思考一下，为什么这几条性质就可以帮红黑树处于平衡状态呢？
在这些性质的限制下，我们可以发现：
最短路径：全部是黑色节点
最长路径：一黑一红交替出现

所以，最长路径不会超过最短路径的两倍，所以红黑树可以到达相对平衡

红黑树的节点(以K_V型为例）

红黑树的节点，我们依旧采用三叉链

但是，我们不需要平衡因子，
我们需要引入颜色变量，
由于只有红色和黑色，我们就直接使用枚举类型来表示颜色

enum Color
{
RED,
BLACK
};

template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K,V>* _left = nullptr;
RBTreeNode<K,V>* _right = nullptr;
RBTreeNode<K,V>* _parent = nullptr;
Color _col = RED;
pair<K, V> _value;

RBTreeNode(const pair<K,V>& value)
:_value(value)
{}
};

红黑树的插入

在学习完了AVL树之后，再来理解红黑树的插入是非常简单的。

新插入节点颜色

在学习插入之前，我们来思考一个问题，新插入的节点，我们究竟给什么颜色呢？
给黑色还是红色呢？

如果我们给黑色，那么我们就破坏了第四条性质
此时，新插入的节点的这条路径上的黑色节点数量多了一个，直接影响了整棵树，破坏性非常强

如果我们给红色，那么我们就破坏了第三条性质
此时，只是影响了当前的这一棵子树，破坏性比上面的情况小

于是，我们选择坏处小的这种情况。

我们给新插入节点的颜色默认为红色。（当然根节点除外）

插入

首先还是按照搜索二叉树的插入方法一样，大的往右走，小的往左走，然后连接上父亲节点。

处理完这一系列操作之后

我们就要像AVL树更新平衡因子一样，更新颜色了。

我们插入的是红色节点，破坏了第三条性质，不能出现连续红色节点，所以我们需要维护颜色。

当我们需要调整的时候，一定是这种情况
cur = 红，parent = 红，grandparent = 黑
如果父亲不是红，就不需要调整，如果爷爷是红，那么早就该调整了。

因此我们只需要考虑爷爷的另一个节点的颜色即可，也就是叔叔节点的颜色

叔叔存在且为红色（变色）

在这里插入图片描述

此时我们只需要调整颜色即可，我们将parent 和uncle都变成黑色，把爷爷变成红色，
这样既解决了连续红色节点的问题，又没有给该路径增加新节点

调整后变成了下图
在这里插入图片描述

此时爷爷变红了，需要担心爷爷的父亲是否也是红色，那么就需要向上继续调整，直到爷爷的父亲不是红色节点为止。
在这里插入图片描述

注意：根节点除外，当爷爷的父亲不存在的时候，就到了根节点，根节点始终要保持黑色，我们可以在出循环之后，给根节点置为黑色，就可以避免在循环内额外处理这种情况。

叔叔不存在或叔叔为黑色（旋转 + 变色）

（1）单旋
在这里插入图片描述

此时单纯的变色已经不能够解决问题了，需要额外引入旋转
看左边这个图，出现了连续的红色节点，需要调整了，说明左边高了，我们就需要通过旋转来控制平衡，
这里的旋转和AVL树的旋转操作一样，
这里进行右单旋即可
右单旋之后，变成了右图
旋转之后，将父亲置为黑色，爷爷置为红色
即消除了连续红色节点，又没有新增每条路径上的黑色节点。

左单旋也是一样，就不多赘述了。

(2)双旋
在这里插入图片描述
双旋和单旋的区别在于，cur究竟是在parent的左边还是右边
如果在左边就是完全失衡，只需要右单旋，如果在右边则偏了，需要先左单旋成完全失衡，再右单旋进行调整。

像第一幅图，cur在parent的右边，就需要进行双旋，先一parent为root，进行左单旋，
就变成了第二幅图，此时以grandparent为root进行右单旋即可
就变成了第三幅图

此时对颜色的调整为
cur需要变成黑色，grandparent需要变成红色（图中出现了一点问题，相信读者能看出来）

对于旋转，我们在旋转完成之后的子树的根节点就是黑色，不可能出现连续的红色节点，所以不需要继续向上调整，我们也就可以跳出循环，直接break掉。

另外另一个方向的双旋也是类似，这里也不多赘述了

代码

#include <iostream>

using namespace std;

namespace bit
{
enum Color
{
RED,
BLACK
};

template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K,V>* _left = nullptr;
RBTreeNode<K,V>* _right = nullptr;
RBTreeNode<K,V>* _parent = nullptr;
Color _col = RED;
pair<K, V> _value;
RBTreeNode(const pair<K,V>& value)
:_value(value)
{}
};

template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root = nullptr;

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

Node* pparent = parent->_parent;

parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

subL->_right = parent;
parent->_parent = subL;

if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = pparent;
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
}


}

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;

parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

subR->_left = parent;
parent->_parent = subR;

if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = pparent;
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
}
}

void inorder(Node* root)
{
if (root == nullptr)
return;

inorder(root->_left);
cout << root->_value.first << ":" << root->_value.second << endl;
inorder(root->_right);
}

public:
void InOrder()
{
inorder(_root);
}

bool insert(const pair<K, V>& value)
{
if (_root == nullptr)//空树就直接申请节点，将根节点处理成黑色
{
_root = new Node(value);
_root->_col = BLACK;
return true;
}

Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (value.first > cur->_value.first)
{
parent = cur;
cur = cur->_right;
}
else if (value.first < cur->_value.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;//已经存在就插入失败
}
}

cur = new Node(value);
cur->_parent = parent;

if (value.first > parent->_value.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}


while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)//parent在左侧
{
Node* uncle = grandparent->_right;

if (uncle && uncle->_col == RED)//叔叔存在且为红
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//叔叔不存在或者叔叔为黑色，则进行旋转 + 变色
{
if (cur == parent->_left)//进行右单旋即可
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}

break;
}
}
else//parent在右侧
{
Node* uncle = grandparent->_left;

if (uncle && uncle->_col == RED)//叔叔存在且为红
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//叔叔不存在或者叔叔为黑色
{
if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}


}
}

_root->_col = BLACK;

return true;
}

};
}

关于红黑树的删除，这里就不进行讲解了，感兴趣的同学可以去看看算法导论和殷人昆老师的数据结构教材，里面可以找到答案。


原文地址：https://blog.csdn.net/2303_78940834/article/details/142894909

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024