关注

[C++] 深入理解红黑树与代码实现

1. 红黑树的概念

红黑树是一颗二叉搜索树，具备二叉搜索树的所有性质。可以跳转至这篇文章了解二叉搜索树：

C++：深入理解二叉搜索树与代码实现

红黑树在二叉搜索树的基础上还具有以下性质：

  1. 只有红色和黑色两种节点
  2. 根节点为黑色
  3. 任何一条路径都不会出现连续的红色节点
  4. 任何一条路径上的黑色节点数量相同

红黑树在二叉搜索树的基础上，通过控制颜色来控制平衡，最长路径不超过最短路径的两倍。

为什么呢？
根据性质4，极端场景下的最短路径全是黑色节点，假设最短路径是 b（black）；
由规则2，3可知，极端场景下的最长路径为一黑一红节点间隔组成，那么最长路径为 2 * b；
但并不是每一棵红黑树的最长 / 最短路径都符合以上的极端情况，因此，假设任意一条路径长度为x，那么 b <= x <= 2 * b 。
请添加图片描述

2. 时间复杂度分析

假设N是红黑树中节点的数量，h是最短路径的长度，那么可以得出 2^h -1 <= N < 2^(2*h) -1 的结论，由此可以推断出 h 近似为 logN 。也就是说红黑树增删查改的最坏情况也就是走最长路径即 2 * logN ，时间复杂度的量级还是 O(logN)。请添加图片描述
红黑树和AVL树都是通过不同的方式使二叉搜索树尽量平衡，因此他们的效率位于同一档次；且红黑树对平衡的控制没那么严格，因此旋转次数更少，C++的STL中也更多使用红黑树作为底层容器。

3. 红黑树的实现

3.1 红黑树的结构

  • 节点：红黑树仅仅在平衡规则部分与AVL树不同，因此红黑树的节点中没有平衡因子，而是用颜色作为枚举值来表示。剩余成员和AVL树相同（父节点指针，左右孩子指针，key / value）。
  • 树：红黑树的成员为根节点。

以下是以key / value为例的红黑树框架：

// 枚举值表示颜色
enum Colour
{
    RED,
    BLACK
};

// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
    // 这里更新控制平衡也要加入parent指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;

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

template<class K, class V>
class RBTree
{
private:
    Node* _root = nullptr;
    typedef RBTreeNode<K, V> Node;
public:
	//...
};

3.2 红黑树的插入

红黑树的插入逻辑和二叉搜索树相同，即找到一个合适的空位置插入。插入后仅需观察颜色是否符合规则即可：

  1. 若为空树，插入的节点为根节点，颜色设置为黑，插入结束。
  2. 不为空树，插入的节点颜色设置为红，如果父节点为黑，则符合条件，插入结束；若父节点为红，则不满足规则3（不能出现连续的红色节点），需要向上调整颜色 / 旋转。

对于是否需要旋转，主要观察的是uncle节点，也就是父节点的兄弟节点，如图：
在这里插入图片描述
（插入的是x节点，parent节点为6，uncle节点为15，grandparent节点为10）

3.2.1 情况一：仅变色

当uncle节点存在且为红色时，仅需变色即可：
在这里插入图片描述

  1. 如果grandparent节点的父节点仍然是红色，则一直向上更新；
  2. 如果父节点为黑色，则停止更新；
  3. 最坏情况是一路向上更新到了根节点，此时需要将根节点变为黑色，停止更新。

3.2.2 情况二：旋转 + 变色

当uncle节点不存在或者为黑色时，需要旋转 + 变色。

我们可以通过uncle节点的状态来推断cur节点的性质：如果uncle节点不存在，则cur节点一定是新增节点；如果uncle节点存在且为黑，则cur节点一定不是新增节点。假设法证明如下：
在这里插入图片描述

  • 旋转：究竟需要单旋还是双旋，判断条件和AVL树相同。即看cur，parent，grandparent节点是否在一条直线上，如果在，则单旋；否则双旋。
  • 变色：要解决连续红色节点的问题，同时还要保证各条路径上的黑色节点数量相同，接下来我们具体情况具体分析。
⭕左单旋：

请添加图片描述
当g，p，c节点呈一条直线，且p，c均为右孩子节点时，需要进行左单旋。旋转后p，c节点均为红色，为了避免出现连续红色节点，需要将p节点变为黑色，原先左边路径有两个黑色节点，为了保持一致，需要更改g的颜色为红色。

由于之前证明了c节点一定不是新增节点，因此旋转前每条路径的黑色节点个数是符合规则4（任意路径黑色节点数量相同）的，只需要保持原先路径的黑色节点数量不变即可，不需要改变c节点的颜色。

⭕右单旋：

