红黑树算法及代码（C++版）

红黑树的定义

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形式自己写了一遍）

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。