红黑树：首先是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似于平衡。
网站的建设成都创新互联公司专注网站定制,经验丰富,不做模板,主营网站定制开发.小程序定制开发,H5页面制作!给你焕然一新的设计体验!已为成都餐厅设计等企业提供专业服务。
红黑树满足的性质：
根节点是黑色的
如果一个节点是红色的，则它的两个子节点是黑色的(没有连续的红节点)
每条路径的黑色节点的数量相等
红黑树保证最长路径不超过最短路径的两倍，如下图所示
插入节点时的三种情况
cur为红，p为红，g为黑，u存在且为红
cur为红，p为红，g为黑，u不存在/u为黑，p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红
cur为红，p为红，g为黑，u不存在/u为黑，p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
#pragma once
#include
using namespace std;
enum Color
{
RED,
BALCK
};
template
struct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
K _key;
V _value;
Color _col;
RBTreeNode(const K& key, const V& value)
:_left(NULL)
, _right(NULL)
, _parent(NULL)
, _key(key)
, _value(value)
, _col(RED)
{}
};
template
class RBTree
{
typedef RBTreeNode Node;
public:
RBTree()
:_root(NULL)
{}
Node* Find(const K& key)
{
if (_root == NULL)
return NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key == key)
return cur;
else if (cur->_key < key)
cur = cur->_right;
else
cur = cur->_left;
}
return NULL;
}
bool Insert(const K& key, const V& value)
{
if (_root == NULL)
{
_root = new Node(key, value);
_root->_col = BALCK;
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
{
cout << "该节点已存在" << endl;
return false;
}
}
cur = new Node(key, value);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//调整节点颜色
while (cur != _root&&parent->_col == RED)
{//规定根节点必须为黑色，若parent的颜色为红色，则它一定不为根节点，它的父节点也一定存在
Node* ppNode = parent->_parent;//不用判空
Node* uncle = NULL;
if (parent == ppNode->_left)
{//parent为它的父节点的左孩子，则叔节点若存在，肯定在右边
uncle = ppNode->_right;
if (uncle&&uncle->_col == RED)
{//1.cur为红，parent为红，ppNode为黑，u存在且为红
parent->_col = uncle->_col = BALCK;
ppNode->_col = RED;
cur = ppNode;
ppNode = cur->_parent;
}
else
{//2.cur为红，parent为红，uncle不存在或者为黑
if (cur == parent->_right)
{
RotateL(parent);
swap(cur, parent);
}
parent->_col = BALCK;
ppNode->_col = RED;
RotateR(ppNode);
}
}
else
{//另一边
uncle = ppNode->_left;
if (uncle&&uncle->_col == RED)
{//1.cur为红，parent为红，ppNode为黑，u存在且为红
parent->_col = uncle->_col = BALCK;
ppNode->_col = RED;
cur = ppNode;
ppNode = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(parent);
swap(cur, parent);
}
parent->_col = BALCK;
ppNode->_col = RED;
RotateL(ppNode);
}
}
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
if (parent == _root || ppNode == NULL)//若要调整的节点为根节点
{
_root = subL;
subL->_parent = NULL;
}
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;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* ppNode = parent->_parent;
subR->_left = parent;
if (parent == _root || ppNode == NULL)//若要调整的节点为根节点
{
_root = subR;
subR->_parent = NULL;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
bool IsBalance()
{
int BlackNodeCount = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BALCK)
{
BlackNodeCount++;
}
cur = cur->_left;
}
int count = 0;
return _IsBalance(_root, BlackNodeCount, count);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
~RBTree()
{}
protected:
bool _IsBalance(Node* root, const int BlackNodeCount, int count)
{
if (root == NULL)
return false;
if (root->_parent)
{
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "不能有两个连续的红节点" << endl;
return false;
}
}
if (root->_col == BALCK)
++count;
if (root->_left == NULL&&root->_right == NULL&&count != BlackNodeCount)
{
cout << "该条路径上黑色节点数目与其它不相等" << endl;
return false;
}
return _IsBalance(root->_left, BlackNodeCount,count) &&
_IsBalance(root->_right, BlackNodeCount,count);
}
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
protected:
Node* _root;
};
void Test()
{
RBTree bt;
int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
bt.Insert(arr[i], i);
}
bt.IsBalance();
bt.InOrder();
cout << bt.Find(6) << endl;;
cout<红黑树与AVL树的异同：
红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(lg(N))
红黑树的不追求完全平衡，保证最长路径不超过最短路径的2倍，相对而言，降低了旋转的要求，所以性能跟AVL树差不多，但是红黑树实现更简单，所以实际运用中红黑树更多。
红黑树的应用：
STL库中的map、set
多路复用epoll模式在linux内核的实现
JAVA的TreeMap实现
本文名称：红黑树的插入及查找
文章URL：http://cdkjz.cn/article/jhihid.html
