AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

c++的学习之路：27、红黑树

2024-04-22 51
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： c++的学习之路：27、红黑树

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的，如下方这个图片就是我从网上看到的一个红黑树的图片，这个就是红黑树。

二、 红黑树的性质

红黑树的性质有下面五点，代码也是根据这五点进行编写


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


2、根节点是黑色的


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


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


5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

三、代码实现

1、节点的定义


如下方代码就是利用三叉链进行维护树的，每个节点都是有一个pair以及一个col也就是颜色，如下方代码中的枚举。

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    pair<K, V> _kv;
    Clour _col;

    RBTreeNode(const pair<K,V>& kv)//创建节点、三叉链
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)//颜色记录
    {}

};

enum Clour //红黑树定义一个枚举列表来标记yanse
{
    RED,
    BLACK,
};

2、插入

这个插入前面都和AVL树差不多，但是需要注意的是，就是上面的性质，首先就是根节点必须是黑色，第二就是不能连续红色，第三就是每条路径的黑色要想等，红色节点下面必须是黑色的，那么下面将说一下如何插入的，如下面三种情况。


情况一：如下图有两个红色的时候，这时如果叔叔也是红色，就需要把叔叔也变黑然后祖父变红，最后在把祖父变黑就可以了。

情况二：如下图就是叔叔为黑的时候，这时候需要先进行旋转，在进行染色，这样就可以得出下方这个图。

情况三 ：如下图这个就是情况三，上述的都是单旋就可以解决，这个就需要双旋就变成了情况二，然后在进行如下图。


