C++手撕红黑树

@TOC

零、前言

本章继AVL树后继续讲解学习C++中另一个二叉搜索树--红黑树

一、红黑树的概念及性质

  • 概念：

  1. 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black

  2. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接***衡的

注：AVL树是严格平衡的二叉搜索树，左右子树高度不超过1；红黑树是近似平衡，最长路径不超过最短路径的二倍

  • 示图：
image-20220228175734450
  • 红黑树的性质：

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的

  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

  5. 每个NIL结点都是黑色的(此处的结点指的是空结点)（该条规则确定了路径条数）

  • 为什么红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍：

红黑树第三条性质说明红黑树不能存在连续（父子相连）的红结点，可以存在连续的黑结点，又由于第四条性质每个路径上的黑结点个数都相同 ，所以对于最短路径来说一定是都是黑色结点，对于最长路径来说一定是黑色红色相间的路径，所以最长路径不超过最短路径长度的二倍

  • 示图：
image-20220228182237198

二、红黑树结点的定义

对于红黑树来说以颜色来代替AVL树的平衡因子的作用，除此之外在定义上没有什么区别

  • 实现代码： 
enum Colour//颜色
{
    RED,
    BLACK,
};
template<class K, class V>
struct RBTreeNode
{
    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)
        , _kv(kv)
        , _col(RED)
    {}
};

注：此处采用枚举来表示，当然也可以使用其他方式

  • 在节点的定义中为什么要将节点的默认颜色给成红色的：

  1. 如果默认颜色为黑，那么在插入中插入一个黑结点一定会让该路径上的黑结点数量加1，从而与其他路径上黑结点数量造成不一致，而一定会影响该棵红黑树

  2. 如果默认颜色为红，那么在插入中插入一个红结点，可能新插入结点的父结点为黑色结点则没有影响，也可能新插入结点的父结点为红结点，由于不能存在连续的（父子相连的）红色结点，而对该棵树造成影响

  3. 所以默认为红色比较黑色来说是好的

三、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，当违反限制条件时就需要做出相应的调整

  • 红黑树的插入可分为两步：

  1. 按照二叉搜索的树规则插入新节点

  2. 新节点插入后检查红黑树的性质是否造到破坏

  • 注意：

  1. 因为新节点的默认颜色是红色，如果其父亲节点的颜色是黑色，则没有违反红黑树任何性质，则不需要调整

  2. 当新插入节点的父亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

  3. 因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在

  4. 红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况

注：约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1、变色处理

情况一: cur为红，p为红，g为黑，u存在且为红

  • 示图：
image-20220301124649974
  • 分析：

  1. 为了让该以 g 为根的子树不存在连续的红色结点，并且不增加路径上的黑色结点，我们让 g 的颜色变红，让 u 和 p 的颜色变黑，各路径上黑色结点数量没变，以此达到红黑树的性质

  2. 因为 p 和 u 的颜色变黑，对其子树没有影响，但是 g 的颜色变红，可能存在影响，需要继续向上判断

  • 判断逻辑：

  1. 如果 g 就是该棵树的根那么最后需要将 g 的颜色变黑

  2. 如果 g 是整棵树的子树，如果 g 的父节点是是黑色结点则不用调整，如果是红色结点则需要根据具体情况来做出调整

  • 解决方式：

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

  • 抽象示图：
image-20220301123629153
  • 动图演示1：
红黑树变色处理
  • 动图演示2：
红黑树变色处理2

2、单旋+变色

情况二: cur为红，p为红，g为黑，u不存在/u为黑

  • 示图：
image-20220301125108739
  • 分析：

  1. 当 u 节点不存在时，说明cur一定是插入节点，如果 cur 不是新插入节点，那么在插入前时 cur 一定是黑色结点（由黑色变红），则插入前就不符合路径上黑结点数量相同的性质

  2. 当 u 节点存在且为黑色时，说明 cur 的颜色插入前一定是黑色，进过插入后变色为红色，否则在插入前就存在连续的红色结点，不符合红黑树性质

  • 解决方法：

  1. 如果p为g的左孩子，cur为p的左孩子，则进行右单旋转，p变黑，g变红

  2. 如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，p变黑，g变红

  • 抽象示图：
image-20220301123356450
  • 动态示图：
红黑树单旋处理1
  • 动图演示2：
