前言：

AVL树是二叉平衡搜索树，红黑树是基于AVL树的改造，是基于旋转的次数的减少。

红黑树简介

红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树操作

红黑树是一种自平衡的二叉搜索树，它通过在每个节点上添加颜色属性（红色或黑色）并遵循特定的规则来保持树的平衡，从而保证了插入、删除和查找操作的对数时间复杂度。

在C++中实现红黑树通常涉及以下步骤：

1. 定义节点结构，包含数据、颜色、左右子节点指针等。
2. 实现红黑树的基本操作，如插入、删除、左旋、右旋、颜色翻转等。
3. 维护红黑树的性质，确保在每次插入或删除后通过一系列旋转和颜色调整操作来恢复平衡。

红黑树的实现

存储结构

• 整体的存贮结构类似于AVL树，AVL实现平衡的需要平衡因子_bf
• 红黑树的节点定义不是红色节点就是黑色节点，根据颜色的区分并且保证红红黑树的性质。

enum Colour
{
   
    RED,
    BLACK
};
template<class K, class V>
    class RBTreeNode
    {
   
        public:
        RBTreeNode<K, V>* _left;
        RBTreeNode<K, V>* _right;
        RBTreeNode<K, V>* _parent;
        pair<K, V> _kv;
        Colour _col;

        RBTreeNode(const pair<K, V>& kv)
            :_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv)
            {
   }
    };

红黑树的插入

• 插入新节点：首先，按照二叉搜索树的规则找到插入位置，并将新节点插入为红色。这是因为在红黑树中，新插入的节点总是被染成红色，以避免立即破坏树的平衡性。
• 颜色调整：插入红色节点后，可能会违反红黑树的性质。特别是，如果新节点的父节点是红色，那么可能会出现两个连续的红色节点，违反了性质4（父节点和子节点不能同时为红色）。在这种情况下，需要进行颜色调整和可能的树旋转操作来恢复红黑性质。
• 旋转操作：根据新节点的位置（是左子树还是右子树）以及叔叔节点的颜色，可能需要执行左旋或右旋操作。旋转操作可以重新分配节点的颜色和子节点关系，以帮助恢复红黑树的平衡。
• 迭代调整：在某些情况下，可能需要向上迭代，对祖父节点甚至更高层的节点进行调整，以确保整个树的红黑性质得到满足。
• 特殊情况处理：如果新节点成为根节点，或者在调整过程中发现根节点变为红色，需要将根节点染成黑色，以满足性质2（根节点是黑色的）

bool insert(const pair<K, V>& kv)
{
   
    if (_root == nullptr)
    {
   
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
   
        if (kv.first > cur->_kv.first)
        {
   
            parent = cur;
            cur = cur->_right;
        }
        else if (kv.first < cur->_kv.first)
        {
   
            parent = cur;
            cur = cur->_left;
        }
        else
        {
   
            return false;
        }
    }

    cur = new Node(kv);
    cur->_col = RED;

    if (kv.first < parent->_kv.first)
    {
   
        parent->_left = cur;
    }
    else
    {
   
        parent->_right = cur;
    }
    cur->_parent = parent;、
    //调账
  ...
}

调整（旋转）

• 红黑树的底层类似于AVL，仅仅是旋转次数变少，但是时间复杂度依旧是O（lgN）

左旋

void RotateL(Node* parent)
{
   

    Node* cur = parent->_right;

    Node* curleft = cur->_left;

    parent->_right = curleft;

    if (curleft)
    {
   
        curleft->_parent = parent;
    }

    cur->_left = parent;

    Node* ppnode = parent->_parent;

    parent->_parent = cur;

    if (parent == _root)
    {
   
        _root = cur;
        cur->_parent = nullptr;
    }
    else
    {
   
        if (ppnode->_left == parent)
        {
   
            ppnode->_left = cur;
        }
        else
        {
   
            ppnode->_right = cur;
        }

        cur->_parent = ppnode;
    }
}

右旋

void RotateR(Node* parent)
{
   
    Node* cur = parent->_left;
    Node* curright = cur->_right;

    parent->_left = curright;

    if (curright)
    {
   
        curright->_parent = parent;
    }

    cur->_right = parent;

    Node* ppnode = parent->_parent;

    parent->_parent = cur;

    if (ppnode == nullptr)
    {
   
        _root = cur;
        cur->_parent = nullptr;
    }
    else
    {
   
        if (ppnode->_left == parent)
        {
   
            ppnode->_left = cur;
        }
        else
        {
   
            ppnode->_right = cur;
        }

        cur->_parent = ppnode;
    }

}

