红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是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();
}运行程序：
《完》
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
