目录
认识红黑树:
红黑树的平衡调节:
情况一:
情况二:
情况三:
代码:
红黑树和AVL树一样,也是一种平衡二叉树,在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确没有一条路径会比其他路径长出俩倍,因而是接近平衡的。虽然它的平衡性没有AVL树那么好,但实际上效率几乎一样,而且它比AVL树更好控制。对于红黑树的规则如下:
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的,则它的两个孩子结点是黑色的 4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
只需满足以上特性,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍。 下图,就是红黑树:
认识了红黑树,它到底是如何进行平衡调节的呢?先列举它需要调节平衡的时候,大致可分为两类,先约定,cur为当前节点,p为父节点,g为祖先节点,u为叔叔节点。
叔叔存在且为红色:
这种时候p节点已经不满足特性2了,我们需要调整,方法:p,u改为黑,g改为红,注意如果g是根节点就再改为黑:
只需简单改色,就可让这颗树重新满足红黑树特性。
注意,到这里还没有结束,因为这颗树可能是别人的子树,改色后,可能出现下图的情况 :
祖先节点的父节点,可能是红的,这样最后就两个红色在一起了,我们需要将cur=g,p=g->parent,继续向上更新,直到父节点为黑色或者空(父节点为空时就是根节点)
cur为红,p为红,g为黑,u不存在/u存在且为黑:
说明:u的情况有两种 1.如果u节点不存在,则cur一定是新插入节点,因为如果cur不是新插入节点 则cur和p一定有一个节点的颜色是黑色,就不满足性质4:每条路径黑色节点个 数相同。 2.如果u节点存在,则其一定是黑色的,那么cur节点原来的颜色一定是黑色的 现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由 黑色改成红色。
这两种情况都可以用一种方法处理: p变黑,g变红,然后以g为旋转点,进行右单旋(旋转相关的知识可以看我上一篇博客)
情况三和情况二只有一个区别就是,cur为情况二图中p的右子树,其余条件完全相同:
调整方法: 先以p为旋转点进行左旋后,可以发现已经和情况二一样了,不过这时的p和cur和情况二中的p和cur是反过来的(旋转造成的),我们再交换p和cur就和情况二一样了(不交换也可以变色时让cur变色),然后再按情况二的调整方法,先p变黑,g变红,以g为旋转点右旋。
特别注意:上图列出的三种情况,都是叔叔节点在祖先节点右边的情况,实际还需考虑叔叔节点在祖先节点左边的情况,两种情况方法原理完全相同,只需颠倒一下,左旋变右旋,右旋变左旋。
#pragma once
#include<string>
enum colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTNode
{
AVLNode<K, V>* _left;//左子树
AVLNode<K, V>* _right;//右子树
AVLNode<K, V>* _parent;//父节点
pair<K, V> _kv;
colour _clo;
RBNode(const pair<K, V>& kv)//构造函数
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
,_clo(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBNode<K, V> node;
public:
bool insert(const pair<K,V>& kv)
{
if (_root == nullptr)//若原来树为空
{
_root = new node(kv);
_root->_col = RED;
return true;
}
node* cur = _root;
node* parent = nullptr;
while (cur)//开始找插入位置
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = parent->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = parent->_right;
}
else
{
return false;
}
}
cur = new node(kv);
cur->col = RED;
if (kv.first > parent->_kv.first)//调整父节点
{
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;
if (uncle->_col == RED)//若叔叔为红,p,u改黑,g改红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
if (grandfather == _root)//g为根,再次变黑
{
grandfather->_col = BLACK;
}
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
else//若叔叔不存在或者为黑
{
if (cur == parent->_left)
{
// g
// p u
// c
//g变红,p变黑,右旋
grandfather->_col = RED;
parent->_col = BLACK;
RotateR(grandfather);
}
else
{
// g
// p u
// c
//g变红,c变黑,先以p左旋,再以g右旋
grandfather->_col = RED;
cur->_col = BLACK;
RotateL(parent);
RotateR(grandfather);
}
break;//这种情况无需再向上更新
}
}
else//父在爷爷的右
{
node* uncle = grandfather->left;
if (uncle->_col == RED)//若叔叔为红,p,u改黑,g改红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
if (grandfather == _root)//g为根,再次变黑
{
grandfather->_col = BLACK;
}
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
else//若叔叔不存在或者为黑
{
if (cur == parent->_left)
{
// g
// u p
// c
//g变红,c变黑,先以p右旋,再以g左旋
grandfather->_col = RED;
cur->_col = BLACK;
RotateR(parent);
RotateL(grandfather);
}
else
{
// g
// u p
// c
//g变红,p变黑,左旋
grandfather->_col = RED;
parent->_col = BLACK;
RotateL(grandfather);
}
break;//这种情况无需再向上更新
}
}
}
}
void RotateR(node* parent)
{
//调节节点
node* subL = parent->_left;
node* subLR = subL->_right;
node* ppnode = parent->_parent;
parent->_left = subLR;
if (subLR)//防止为空
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
//调节父节点的指向
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
node* ppnode = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
parent->_parent = subR;
subR->_right = parent;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
private:
node* _root;
};