导致红黑树的不平衡原因

• 红黑树不可以连续个连续的节点是红色
• 保证每一个路径黑色节点数目是一样的（根据这个条件，我们要插入红色节点）

情况一

• u节点存在，并且是红色

情况二

• u节点不存在或者u节点为黑色

如何保证红黑树平衡

• 我们需要寻找parent的节点的兄弟节点定义为uncle，进行判断，空，黑，红。
• 如果是红色节点，将parent和uncle节点的颜色转换为黑色，继续向上调整

• 如果节点不存在或者为黑的情况下，进行旋转，调整节点颜色。

  while (parent && parent->_col == RED)
  {
       
     Node* grandparent = parent->_parent;
     if (parent == grandparent->_left)
     {
       
         Node* uncle = grandparent->_right;
         if (uncle && uncle->_col == RED)
         {
       
             parent->_col = uncle->_col = BLACK;
             grandparent->_col = RED;
             cur = grandparent;
             parent = cur->_parent;
         }
         else//uncle is not or black
         {
       
             if (cur == parent->_left)
             {
       
                 RotateR(grandparent);
                 grandparent->_col = RED;
                 parent->_col = BLACK;
             }
             else
             {
       
                 RotateL(parent);
                 RotateR(grandparent);
                 grandparent->_col = RED;
                 cur->_col = BLACK;
             }
             break;
         }
     }
     else//parent == grandparent->_right
     {
       
         Node* uncle = grandparent->_left;
  
         if (uncle && uncle->_col == RED)
         {
       
             grandparent->_col = RED;
             parent->_col = uncle->_col= BLACK;
             cur = grandparent;
             parent = cur->_parent;
         }
         else
         {
       
             if (cur == parent->_right)
             {
       
                 RotateL(grandparent);
                 parent->_col = BLACK;
                 grandparent->_col = RED;
             }
             else
             {
       
                 RotateR(parent);
                 RotateL(grandparent);
                 cur->_col = BLACK;
                 grandparent->_col = RED;
             }
         }
         break;
     }
  }
  

红黑树平衡的验证

• 根节点不需要进行验证直接返回就好
• 根节点如果是红色的节点可以进行返回。保证根节点是黑色的
• 红黑树的特点就是每一个路径的黑色节点数目是一样的。这时候就需要检查黑色节点的数目

bool is_balance(Node* root)
{
   
    if (root == nullptr)
    {
   
        return true;
    }

    if (root->_col == RED)
    {
   
        return false;
    }
    int stdnum = 0;
    Node* cur = root;
    while (cur)
    {
   
        if (cur->_col == BLACK)
        {
   
            ++stdnum;
        }
        cur = cur->_left;
    }

    return Checknum(root, 0, stdnum);
}

检查黑色节点

• 利用传值调用，递归实现
• 走到根节点进行判断，如果是和标准相等的情况下，返回true。

bool Checknum(Node* root, int blacknum, int stdnum)
{
   
    if (root == nullptr)
    {
   
        if (blacknum != stdnum)
        {
   
            return false;
        }
        return true;
    }

    if (root->_col == BLACK)
    {
   
        ++blacknum;
    }

    return Checknum(root->_left, blacknum, stdnum)
        && Checknum(root->_right, blacknum, stdnum);
}

源码

#pragma once


#include<iostream>
#include<assert.h>
#include<utility>

using namespace std;

namespace RBTree
{
   
    enum Colour
    {
   
        RED,
        BLACK
    };
    template<class K, class V>
    class RBTreeNode
    {
   
    public:
        RBTreeNode<K, V>* _left;
        RBTreeNode<K, V>* _right;
        RBTreeNode<K, V>* _parent;
        pair<K, V> _kv;
        Colour _col;