红黑树单旋处理2

3、双旋+变色

情况三: cur为红，p为红，g为黑，u不存在/u为黑

  • 示图：
image-20220301130843518
  • 分析：

这里显然一次旋转也无法让达到红黑树平衡，由此就需要进行两次旋转

  • 解决方式：

  1. 如果p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，p旋转后再对g进行右单旋，旋转后将cur变黑，g变红

  2. 如果p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，p旋转后再对g进行左单旋，旋转后将cur变黑，g变红

  • 抽象示图：
image-20220301133953237
  • 动图演示1：
红黑树双旋处理1
  • 动图演示2：
红黑树双旋处理2

4、插入实现

插入主体实现：

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
    //空树的情况
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return make_pair(_root, true);
    }

    //查找位置插入节点
    Node* cur = _root, * parent = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return make_pair(cur, false);
        }
    }

    //创建链接节点
    cur = new Node(kv);
    Node* newnode = cur;
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;

    //父节点存在且为红，则需要调整（不能存在连续的红色节点）
    while (parent && parent->_col == RED)
    {
        //此时当前节点一定有祖父节点
        Node* granparent = parent->_parent;
        //具体调整情况主要看叔叔节点
        //分左右讨论
        if (parent == granparent->_left)
        {
            Node* uncle = granparent->_right;
            //情况1：叔叔节点存在且为红
            if (uncle && uncle->_col == RED)
            {
                //修改颜色，继续向上检查
                granparent->_col = RED;
                parent->_col = uncle->_col = BLACK;

                cur = granparent;
                parent = cur->_parent;
            }
            else//情况2和3：叔叔节点不存在 或者存在且为黑
            {
                //单旋(三代节点为斜线)+变色
                if (cur == parent->_left)
                {
                    RotateR(granparent);

                    granparent->_col = RED;
                    parent->_col = BLACK;
                }
                else//双旋(三代节点为折线)+变色
                {
                    RotateL(parent);
                    RotateR(granparent);

                    cur->_col = BLACK;
                    granparent->_col = RED;
                }
                //旋转后不需再向上调整了
                break;
            }
        }
        else//parent=grandparent->right
        {
            Node* uncle = granparent->_left;
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                granparent->_col = RED;

                cur = granparent;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_right)
                {
                    RotateL(granparent);

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

                    cur->_col = BLACK;
                    granparent->_col = RED;
                }
                break;
            }
        }
    }

    //确保根节点为黑
    _root->_col = BLACK;
    return make_pair(newnode, true);
}

旋转实现：

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentP = parent->_parent;


    parent->_right = subRL;
    if (subRL)
    {
        subRL->_parent = parent;
    }

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

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

void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* parentP = parent->_parent;


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

    subL->_right = parent;
    parent->_parent = subL;

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

四、红黑树的验证

  • 红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

  2. 检测其是否满足红黑树的性质

  • 实现代码： 
bool IsRBTree()
{
    //空树
    if (_root == nullptr)
    {
        return true;
    }
    //根节点为黑色
    if (_root->_col == RED)
    {
        cout << "根节点为红色" << endl;
        return false;
    }
    //黑色结点数量各路径上相同
    //先走一条得到基准值
    int Blacknum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            Blacknum++;
        cur = cur->_left;
    }
    //检查子树
    int i = 0;
    return _IsRBTree(_root, Blacknum, i);
}

bool _IsRBTree(Node* root, int blacknum, int count)
{
    //递归到空节点
    if (root == nullptr)
    {
        if (blacknum == count)
            return true;
        cout << "各路径上黑色节点个数不同" << endl;
        return false;
    }
    //子节点为红则检查父节点是否为红（通过父节点检查子节点会遇到空节点）
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续红色节点" << endl;
        return false;
    }
    //计数黑结点
    if (root->_col == BLACK)
        count++;
    //递归左右子树
    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}

五、红黑树的删除

红黑树的删除不做讲解，有兴趣可参考：《算法导论》或者《STL源码剖析》
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
http://blog.csdn.net/chenhuajie123/article/details/11951777

六、红黑树与AVL树的比较

  • 分析总结：

  1. 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )

  2. 红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数

  3. 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

  • 附上源码

  • RBTree.h:

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