bool Insert(const pair<V, K> kv)
    {
        while (_root == nullptr)//判空，如果是空就插入节点，这个就是根节点，然后就开始变黑
        {
            _root = new Node(kv);
            _root->_col = BLACK;//初始的根节点必须是黑的
            return true;
        }
        Node* parent = nullptr;//记录父节点
        Node* cur = _root;//记录节点
        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);//创建新节点
        if (cur->_kv.first > kv.first)//找地方插入，kv大就插入在右边
        {
            parent->_left = cur;
        }
        else //kv小就插入在坐标
        {
            parent->_right = cur;
        }
        cur->_parent=parent;
        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;//记录祖父节点在循环中使用
            if (grandfather->_left == parent)//两种情况，一种是父在祖父的左边
            {
                Node* uncle = grandfather->_right;//记录叔叔节点
                if (uncle && uncle->_col == RED)//判断叔叔是否是红色，如果是红色的就把叔叔和父亲置为黑，然后把
                {                                //祖父变红，然后一直叠加到最上面
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//如果叔叔不存在或者叔叔为黑色就走这个了
                {    //      g
                    //    p    u
                    //c
                    if (cur == parent->_left)//图型就如上面这个时，先进行旋转，然后就是先右旋在把父亲变黑，祖父变红
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        //     g
                        //   p   u
                        //     c
                        RotateL(parent);//如图这种形状的时候，就开始双旋，如图
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        //parent->_col = RED;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else//如果在右边的时候如下
            {
                //    g
                //  u   p
                //        c
                Node* uncle = grandfather->_left;
                // 叔叔存在且为红，变色处理，并继续往上处理
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    // 继续往上调整
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else //叔叔不存在或者叔叔存在且为黑，旋转+变色，和上面一样的操作
                {
                    //    g
                    //  u   p
                    //        c
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else
                    {
                        //    g
                        //  u   p
                        //    c
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;//最后把根节点变黑
        return true;
    }

3、验证

这个验证就是根据上面的性质，就行每一性质的检查，就比如下方的第一个就是检查根节点。

bool IsBalance()
    {
        if (_root && _root->_col == RED)
        {
            cout << "根节点颜色是红色" << endl;
            return false;
        }

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

        // 检查是否有连续红色节点
        return _Check(_root, 0, benchmark);
    }

下面是进行一组数据的检测，测试结果如下，没插入一个数据就进行测试一下，每次都进行判断一次红黑树是否为真，如下方代码。

void TestRBTree1()
{
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    RBTree<int, int> t1;
    for (auto e : a)
    {
        t1.Insert(make_pair(e, e));
        cout << e << "插入：" << t1.IsBalance() << endl;
    }

    t1.InOrder();
    cout << endl;
    cout << t1.IsBalance() << endl;
}

四、代码

#pragma once
 
enum Clour //红黑树定义一个枚举列表来标记yanse
{
  RED,
  BLACK,
};
 
template<class K, class V>
struct RBTreeNode
{
  RBTreeNode* _left;
  RBTreeNode* _right;
  RBTreeNode* _parent;
  pair<K, V> _kv;
  Clour _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:
  bool Insert(const pair<V, K> kv)
  {
    while (_root == nullptr)//判空，如果是空就插入节点，这个就是根节点，然后就开始变黑
    {
      _root = new Node(kv);
      _root->_col = BLACK;//初始的根节点必须是黑的
      return true;
    }
    Node* parent = nullptr;//记录父节点
    Node* cur = _root;//记录节点
    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);//创建新节点
    if (cur->_kv.first > kv.first)//找地方插入，kv大就插入在右边
    {
      parent->_left = cur;
    }
    else //kv小就插入在坐标
    {
      parent->_right = cur;
    }
    cur->_parent=parent;
    while (parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;//记录祖父节点在循环中使用
      if (grandfather->_left == parent)//两种情况，一种是父在祖父的左边
      {
        Node* uncle = grandfather->_right;//记录叔叔节点
        if (uncle && uncle->_col == RED)//判断叔叔是否是红色，如果是红色的就把叔叔和父亲置为黑，然后把
        {               //祖父变红，然后一直叠加到最上面
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else//如果叔叔不存在或者叔叔为黑色就走这个了
        { //    g
          //  p u
          //c
          if (cur == parent->_left)//图型就如上面这个时，先进行旋转，然后就是先右旋在把父亲变黑，祖父变红
          {
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            //     g
            //   p   u
            //     c
            RotateL(parent);//如图这种形状的时候，就开始双旋，如图
            RotateR(grandfather);
            cur->_col = BLACK;
            //parent->_col = RED;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else//如果在右边的时候如下
      {
        //    g
        //  u   p
        //        c
        Node* uncle = grandfather->_left;
        // 叔叔存在且为红，变色处理，并继续往上处理
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
 
          // 继续往上调整
          cur = grandfather;
          parent = cur->_parent;
        }
        else //叔叔不存在或者叔叔存在且为黑，旋转+变色，和上面一样的操作
        {
          //    g
          //  u   p
          //        c
          if (cur == parent->_right)
          {
            RotateL(grandfather);
            grandfather->_col = RED;
            parent->_col = BLACK;
          }
          else
          {
            //    g
            //  u   p
            //    c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;//最后把根节点变黑
    return true;
  }
 
  ~RBTree()
  {
    _Destroy(_root);
    _root = nullptr;
  }
 
  Node* Find(const K& key)
  {
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < key)
      {
        cur = cur->_right;
      }
      else if (cur->_kv.first > key)
      {
        cur = cur->_left;
      }
      else
      {
        return cur;
      }
    }
 
    return nullptr;
  }
 
  void InOrder()
  {
    _InOrder(_root);
  }
 
  bool IsBalance()
  {
    if (_root && _root->_col == RED)
    {
      cout << "根节点颜色是红色" << endl;
      return false;
    }
 
    int benchmark = 0;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_col == BLACK)
        ++benchmark;
      cur = cur->_left;
    }
 
    // 检查是否有连续红色节点
    return _Check(_root, 0, benchmark);
  }
 
  int Height()
  {
    return _Height(_root);
  }
 
private:
  void _Destroy(Node* root)
  {
    if (root == nullptr)
      return;
 
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  }
 
  int _Height(Node* root)
  {
    if (root == NULL)
      return 0;
 
    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
 
    return leftH > rightH ? leftH + 1 : rightH + 1;
  }
 
  bool _Check(Node* root, int blackNum, int benchmark)
  {
    if (root == nullptr)
    {
      if (benchmark != blackNum)
      {
        cout << "某条路径黑色节点的数量不相等" << endl;
        return false;
      }
 
      return true;
    }
 
    if (root->_col == BLACK)
    {
      ++blackNum;
    }
 
    if (root->_col == RED
      && root->_parent
      && root->_parent->_col == RED)
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
 
    return _Check(root->_left, blackNum, benchmark)
      && _Check(root->_right, blackNum, benchmark);
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
 
    _InOrder(root->_left);
    cout << root->_kv.first << " ";
    _InOrder(root->_right);
  }
 
  void RotateL(Node* parent)//左旋，就不介绍了，AVL里面更详细
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
 
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
 
    Node* ppnode = parent->_parent;
 
    subR->_left = parent;
    parent->_parent = subR;
 
    if (ppnode == nullptr)
    {
      _root = subR;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subR;
      }
      else
      {
        ppnode->_right = subR;
      }
 
      subR->_parent = ppnode;
    }
  }
 
  void RotateR(Node* parent)//右旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
 
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
 
    Node* ppnode = parent->_parent;
 
    subL->_right = parent;
    parent->_parent = subL;
 
    if (parent == _root)
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subL;
      }
      else
      {
        ppnode->_right = subL;
      }
      subL->_parent = ppnode;
    }
  }
 
  Node* _root = nullptr;
};
 
void TestRBTree1()
{
  int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  RBTree<int, int> t1;
  for (auto e : a)
  {
    t1.Insert(make_pair(e, e));
    cout << e << "插入：" << t1.IsBalance() << endl;
  }
 
  t1.InOrder();
  cout << endl;
  cout << t1.IsBalance() << endl;
}


文章标签：
C++
关键词：
C++学习
C++红黑树
C++学习红黑树
懒懒学c
目录
相关文章
土木林森
|
3月前
|
算法 C语言 C++
C++语言学习指南：从新手到高手，一文带你领略系统编程的巅峰技艺！
【8月更文挑战第22天】C++由Bjarne Stroustrup于1985年创立，凭借卓越性能与灵活性，在系统编程、游戏开发等领域占据重要地位。它继承了C语言的高效性，并引入面向对象编程，使代码更模块化易管理。C++支持基本语法如变量声明与控制结构；通过`iostream`库实现输入输出；利用类与对象实现面向对象编程；提供模板增强代码复用性；具备异常处理机制确保程序健壮性；C++11引入现代化特性简化编程；标准模板库(STL)支持高效编程；多线程支持利用多核优势。虽然学习曲线陡峭，但掌握后可开启高性能编程大门。随着新标准如C++20的发展，C++持续演进，提供更多开发可能性。
土木林森
79 0
梦笔生花伟
|
22天前
|
编译器 C语言 C++
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言，那就需要配置必要的环境和相关的软件，才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境，您需要确保电脑上有以下两款可用的软件，文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件，源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前，请确保您有一个文本编辑器，且有足够的经验来编写一个计算机程序，然后把它保存在一个文件中，编译并执行它。 Visual Studio Code：虽然它是一个通用的文本编辑器，但它有很多插
梦笔生花伟
53 6
nanshaws
|
1月前
|
Java 编译器 C++
c++学习，和友元函数
本文讨论了C++中的友元函数、继承规则、运算符重载以及内存管理的重要性，并提到了指针在C++中的强大功能和使用时需要注意的问题。
nanshaws
19 1
枫叶丹4
|
3月前
|
关系型数据库 C++ 容器
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——红黑树
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——红黑树
枫叶丹4
35 0
小余大牛成长记
|
4月前
|
存储 安全 编译器
【C++入门 四】学习C++内联函数 | auto关键字 | 基于范围的for循环(C++11) | 指针空值nullptr(C++11)
【C++入门 四】学习C++内联函数 | auto关键字 | 基于范围的for循环(C++11) | 指针空值nullptr(C++11)
小余大牛成长记
67 2
小余大牛成长记
|
4月前
|
人工智能 分布式计算 Java
【C++入门 一 】学习C++背景、开启C++奇妙之旅
【C++入门 一 】学习C++背景、开启C++奇妙之旅
小余大牛成长记
53 1
დ旧言~
|
4月前
|
Java C++ Python
【C++】手撕红黑树
【C++】手撕红黑树
დ旧言~
26 1
小余大牛成长记
|
4月前
|
存储 自然语言处理 编译器
【C++入门 三】学习C++缺省参数 | 函数重载 | 引用
【C++入门 三】学习C++缺省参数 | 函数重载 | 引用
小余大牛成长记
53 1
小余大牛成长记
|
4月前
|
小程序 C++
【C++入门 二 】学习使用C++命名空间及其展开
【C++入门 二 】学习使用C++命名空间及其展开
小余大牛成长记
53 1
笨笨小乌龟
|
4月前
|
C++
C++基础知识（四：类的学习）
类指的就是对同一类对象，把所有的属性都封装起来，你也可以把类看成一个高级版的结构体。
笨笨小乌龟
59 0