红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是red或black。通过对任何一条从根到叶子简单路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,因而近似于平衡。
红黑树是满足下面红黑性质的二叉搜索树:
每个节点,不是红色就是黑色的
根节点是黑色的
如果一个节点是红色的,则它的两个子节点是黑色的(没有连续的红节点)
对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。(每条路径的黑色节点的数量相等)
这里分析一下为什么红黑树能保证最长路径不超过最短路径的两倍:首先因为第4条约束条件假设一棵树如下所示:
B
B B
B B B表示为黑色结点,那么要在其中插入任何一个黑色结点就需要保证第4条约定,而如果要插入红色结点,则第3条约束又使得红色结点只能插在黑色结点之间,因此一条路径最多变成:
B
B R
B B
R
B 因此,最长路径不超过最短路径的两倍,也就保证了搜索的效率;
下面是实现红黑树的插入过程:
#pragma once
#include <iostream>
using namespace std;
//结点的颜色 红or黑
enum Color
{
RED,
BLACK
};
//结点结构体
template <class K, class V>
struct RBTreeNode
{
K _key;
V _val;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
RBTreeNode(const K& key, const V& val)
:_key(key)
,_val(val)
,_left(NULL)
,_right(NULL)
,_parent(NULL)
,_col(RED)
{}
};
//红黑树类
template <class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree()
:_root(NULL)
{}
~RBTree()
{
_Clear(_root);
}
//插入结点
bool Insert(const K& key, const V& val)
{
if(_root == NULL)//如果根结点为NULL,创建新的结点为根结点返回true
{
_root = new Node(key, val);
_root->_col = BLACK;
return true;
}
//如果根结点不为NULL,则遍历树直到找到合适的插入位置
Node* cur = _root;
Node* prev = cur;
while(cur != NULL)
{
if(cur->_key == key)//如果树中已经有该结点,则返回false
return false;
else if(cur->_key > key)//如果关键值小于结点的关键值,则去左子树找
{
prev = cur;
cur = cur->_left;
}
else//否则关键值大于结点的关键值,去右子树找
{
prev = cur;
cur = cur->_right;
}
}
//循环结束,找到了合适的插入位置,判断应该插入到结点的左边还是右边
Node* tmp = new Node(key, val);
if(prev->_key > key)
prev->_left = tmp;
else
prev->_right = tmp;
tmp->_parent = prev;
//插入结点之后,就要开始判断目前的树是否符合红黑树的性质
while((tmp != _root) && (prev->_col == RED))
{
Node* grandfather = prev->_parent;//提取出tmp的祖父结点
if(grandfather->_left == prev)//如果prev是grandfather的左结点
{
//第一种情况
//tmp为红,prev为红,grandfather为黑,uncle存在且为红
//则将prev,uncle改为黑,grandfather改为红,然后把grandfather当成tmp,继续向上调整。
Node* uncle = grandfather->_right;
if(uncle != NULL && uncle->_col == RED)
{
prev->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
tmp = grandfather;
prev = tmp->_parent;
}
else//第二种情况:tmp为红,prev为红,grandfather为黑,uncle不存在/uncle为黑
//prev为grandfather的左孩子,tmp为prev的左孩子,则进行右单旋转;
//prev、grandfather变色--prev变黑,grandfather变红
{
//第三种情况
//tmp为红,prev为红,grandfather为黑,uncle不存在/uncle为黑
//prev为grandfather的左孩子,tmp为prev的右孩子,则针对prev做左单旋转;
//则转换成了情况二
if(prev->_right == tmp)
{
_RotateL(prev);
swap(tmp, prev);
}
_RotateR(grandfather);//进行右单旋
prev->_col = BLACK;
grandfather->_col = RED;
break;
}
}
else//当perv是grandfather的右结点的时候,和上面的情况相反
{
//第一种情况
//tmp为红,prev为红,grandfather为黑,uncle存在且为红
//则将prev,uncle改为黑,grandfather改为红,然后把grandfather当成tmp,继续向上调整。
Node* uncle = grandfather->_left;
if(uncle != NULL && uncle->_col == RED)
{
prev->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
tmp = grandfather;
prev = tmp->_parent;
}
else//第二种情况:tmp为红,prev为红,grandfather为黑,uncle不存在/uncle为黑
//prev为grandfather的右孩子,tmp为prev的右孩子,则进行左单旋转
//prev、grandfather变色--prev变黑,grandfather变红
{
//第三种情况
//tmp为红,prev为红,grandfather为黑,uncle不存在/uncle为黑
//prev为grandfather的右孩子,tmp为prev的左孩子,则针对prev做右单旋转
//则转换成了情况二
if(prev->_left == tmp)
{
_RotateR(prev);
swap(tmp, prev);
}
_RotateL(grandfather);//进行右单旋
prev->_col = BLACK;
grandfather->_col = RED;
break;
}
}
}
//如果根结点被调整成了红色,将其改为黑色,并会不影响左右黑结点的个数
if(_root->_col == RED)
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
/*bool Find(const K& key)
{
}*/
private:
void _Clear(Node* root)
{
if(root == NULL)
return;
_Clear(root->_left);
_Clear(root->_right);
delete root;
root = NULL;
}
void _RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL != NULL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == NULL)
_root = subR;
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
void _RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR != NULL)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppNode == NULL)
_root = subL;
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
void _InOrder(Node* root)
{
if(root != NULL)
{
_InOrder(root->_left);
cout<<root->_key<<" ";
_InOrder(root->_right);
}
}
private:
Node* _root;
};
void Test()
{
int arr[] = {3, 4, 6, 1, 7, 2, 8};
RBTree<int, int> t;
for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
t.Insert(arr[i], i);
t.InOrder();
}
运行程序:
《完》
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。