红黑树是近似平衡的二叉搜索树。
红黑树的性质:
1,每个节点不是红色就是黑色
2,根节点必须是黑色
3,没有连续的红节点
4,每条路径上黑色节点数目相等
红黑树保证最长路径不超过最短路径的两倍。那么,为什么满足以上这些条件就能保证呢?
最短路径一定是节点全黑,要保证每条路径的黑节点数量相等,只能在两个黑节点之间添加红节点,所以最长路径不会超过最短路径的两倍。
红黑树保证效率为log2^N
如上图所示是一棵简单的红黑树,红黑树的插入要通过旋转和变色来调节平衡。
当parent是grandfather的左孩子,uncle是grandfather的右孩子时,插入可分为以下情况:
1,叔叔节点存在且为红色
Node* grandfther = parent->_parent;
if (parent == grandfther->_left)
{
Node* uncle = grandfther->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfther->_col = RED;
cur = grandfther;
parent = cur->_parent;
}
2,叔叔节点不存在或存在且为黑
将parent变黑,grandfather变红,进行右单旋
else // u 不存在 u黑
{
if(cur == parent->_right) // 双旋
{
RotateL(parent);
swap(cur,parent);
}
RotateR(grandfther);
parent->_col = BLACK;
grandfther->_col = RED;
break;
}
3,cur是parent的右孩子,需要双旋
当parent是grandfather的右时,需要分析的情况还是以上三种,只是方向相反而已。
完整代码:
#pragma once
#include<iostream>
using namespace std;
enum Colour
{
RED,BLACK,};
template<class K,class V>
struct RBTreeNode
{
K _key;
K _value;
RBTreeNode<K,V>* _left;
RBTreeNode<K,V>* _right;
RBTreeNode<K,V>* _parent;
Colour _col;
RBTreeNode(const K& key,const V& value)
:_key(key),_value(value),_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(const RBTree<K,V>& tree)
{
_Copy(tree._root);
}
~RBTree()
{
_Destroy(_root);
}
RBTree<K,V>& operator = (const RBTree<K,V>& tree)
{
RBTree<K,V> tmp(tree);
swap(_root,tree._root);
return *this;
}
bool Insert(const K& key,const V& value)
{
if (_root == NULL)
{
_root = new Node(key,value);
_root->_col = BLACK;
return true;
}
Node* parent = NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key,value);
if (parent->_key < key)
{
parent->_right = cur;
cur->_parent = parent;
}
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 && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // u 不存在 u黑
{
if (cur == parent->_right) // 双旋
{
RotateL(parent);
swap(cur,parent);
}
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
}
//parent = grandfather->right
else if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateR(parent);
swap(parent,cur);
}
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
}
bool IsBalance()
{
Node* cur = _root;
if (_root == NULL)
{
return true;
}
//根节点是黑色
if (_root->_col == RED)
{
return false;
}
int BlackNode = 0;
//统计最左路径上黑色节点的数量
while (cur)
{
if (cur->_col == BLACK)
{
++BlackNode;
}
cur = cur->_left;
}
//一条路径上黑色节点的数量
int num = 0;
return _IsBlance(_root,BlackNode,num);
}
protected:
void _Copy(Node* root)
{
Node* newNode = NULL;
Node* cur = root;
while (cur)
{
newNode = new Node(cur->_key,cur->_value);
newNode->_left = _Copy(cur->_left);
newNode->_right = _Copy(cur->_right);
}
}
void _Destroy(Node* root)
{
Node* cur = root;
if (root == NULL)
return;
_Destroy(cur->_left);
_Destroy(cur->_right);
delete cur;
cur = NULL;
}
bool _IsBlance(Node* root,const int BlackNode,int num)
{
//一条路径已经走完
if (root == NULL)
{
if (num != BlackNode)
{
cout << "黑色节点数量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++num;
}
if((root->_col == RED) && (root->_parent) && (root->_parent->_col == RED))
{
cout << "有连续的红节点" << root->_key << endl;
return false;
}
return _IsBlance(root->_left,num)
&& _IsBlance(root->_right,num);
}
//右旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (ppNode == NULL)
{
_root = subL;
subL->_parent = NULL;
}
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 (ppNode == NULL)
{
_root = subR;
subR->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void _InOrder(Node* root)
{
Node* cur = root;
if (cur == NULL)
return;
_InOrder(cur->_left);
cout << cur->_key << " ";
_InOrder(cur->_right);
}
private:
Node* _root;
};
void TestRBTree()
{
RBTree<int,int> t;
int a[] = { 16,3,7,11,9,26,18,14,15 }; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { t.Insert(a[i],i); } t.InOrder(); cout << endl; cout << "IsBalance?" << t.IsBalance() << endl; }
我们知道,红黑树是近似平衡的二叉树,那么为什么不直接使用平衡二叉树呢?
原因是红黑树最坏的情况也是log2^N,但它不像平衡二叉树需要严格控制平衡因子,红黑树只需控制节点的颜色,因此它的旋转次数相对于平衡二叉树能少一些,因此,实际中,红黑树的应用更为广泛。
红黑树的应用: 1. C++ STL库 – map 2. Java 库 3. linux内核 4. 其他一些库