红黑树的定义
1.节点非黑即红。
2.根节点为黑。
3.红色节点不连续。(插入时，做判定）
4.完美黑色平衡：根节点到NULL节点，经过黑色节点数目相同。
数据结构
节点结构
struct RedBlackNode{
int _key;
int _value;
RedBlackNode *_left = NULL;
RedBlackNode *_right = NULL;
RedBlackNode *_parent = NULL;
Color color = RED;
};
建立这棵树的规则
判定不符合性质3
满足while则不符合性质3
while(parent && parent->color == RED)
1.变色（uncle红，parent红）
parent、uncle-->黑
grandParent-->红
下一个可能出现不符合规则的，为grandParent节点，下次判定cur=grandParent，parent = grandParent->parent
PS：通过变色，当出现parent为根节点时，满足性质3，退出判定。
2.旋转（uncle黑，parent红）
parent-->黑
grandParent-->红 （经过旋转后，parent成为grandparent，grandparent成为parent）
| 类型 | 旋转情况 |
|---|---|
| LL | 右旋 |
| LR | 左旋后右旋 |
| RR | 左旋 |
| RL | 右旋后左旋 |
PS：
1.LR的本质是转换成LL。所以变色在左旋后。（RL同理）
2.旋转必结束判定
检查这棵树是否满足要求
检查条件：红黑树每条路径上黑色节点数量相同
外封装：
bool RBTree::Check(){
int blackNum = 0;
RBTreeNode *cur = _root;
while(cur){
if(cur->_color == BLACK)
blackNum++;
cur = cur->_left;//任意方向
}
int CBNum = 0;//count Black number
return _Check(_root, blackNum, CBNum);
}
检查黑色节点是否满足要求
bool RBTree::_Check(RBTreeNode *root, int blackNum, int CBNum)
{
if(root == NULL)
return true;
if(root->_color == BLACK)
{
CBNum++;
if(root->_left == NULL && root->_right == NULL){
return true;
}
else{
cout << "叶子节点为" << root->_key << "路径的黑色节点数目与最左侧支路的黑色节点数目不相等！" << endl;
return false;
}
}else if(root->_parent && root->_parent->_color == RED){
//判断是否存在连续的两个红色节点
cout << root->_parent->_key << " 和 " << root->_key << "为两个连续的红色节点" << endl;
return false;
}
return _Check(root->_left, blackNum, CBNum) && _Check(root->_right, blackNum, CBNum);
}
#include <iostream>
#include <cmath>
#include <vector>
#include <random>
using namespace std;
/*请在这里输入这个程序的功能或者作用*/
enum Color{RED, BLACK};
struct RedBlackNode{
int _key;
int _value;
RedBlackNode *_left = NULL;
RedBlackNode *_right = NULL;
RedBlackNode *_parent = NULL;
Color color = RED;
};
class RedBlackTree{
public:
RedBlackTree():
_root(NULL)
{}
void RotateL(RedBlackNode *&node){
RedBlackNode *parent = node->_parent;
RedBlackNode *subR = node->_right;
RedBlackNode *subRL = subR->_left;
//需要变动的是 node， subR， subRL， parent
node->_parent = subR;
node->_right = subRL;
subR->_parent = parent;
subR->_left = node;
if(subRL)subRL->_parent = node;
if(parent==NULL){
_root = subR;
}
else{
if(parent->_left == node){
parent->_left = subR;
}else if(parent->_right == node){
parent->_right = subR;
}
}
//根节点换人
node = subR;
}
void RotateR(RedBlackNode *&node){
RedBlackNode *parent = node->_parent;
RedBlackNode *subL = node->_left;
RedBlackNode *subLR = subL->_right;
//node, subL, subLR, parent
node->_left = subLR;
node->_parent = subL;
subL->_parent = parent;
subL->_right = node;
if(subLR)subLR->_parent = node;
if(parent == NULL){
_root = subL;
}else{
if(parent->_left == node){
parent->_left = subL;
}else if(parent->_right == node){
parent->_right = subL;
}
}
node = subL;
}
RedBlackNode* CreateNode(int key, int value){
RedBlackNode *temp = new RedBlackNode;
temp->_key = key; temp->_value = value;
return temp;
}
bool Insert(int key, int value){
if(_root == NULL){
_root = CreateNode(key, value);
_root->color = BLACK;
return true;
}
RedBlackNode *cur = _root, *parent = NULL;
while(cur){
parent = cur;
if(key < cur->_key){
cur = cur->_left;
}else if(key > cur->_key){
cur = cur->_right;
}else return false;
}
cur = CreateNode(key, value);
if(key < parent->_key){
parent->_left = cur;
}else if(key > parent->_key){
parent->_right = cur;
}
cur->_parent = parent;
while(parent && parent->color == RED){
RedBlackNode* grandParent = parent->_parent;
if(parent == grandParent->_left){
RedBlackNode *uncle = grandParent->_right;
if(uncle && uncle->color == RED){
grandParent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
cur = grandParent;
parent = cur->_parent;
}else if((uncle && uncle->color == BLACK) || uncle == NULL){
if(cur == parent->_left){
parent->color = BLACK;
grandParent->color = RED;
RotateR(grandParent);
}else if(cur == parent->_right){
RotateL(parent);
parent->color = BLACK;
grandParent->color = RED;
RotateR(grandParent);
}
break;
}
}else if(parent == grandParent->_right){
RedBlackNode *uncle = grandParent->_left;
if(uncle && uncle->color == RED){
grandParent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
cur = grandParent;
parent = cur->_parent;
}else if((uncle && uncle->color == BLACK) || uncle == NULL){
if(cur == parent->_right){
parent->color = BLACK;
grandParent->color = RED;
RotateL(grandParent);
}else if(cur == parent->_left){
RotateR(parent);
parent->color = BLACK;
grandParent->color = RED;
RotateL(grandParent);
}
break;
}
}
}
_root->color = BLACK;
return true;
}
void InOrder(){
if(_root == NULL){
cout << "No";
return;
}
_InOrder(_root);
}
void _InOrder(RedBlackNode *a){
if(a==NULL)return;
_InOrder(a->_left);
string str_color = a->color==RED ? "RED": "BLACK";
cout << "key:"<< a->_key << "value:" << a->_value << " Color:" << str_color;
if(a->_parent) cout << "parent_key:" << a->_parent->_key;
cout << endl;
_InOrder(a->_right);
return;
}
bool Check(){
int blackNum = 0;
RedBlackNode *cur = _root;
while(cur){
if(cur->color == BLACK)
blackNum++;
cur = cur->_left;//任意方向
}
int CBNum = 0;//count Black number
return _Check(_root, blackNum, CBNum);
}
bool _Check(RedBlackNode *root, int blackNum, int CBNum)
{
if(root == NULL)
return true;
if(root->color == BLACK)
{
CBNum++;
if(root->_left == NULL && root->_right == NULL){
if(blackNum == CBNum)
return true;
else{
cout << "叶子节点为" << root->_key << "路径的黑色节点数目与最左侧支路的黑色节点数目不相等！" << endl;
return false;
}
}
}else if(root->_parent && root->_parent->color == RED){
//判断是否存在连续的两个红色节点
cout << root->_parent->_key << " 和 " << root->_key << "为两个连续的红色节点" << endl;
return false;
}
return _Check(root->_left, blackNum, CBNum) && _Check(root->_right, blackNum, CBNum);
}
private:
RedBlackNode* _root;
};
int main()
{
RedBlackTree tree;
vector<int> nums = {16,3,7,11,9,26,18,14,15,20,100,0,1,2,5};
for(int i=0; i<nums.size(); i++){
tree.Insert(nums[i], i);
}
tree.InOrder();
cout << "check:" << tree.Check();
return 0;
}
参考资料
红黑树知识：脑子里（忘记哪里学的了）
红黑树代码参考(该代码使用了模板，我用了int形式自己写了一遍）
网友评论