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

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

2024-04-22 35
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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
目录
相关文章
一只大鸽子
|
17天前
|
编译器 C++
C++学习笔记（二开始学习C++）
C++学习笔记（二开始学习C++）
一只大鸽子
22 3
Eternity._
|
16天前
|
存储 编译器 程序员
【C++高阶】C++继承学习手册：全面解析继承的各个方面
【C++高阶】C++继承学习手册：全面解析继承的各个方面
Eternity._
16 1
一只大鸽子
|
17天前
|
编译器 C语言 C++
c++primer plus 6 读书笔记 第二章 开始学习C++
c++primer plus 6 读书笔记 第二章 开始学习C++
一只大鸽子
9 1
7fa6b5ui5pmtk
|
25天前
|
C语言 C++ 容器
【C++初阶学习】第十二弹——stack和queue的介绍和使用
【C++初阶学习】第十二弹——stack和queue的介绍和使用
7fa6b5ui5pmtk
25 8
7fa6b5ui5pmtk
|
25天前
|
存储 C++
C++初阶学习第十一弹——探索STL奥秘（六）——深度刨析list的用法和核心点
C++初阶学习第十一弹——探索STL奥秘（六）——深度刨析list的用法和核心点
7fa6b5ui5pmtk
24 7
嘎嘎旺
|
4天前
|
关系型数据库 C++
【c++】红黑树
【c++】红黑树
嘎嘎旺
5 0
游客n5wu27bgadceq
|
6天前
|
存储 编译器 程序员
C++语言基础学习
C++语言基础学习
游客n5wu27bgadceq
6 0
sumith
|
6天前
|
安全 API C++
逆向学习Windows篇：C++中多线程的使用和回调函数的实现
逆向学习Windows篇：C++中多线程的使用和回调函数的实现
sumith
9 0
sumith
|
6天前
|
C++ UED 开发者
逆向学习 MFC 篇：视图分割和在 C++ 的 Windows 窗口程序中添加图标的方法
逆向学习 MFC 篇：视图分割和在 C++ 的 Windows 窗口程序中添加图标的方法
sumith
7 0
richard_yuu
|
11天前
|
设计模式 算法 程序员
【C++】大气、正规的编程习惯：C++学习路径与注意事项
【C++】大气、正规的编程习惯：C++学习路径与注意事项
richard_yuu
14 0