红黑树
红黑树,是一种二叉搜索树,但在每个节点上增加了一个存储位表示节点的颜色,可以是红色或者是黑色.通过对任意一条从根到叶子节点的路径上各个节点着色方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因而是接*衡的.
红黑树的性质
- 每个节点不是红色就是黑色
- 根节点必须是黑色
- 如果一个节点是红的,则它的两个孩子是黑的(不存在连续的红节点)
- 从某一节点出发到所有的叶子节点,其中经过的黑色节点数量相等
- 每个叶子节点是黑色的(这里的叶子节点指的是NULL节点)
对于一个节点,到其叶子节点所经过的最短路径即全为黑色节点,最长路径则为一黑一红交错的路径
红黑树的实现:
红黑树节点数据结构:
enum Color {
Red,
Black
};
template<class T>
struct RBTree {
T _val;
Color _color;
RBTree<T>* _parent;
RBTree<T>* _left;
RBTree<T>* _right;
RBTree(const pair<T>& val = T(), const Color& color = Red)
:_val(val)
,_color(color)
,_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
{}
};红黑树的插入:
插入分为两个步骤:
- 按照二叉搜索树的特性找到插入的位置
- 按照红黑树的特性进行调节(旋转+调整颜色)
决定新插入节点的颜色:
如果新插入的结点为红色，则有可能打破了不能有连续的红结点这一规则，而如果插入的是黑色，则又破坏了每个路径的黑节点数量相同这一规则。如果都会破坏的话，就需要选择一个方便修复的，而不能有连续的红结点这一规则，只需要进行一下颜色的变换或者旋转，就可以解决这个问题，所以新增节点都为红色。
插入节点出现的各种情况:
情况1:插入节点的父节点为黑色
此时是最好的情况,因为没有破坏任何规则,所以此时无须任何处理.
情况2:插入节点的父节点为红色,叔叔节点也为红色,祖父为黑色
因为出现了连续的红色节点,所以只需要进行颜色的修正即可解决.(将父节点和叔叔节点变黑,祖父节点变红即可).同时,因为祖父节点之上可能还有其它节点,还需要从祖父节点的位置继续向上调整.
情况3:插入节点的父节点为红色,叔叔为黑或者不存在,祖父为黑.孩子与父亲呈直线状态.
这里有两种情况:
- 如果叔叔存在，则此时的孩子节点可能是下面的子树在进行变色处理时，将其从原本的黑色变为了红色。（否则不满足路径黑节点数量相同的性质）
- 如果叔叔不存在，则此时的孩子节点是刚插入进来的结点，因为不能有连续的红结点，所以孩子和父亲必须有一个是黑色，但是此时又不满足黑节点数量相同的性质。
解决的方法也不难，只需要旋转+变色处理即可
和AVL树一样，因为父亲和孩子呈直线状态，所以只需要单旋即可。
如果父亲是祖父的左孩子，孩子是父亲的左孩子，此时祖父进行右单旋
如果父亲是祖父的右孩子，孩子是父亲的右孩子，此时祖父进行左单旋。
情况4:父亲为红色,叔叔为黑色或者不存在,祖父为黑色.孩子与父亲呈折现状态.
这种情况与情况3类似,采取的解决办法是双旋+变色处理
如果父亲是祖父的左孩子,孩子是父亲的右孩子,父亲此时需要左单旋.
如果父亲是祖父的右孩子,孩子是父亲的左孩子,父亲此时需要右单旋.
左/右单旋后,交换父节点与新插入节点之后,就变成了情况3,接着按照情况3的处理办法接着处理即可.
bool Insert(const std::pair<K, V>& val){
//判断树是否为空
if (_root == nullptr){
_root = new Node(val, Black);
return true;
}
//查找
Node* cur = _root;
Node* parent = nullptr;
while (cur){
if (val.first > cur->_val.first){
parent = cur;
cur = cur->_right;
}
else if (val.first < cur->_val.first){
parent = cur;
cur = cur->_left;
}
else{
return false;
}
}
//新插入节点为红色
cur = new Node(val, Red);
//保存插入的结点，因为后面会往上更新红黑树，所以cur可能会变化。
Node* newNode = cur;
//判断插入位置
if (cur->_val.first > parent->_val.first){
parent->_right = cur;
}
else{
parent->_left = cur;
}
cur->_parent = parent;
//更新红黑树，如果父节点的颜色为黑，则说明满足条件，不需要处理，如果为红，则说明不满足，需要处理。
while (parent && parent->_color == Red){
Node* ppNode = parent->_parent;
//如果父节点为祖父的左子树
if (ppNode->_left == parent){
//此时判断叔叔节点的状态，红黑树状态取决于叔叔
Node* uncle = ppNode->_right;
//第一种情况，如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整
if (uncle && uncle->_color == Red){
//变色
uncle->_color = parent->_color = Black;
ppNode->_color = Red;
//继续往上
cur = ppNode;
parent = cur->_parent;
}
/*
叔叔节点为黑或者不存在，此时有两种情况
情况二：cur为父节点的左子树，即直线状态。
情况三：cur为父节点的右子树，即折线状态。
情况二单旋一次后更改颜色即可完成
对于情况三，如果将其进行一次旋转后再稍微处理，就可以转换成情况二
*/
else{
//因为这里的双旋和AVL不一样，可以不用处理平衡因子，所以如果为折线则先旋转处理后，将其转换为直线处理即可。
//第三种情况，折线状态，转换为直线状态处理
if (parent->_right == cur){
RotateL(parent);
//单旋后再交换节点，即可变成直线状态。
std::swap(parent, cur);
}
//处理第二种状态
RotateR(ppNode);
parent->_color = Black;
ppNode->_color = Red;
//处理完成
break;
}
}
//如果父亲为祖父的右子树
else{
//此时叔叔为左子树。
Node* uncle = ppNode->_left;
if (uncle && uncle->_color == Red){
uncle->_color = parent->_color = Black;
ppNode->_color = Red;
cur = ppNode;
parent = cur->_parent;
}
else{
if (parent->_left == cur){
RotateR(parent);
std::swap(cur, parent);
}
RotateL(ppNode);
ppNode->_color = Red;
parent->_color = Black;
break;
}
}
}
//为了防止不小心把根节点改为红色，最后手动改为黑色即可
_root->_color = Black;
return true;
}
旋转:左旋AND右旋
//左旋:
void RotateL(){
Node* subR = parent->_right;
Node* subRL = subR->_left;
subR->_left = parent;
parent->_right = subRL;
if(subRL){
subRL->_parent = parent;
}
//连接subR与祖父节点
if(parent == _root){
_root = subR;
subR->_parent = nullptr;
}else{
Node* g = parent->_parent;
subR->_parent = g;
if(g->_left == parent){
g->_left = subR;
}else{
g->_right = subR;
}
}
parent->_parent = subR;
}
//右旋:
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
subL->_right = parent;
parent->_left = subLR;
if (sunLR) {
subLR->_parent = parent;
}
if (parent == root) {
_root = subL;
subL->_parent = nullptr;
}
else {
Node* g = parent->_parent;
subL->_parent = g;
if (g->_left == parent) {
g->_left = subL;
}
else {
g->_right = subL;
}
}
//再连接parent的_parent
parent->_parent = subL;
}
查找:
bool Find(const std::pair<K, V>& data){
//根据二叉搜索树的性质，从根节点出发，比根节点大则查找右子树，比根节点小则查找左子树
Node* cur = _root;
while (cur)
{
//比根节点大则查找右子树
if (data.first > cur->_data.first)
{
cur = cur->_right;
}
//比根节点小则查找左子树
else if (data.first < cur->_data.first)
{
cur = cur->_left;
}
//相同则返回
else
{
return true;
}
}
//遍历完则说明查找不到，返回false
return false;
}
红黑树的验证:
- 根节点必须为黑节点
- 不存在连续的红节点
- 从某一节点出发到其所有的叶子节点,其中经过的黑色节点数量相等
bool IsRBTree(){
if (_root == nullptr){
//空树也是红黑树
return true;
}
//违反性质1
if (_root->_color != BLACK){
return false;
}
//获取从根节点出发的任意一条子路径的黑色节点数，这里选取最左子树。
Node* cur = _root;
size_t blackCount = 0;
size_t count = 0;
while (cur){
if (cur->_color == BLACK){
blackCount++;
}
cur = cur->_left;
}
//递归判断其他路径的黑色节点数
return _IsRBTree(_root, count, blackCount);
}
bool _IsRBTree(Node* root, size_t count, const size_t blackCount){
//此时说明已经走到叶子节点，判断黑色节点数是否相等，不相等则违反性质3
if (root == nullptr){
if (count != blackCount){
return false;
}
else{
return true;
}
}
//如果没走完，就接着判断其他情况
//判断性质2，如果存在连续的红结点，则返回错误
Node* parent = root->_parent;
if (parent && root->_color == RED && parent->_color == RED){
return false;
}
//如果当前节点为黑色，则记录
if (root->_color == BLACK){
count++;
}
//接着递归判断当前节点的所有路径
return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);
}完整代码:
#include<iostream>
using namespace std;
enum Color
{
BLACK,
RED,
};
template<class K, class V>
struct RBTreeNode
{
typedef RBTreeNode<K, V> Node;
RBTreeNode(const std::pair<K, V>& data = std::pair<K, V>(), const Color& color = RED)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _color(color)
{}
Node* _left;
Node* _right;
Node* _parent;
std::pair<K, V> _data;
Color _color;
};
template<class K, class V>
class RBTree
{
public:
typedef RBTreeNode<K, V> Node;
RBTree()
: _root(nullptr)
{}
~RBTree()
{
destory(_root);
}
void _InOrderTravel(Node* root) const
{
if (root == nullptr)
return;
_InOrderTravel(root->_left);
std::cout << root->_data.first << ':' << root->_data.second << std::endl;
_InOrderTravel(root->_right);
}
void InOrderTravel() const
{
_InOrderTravel(_root);
}
void destory(Node*& root)
{
Node* node = root;
if (!root)
return;
destory(node->_left);
destory(node->_right);
delete node;
node = nullptr;
}
//右旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
//如果subLR存在，则让他的父节点指向parent。
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
//两种情况
//如果parent为根节点，则让subL成为新的根节点
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
//如果不是根节点，则改变subL与其祖父节点的指向关系
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
//左旋
void RotateL(Node* parent)
{
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;
}
}
bool Find(const std::pair<K, V>& data)
{
//根据二叉搜索树的性质，从根节点出发，比根节点大则查找右子树，比根节点小则查找左子树
Node* cur = _root;
while (cur)
{
//比根节点大则查找右子树
if (data.first > cur->_data.first)
{
cur = cur->_right;
}
//比根节点小则查找左子树
else if (data.first < cur->_data.first)
{
cur = cur->_left;
}
//相同则返回
else
{
return true;
}
}
//遍历完则说明查找不到，返回false
return false;
}
bool Insert(const std::pair<K, V>& data)
{
//按照二叉搜索树的规则先找到位置
//创建根节点
if (_root == nullptr)
{
_root = new Node(data, BLACK);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (data.first > cur->_data.first)
{
parent = cur;
cur = cur->_right;
}
else if (data.first < cur->_data.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//新插入节点为红色
cur = new Node(data, RED);
//保存插入的结点，因为后面会往上更新红黑树，所以cur可能会变化。
Node* newNode = cur;
//判断插入位置
if (cur->_data.first > parent->_data.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新红黑树，如果父节点的颜色为黑，则说明满足条件，不需要处理，如果为红，则说明不满足，需要处理。
while (parent && parent->_color == RED)
{
Node* ppNode = parent->_parent;
//如果父节点为祖父的左子树
if (ppNode->_left == parent)
{
//此时判断叔叔节点的状态，红黑树状态取决于叔叔
Node* uncle = ppNode->_right;
//第一种情况，如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整
if (uncle && uncle->_color == RED)
{
//变色
uncle->_color = parent->_color = BLACK;
ppNode->_color = RED;
//继续往上
cur = ppNode;
parent = cur->_parent;
}
/*
叔叔节点为黑或者不存在，此时有两种情况
情况二：cur为父节点的左子树，即直线状态。
情况三：cur为父节点的右子树，即折线状态。
情况二单旋一次后更改颜色即可完成
对于情况三，如果将其进行一次旋转后再稍微处理，就可以转换成情况二
*/
else
{
//因为这里的双旋和AVL不一样，可以不用处理平衡因子，所以如果为折线则先旋转处理后，将其转换为直线处理即可。
//第三种情况，折线状态，转换为直线状态处理
if (parent->_right == cur)
{
RotateL(parent);
//单旋后再交换节点，即可变成直线状态。
std::swap(parent, cur);
}
//处理第二种状态
RotateR(ppNode);
parent->_color = BLACK;
ppNode->_color = RED;
//处理完成
break;
}
}
//如果父亲为祖父的右子树
else
{
//此时叔叔为左子树。
Node* uncle = ppNode->_left;
if (uncle && uncle->_color == RED)
{
uncle->_color = parent->_color = BLACK;
ppNode->_color = RED;
cur = ppNode;
parent = cur->_parent;
}
else
{
if (parent->_left == cur)
{
RotateR(parent);
std::swap(cur, parent);
}
RotateL(ppNode);
ppNode->_color = RED;
parent->_color = BLACK;
break;
}
}
}
//为了防止不小心把根节点改为红色，最后手动改为黑色即可
_root->_color = BLACK;
return true;
}