//颜色
enum Colour
{
    RED,
    BLACK,
};
template<class K, class V>
struct RBTreeNode
{
    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)
        , _kv(kv)
        , _col(RED)
    {}
};

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    RBTree()
        :_root(nullptr)
    {
    }

    void _Destory(Node*& root)
    {
        if (root == nullptr)
            return;

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;
        root = nullptr;
    }
    ~RBTree()
    {
        _Destory(_root);
    }

    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;
    }

    pair<Node*, bool> Insert(const pair<K, V>& kv)
    {
        //空树的情况
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return make_pair(_root, true);
        }

        //查找位置插入节点
        Node* cur = _root, * parent = _root;
        while (cur)
        {
            if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return make_pair(cur, false);
            }
        }

        //创建链接节点
        cur = new Node(kv);
        Node* newnode = cur;
        if (parent->_kv.first > kv.first)
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        cur->_parent = parent;

        //父节点存在且为红，则需要调整（不能存在连续的红色节点）
        while (parent && parent->_col == RED)
        {
            //此时当前节点一定有祖父节点
            Node* granparent = parent->_parent;
            //具体调整情况主要看叔叔节点
            //分左右讨论
            if (parent == granparent->_left)
            {
                Node* uncle = granparent->_right;
                //情况1：叔叔节点存在且为红
                if (uncle && uncle->_col == RED)
                {
                    //修改颜色，继续向上检查
                    granparent->_col = RED;
                    parent->_col = uncle->_col = BLACK;

                    cur = granparent;
                    parent = cur->_parent;
                }
                else//情况2和3：叔叔节点不存在 或者存在且为黑
                {
                    //单旋(三代节点为斜线)+变色
                    if (cur == parent->_left)
                    {
                        RotateR(granparent);

                        granparent->_col = RED;
                        parent->_col = BLACK;
                    }
                    else//双旋(三代节点为折线)+变色
                    {
                        RotateL(parent);
                        RotateR(granparent);

                        cur->_col = BLACK;
                        granparent->_col = RED;
                    }
                    //旋转后不需再向上调整了
                    break;
                }
            }
            else//parent=grandparent->right
            {
                Node* uncle = granparent->_left;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    granparent->_col = RED;

                    cur = granparent;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_right)
                    {
                        RotateL(granparent);

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

                        cur->_col = BLACK;
                        granparent->_col = RED;
                    }
                    break;
                }
            }
        }

        //确保根节点为黑
        _root->_col = BLACK;
        return make_pair(newnode, true);
    }

    bool IsRBTree()
    {
        if (_root == nullptr)
        {
            return true;
        }

        if (_root->_col == RED)
        {
            cout << "根节点为红色" << endl;
            return false;
        }

        int Blacknum = 0;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_col == BLACK)
                Blacknum++;
            cur = cur->_left;
        }

        int i = 0;
        return _IsRBTree(_root, Blacknum, i);
    }

private:
    bool _IsRBTree(Node* root, int blacknum, int count)
    {
        if (root == nullptr)
        {
            if (blacknum == count)
                return true;
            cout << "各路径上黑色节点个数不同" << endl;
            return false;
        }

        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "存在连续红色节点" << endl;
            return false;
        }

        if (root->_col == BLACK)
            count++;

        return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* parentP = parent->_parent;


        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }

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

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

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        Node* parentP = parent->_parent;


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

        subL->_right = parent;
        parent->_parent = subL;

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

private:
    Node* _root;
};
  • test.cpp: 
#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
#include <vector>
#include <string>
#include <stdlib.h>
#include <time.h>

void TestRBTree()
{
    //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    RBTree<int, int> t;
    int n = 1000000;
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        int e = rand();
        t.Insert(make_pair(e, e));
    }

    //t.InOrder();
    cout << t.IsRBTree() << endl;
}
void test_RBTree()
{
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    RBTree<int, int> t;
    for (auto e : a)
    {
        t.Insert(make_pair(e, e));

    }
    cout << t.IsRBTree() << endl;
}
int main()
{
    test_RBTree();
    TestRBTree();
    return 0;
}
#高频知识点汇总##数据结构#
全部评论
对我来说还是有点难的
点赞 回复 分享
发布于 2022-08-16 14:10

相关推荐

