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

相关推荐

10-30 20:09
哈尔滨理工大学 Java
点赞 评论 收藏
分享
11-28 19:01
哈尔滨理工大学 算法工程师
点赞 评论 收藏
分享
11-08 23:28
河南理工大学 平台产品
点赞 评论 收藏
分享
11-29 18:37
已编辑
门头沟学院 大数据开发工程师
点赞 评论 收藏
分享
头像
10-28 15:28
山西农业大学 Java
Java应届生技术栈模版
简历上的技术栈一定要具有层次感，比如基础--数据库--NOSQL--框架--微服务--运维工具&nbsp;注释：408可以提现应届生的专业素养&nbsp;注释：大家在学习多线程的时候，JMM往往是大家忽略的内容，但是JMM的内容是至关重要的&nbsp;掌握计算机网络、数据结构、计算机操作系统、计算机组成原理&nbsp;Java基础：掌握Java基础、如集合框架、Stream流、反射机制、网络IO、多线程、JMM、JUC并发编程&nbsp;JVM：熟悉JVM的内存模型、类加载机制、垃圾回收机制等&nbsp;MySQL：熟悉日志、MVCC、事务、索引、锁机制，具备慢SQL的优化经验&nbsp;NoSQL：熟悉Redis的基本数据结构、网络模型、持久化策略、分布式锁、...
八股文+场景题+算法真题
点赞 评论 收藏
分享
评论
8
26
分享

招聘动态

查看更多

阿里云管培生

2025届校园招聘

富士通（西安）

2025校园招聘

全站热榜

正在热议
# 拼多多求职进展汇总 #
237528次浏览 2039人参与
# 机械求职避坑tips #
23686次浏览 249人参与
# 阿里云管培生offer #
62753次浏览 1761人参与
# 25届秋招总结 #
411990次浏览 4133人参与
# 25届机械人为了秋招做了哪些准备？ #
26319次浏览 363人参与
# 地方国企笔面经互助 #
7015次浏览 17人参与
# 北方华创开奖 #
67142次浏览 553人参与
# ai智能作图 #
29367次浏览 352人参与
# 虾皮求职进展汇总 #
92125次浏览 751人参与
# 实习，投递多份简历没人回复怎么办 #
2441314次浏览 34746人参与
# 软件开发投递记录 #
1481902次浏览 23947人参与
# 我的实习求职记录 #
6134864次浏览 84021人参与
# 我在牛爱网找对象 #
74907次浏览 555人参与
# 发工资后，你做的第一件事是什么 #
9238次浏览 43人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
83364次浏览 602人参与
# 机械人怎么评价今年的华为 #
158004次浏览 1352人参与
# 京东求职进展汇总 #
513230次浏览 4681人参与
# 如果可以，你希望哪个公司来捞你 #
34045次浏览 196人参与
# 你觉得通信/硬件有必要实习吗？ #
54809次浏览 698人参与
# 歌尔求职进展汇总 #
42921次浏览 294人参与
# 在职场上，你最讨厌什么样的同事 #
6121次浏览 91人参与
# 如果再来一次，你还会选择这个工作吗？ #
116119次浏览 1145人参与
牛客网
牛客企业服务