        RBTreeNode(const pair<K, V>& kv)
            :_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv)
        {
   }
    };

    template<class K, class V>
    class RBTree
    {
   
        typedef RBTreeNode<K, V> Node;

    public:
        bool is_balance()
        {
   
            return is_balance(_root);
        }

        bool Checknum(Node* root, int blacknum, int stdnum)
        {
   
            if (root == nullptr)
            {
   
                if (blacknum != stdnum)
                {
   
                    return false;
                }
                return true;
            }

            if (root->_col == BLACK)
            {
   
                ++blacknum;
            }

            return Checknum(root->_left, blacknum, stdnum)
                && Checknum(root->_right, blacknum, stdnum);
        }
        bool is_balance(Node* root)
        {
   
            if (root == nullptr)
            {
   
                return true;
            }

            if (root->_col == RED)
            {
   
                return false;
            }
            int stdnum = 0;
            Node* cur = root;
            while (cur)
            {
   
                if (cur->_col == BLACK)
                {
   
                    ++stdnum;
                }
                cur = cur->_left;
            }

            return Checknum(root, 0, stdnum);
        }
        bool insert(const pair<K, V>& kv)
        {
   
            if (_root == nullptr)
            {
   
                _root = new Node(kv);
                _root->_col = BLACK;
                return true;
            }
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
   
                if (kv.first > cur->_kv.first)
                {
   
                    parent = cur;
                    cur = cur->_right;
                }
                else if (kv.first < cur->_kv.first)
                {
   
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
   
                    return false;
                }
            }

            cur = new Node(kv);
            cur->_col = RED;

            if (kv.first < parent->_kv.first)
            {
   
                parent->_left = cur;
            }
            else
            {
   
                parent->_right = cur;
            }
            cur->_parent = parent;

            while (parent && parent->_col == RED)
            {
   
                Node* grandparent = parent->_parent;
                if (parent == grandparent->_left)
                {
   
                    Node* uncle = grandparent->_right;
                    if (uncle && uncle->_col == RED)
                    {
   
                        parent->_col = uncle->_col = BLACK;
                        grandparent->_col = RED;
                        cur = grandparent;
                        parent = cur->_parent;
                    }
                    else//uncle is not or black
                    {
   
                        if (cur == parent->_left)
                        {
   
                            RotateR(grandparent);
                            grandparent->_col = RED;
                            parent->_col = BLACK;
                        }
                        else
                        {
   
                            RotateL(parent);
                            RotateR(grandparent);
                            grandparent->_col = RED;
                            cur->_col = BLACK;
                        }
                        break;
                    }
                }
                else//parent == grandparent->_right
                {
   
                    Node* uncle = grandparent->_left;

                    if (uncle && uncle->_col == RED)
                    {
   
                        grandparent->_col = RED;
                        parent->_col = uncle->_col= BLACK;
                        cur = grandparent;
                        parent = cur->_parent;
                    }
                    else
                    {
   
                        if (cur == parent->_right)
                        {
   
                            RotateL(grandparent);
                            parent->_col = BLACK;
                            grandparent->_col = RED;
                        }
                        else
                        {
   
                            RotateR(parent);
                            RotateL(grandparent);
                            cur->_col = BLACK;
                            grandparent->_col = RED;
                        }
                    }
                    break;
                }
            }
            _root->_col = BLACK;
            return true;
        }

        void RotateR(Node* parent)
        {
   
            Node* cur = parent->_left;
            Node* curright = cur->_right;

            parent->_left = curright;

            if (curright)
            {
   
                curright->_parent = parent;
            }

            cur->_right = parent;

            Node* ppnode = parent->_parent;

            parent->_parent = cur;

            if (ppnode == nullptr)
            {
   
                _root = cur;
                cur->_parent = nullptr;
            }
            else
            {
   
                if (ppnode->_left == parent)
                {
   
                    ppnode->_left = cur;
                }
                else
                {
   
                    ppnode->_right = cur;
                }

                cur->_parent = ppnode;
            }

        }
        void RotateL(Node* parent)
        {
   

            Node* cur = parent->_right;

            Node* curleft = cur->_left;

            parent->_right = curleft;

            if (curleft)
            {
   
                curleft->_parent = parent;
            }

            cur->_left = parent;

            Node* ppnode = parent->_parent;

            parent->_parent = cur;

            if (parent == _root)
            {
   
                _root = cur;
                cur->_parent = nullptr;
            }
            else
            {
   
                if (ppnode->_left == parent)
                {
   
                    ppnode->_left = cur;
                }
                else
                {
   
                    ppnode->_right = cur;
                }

                cur->_parent = ppnode;
            }
        }

    private:
        Node* _root = nullptr;
    };

}

    }
        void RotateL(Node* parent)
        {
   

            Node* cur = parent->_right;

            Node* curleft = cur->_left;

            parent->_right = curleft;

            if (curleft)
            {
   
                curleft->_parent = parent;
            }

            cur->_left = parent;

            Node* ppnode = parent->_parent;

            parent->_parent = cur;

            if (parent == _root)
            {
   
                _root = cur;
                cur->_parent = nullptr;
            }
            else
            {
   
                if (ppnode->_left == parent)
                {
   
                    ppnode->_left = cur;
                }
                else
                {
   
                    ppnode->_right = cur;
                }

                cur->_parent = ppnode;
            }
        }

    private:
        Node* _root = nullptr;
    };

}