头像
08-20 16:18
西安电子科技大学 Java
MySQL主从同步如何保证数据一致性？
MySQL&nbsp;主从同步是&nbsp;MySQL&nbsp;集群方案中的一种，也是实现难度最低的一种。&nbsp;然而，现在的面试都不问&nbsp;MySQL&nbsp;主从同步原理了，而是开始问主从同步怎么保证数据一致性问题了。&nbsp;所以，今天就给大家安排上了。&nbsp;1.什么是数据一致性？&nbsp;数据一致性是指在一个系统中，数据在不同的部分、不同的时间点，以及不同的操作之间保持一致的状态。&nbsp;数据一致性通常体现在以下几点：&nbsp;数据一致性：确保数据的完整性意味着数据在存储和传输过程中没有被损坏或丢失。这包括数据的准确性、完整性和有效性。例如，在一个电商系统中，商品的库存数量应该是准确的。如果一个用户购买了一件商品，库存数量应该相应地减少。如果库存数量显示不正确，...
点赞 评论 收藏
分享
09-11 18:45
复旦大学 C++
点赞 评论 收藏
分享
09-11 20:00
北京外国语大学 平台产品
中国企业500强榜单中九家供应链企业上榜
中国企业500强榜单：建发、国贸、物产中大、象屿、钢联、国联、天行云、瑞茂通、易大宗供应链企业上。&nbsp;今年500家上榜的中国公司在2023年的总营业收入达到14.6万亿美元，净利润达到7064亿美元。今年上榜公司的年营收门槛约为37.4亿美元，较去年的门槛提升约9%。&nbsp;国家电网有限公司以5459亿美元的营收位居榜首，中国石化和中国石油分列榜单第二位和第三位。位列第13位的京东集团是成为排位最高的大陆民营企业。&nbsp;互联网企业方面，京东位列第13位，较去年上升3位；腾讯位列第38位，较去年上升7位；阿里巴巴排在第21位，排位未发生改变。美团排在第99位，上升了35位。拼多多位列第119位，较去年大幅上...
投递中国石油等公司10个岗位 >
点赞 评论 收藏
分享
08-29 10:14
重庆理工大学 前端工程师
点赞 评论 收藏
分享
09-13 10:55
门头沟学院 Java
点赞 评论 收藏
分享
8 26 评论
分享

招聘动态

查看更多

米哈游2025校园招聘

华勤技术

2025届秋季校园招聘

奥克斯集团

2025届校园招聘

顺丰集团

2025届校园招聘

大华股份

2025届校园招聘

中国电信天翼云

2025届超级优才招聘

恒生电子

2025届校园招聘

用友

2025届校园招聘

嘉银科技2025校园招聘

满帮集团

2025届秋季校园招聘

全站热榜

正在热议
# 机械人，你最希望上岸的公司是？ #
40677次浏览 1031人参与
# 学信网能看师兄师姐就业去向了 #
55375次浏览 141人参与
# 锐明校招来了 #
15657次浏览 255人参与
# 软件开发薪资爆料 #
1449289次浏览 16600人参与
# 许愿池 #
149378次浏览 2135人参与
# 你都收到了哪些公司的感谢信？ #
128602次浏览 1766人参与
# 阿里云管培生，25届技术冲 #
9147次浏览 119人参与
# 国央企笔面经互助 #
4517次浏览 43人参与
# 如果校招重来我最想改变的是 #
149831次浏览 2155人参与
# 无实习如何秋招上岸 #
536172次浏览 6872人参与
# 正在实习的你，几点下班 #
40848次浏览 320人参与
# 视觉/交互/设计工作体验 #
12375次浏览 170人参与
# 晒一晒我的offer #
6114878次浏览 76409人参与
# 应届生应该先就业还是先择业 #
25820次浏览 183人参与
# 选了这个offer，你有没有后悔？ #
210328次浏览 1975人参与
# 你还有多少年退休？ #
2944次浏览 40人参与
# 你觉得比亚迪今年还有春招吗？ #
80794次浏览 509人参与
# 机械人怎么评价今年的华为 #
116570次浏览 894人参与
# 双非本科求职如何逆袭 #
363603次浏览 4847人参与
# 如何看待offer收割机的行为 #
372668次浏览 4117人参与
# 平台or薪资 硬件uu更看重哪个 #
59089次浏览 371人参与
# 你最近一次加班是什么时候？ #
12830次浏览 111人参与
牛客网
牛客企业服务