右单旋的场景就是左单旋的水平翻转，变色规则相同：
请添加图片描述

⭕左右双旋:

请添加图片描述
当p为g的右孩子节点，c为p的左孩子节点时，需要进行左右双旋。旋转后p，c节点均为红色，为了保证没有连续的红色节点，并且路径上黑色节点数量一致，需要将c节点变为黑色，g节点变为红色。

⭕右左双旋：

右左双旋的场景就是左右双旋的水平翻转，变色规则相同：
请添加图片描述

红黑树插入代码实现：

bool Insert(const pair<K, V>& kv)
{
    //根
    if(!_root)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    //非根
    Node* cur = _root;
    Node* parent = nullptr;
    while(cur)
    {
        if(cur->kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if(cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }

    //新建节点
    cur = new Node(kv);
    cur->_col = RED;

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

    cur->_parent = parent;

    //旋转调整
    while(parent && parent->_col = RED)
    {
        Node* grandfather = parent->_parent;

        //p在g左
        if(parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;

            //u存在且为红->变色继续向上处理
            if(uncle && uncle->_col == RED)
            {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;

                cur = grandfather;
                parent = grandfather->_parent;
            }
            else //u不存在或为黑
            {
                if(cur == parent->_left)
                {
                    RotateR(grandfather);

                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    RotateL(parent);
                    RotateR(grandfather);

                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }

                break;
            }
        }
        //p在g右
        else
        {
            Node* uncle = grandfather->_left;
            //仅变色
            if(uncle && uncle->_col == RED)
            {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;

                cur = parent;
                parent = grandfather;
            }
            else //旋转 + 变色
            {
                if(cur == parent->_right)
                {
                    RotateL(grandfather);

                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    RotateR(parent);
                    RotateL(grandfather);

                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }

                break;
            }
        }
    }

    //一律设置为黑
    _root->_col = BLACK;

    return true;
}

//右旋
void RotateR(Node* pParent)
{
    Node* parent = pParent;
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    //1.parent和subLR
    parent->_left = subLR;

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

    Node* parentParent = parent->_parent;

    //2.parent和subL
    parent->_parent = subL;
    subL->_right = parent;

    //3.subL和parentParent
    if(parentParent == nullptr)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if(parentParent->_left == parent)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }

        subL->_parent = parentParent;
    }
}

//左旋
void RotateL(Node* pParent)
{
    Node* parent = pParent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    //1.parent和subRL
    parent->_right = subRL;
    if(subRL)
    {
        subRL->_parent = parent;
    }

    //2.parent和subR
    Node* parentParent = parent->_parent;

    parent->_parent = subR;
    subR->_left = parent;

    //3.subR和parentParent
    if(parentParent == nullptr)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {            
        if(parentParent->_left == parent)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }

        subR->_parent = parentParent;
    }
}

在写双旋代码的过程中，可以按照以下顺序实现，思路更清晰：

  1. parent节点和subRL / subLR节点
  2. parent节点和subR / subL节点
  3. subR / subL节点和parentParent节点

3.3 红黑树的查找

按照二叉搜索树的规则查找即可，时间复杂度为O(logN)：

//查找
Node* Find(const K& key)
{
    Node* cur = _root;
    while(cur)
    {
        if(cur->_kv.first > key)
        {
            cur = cur->_left;
        }
        else if(cur->_kv.first < key)
        {
            cur = cur->_right;
        }
        else
        {
            return cur;
        }
    }

    return nullptr;
}

4. 红黑树的验证

红黑树的验证主要根据四点规则开展，满足了规则就能保证最长路径不超过最短路径的两倍：

  1. 规则1无需多言，2可以直接检查根；
  2. 规则3前序遍历检查，遇到红⾊结点查孩⼦会涉及分类讨论和是否存在的问题，比较麻烦，因此采用检查⽗节点的颜⾊的方式是否合法；
  3. 规则4可以通过前序遍历，并用形参记录根到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。

代码验证：

bool Check(Node* root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        // 前序遍历走到空时，意味着一条路径走完了
        //cout << blackNum << endl;
        if (refNum != blackNum)
        {
            cout << "存在黑色结点的数量不相等的路径" << endl;
            return false;
        }

        return true;
    }

    // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;
    }

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

    return Check(root->_left, blackNum, refNum)
        && Check(root->_right, blackNum, refNum);
}

bool IsBalance()
{
    if (_root == nullptr)
        return true;

    if (_root->_col == RED)
        return false;

    // 参考值
    int refNum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
        {
            ++refNum;
        }

        cur = cur->_left;
    }

    return Check(_root, 0, refNum);
}

// 本期内容就到这里啦，如果对你有帮助，请三连支持！我是青云，我们下期见^_~

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/HikariT/article/details/161890933

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--