AI 助理
备案控制台
开发者社区 数据库 文章 正文

【c++】红黑树

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

红黑树的概念以及性质

概念：

红黑树是一颗二叉搜索树

每个节点不是红色，就是黑色

最长路径最多是最短路径的二倍

2 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

红黑树节点的定义

enum Colour
{
  RED,
  BLACK
};
template<class  K>
struct rbtreenode
{
  rbtreenode<K>* _left;
  rbtreenode<K>* _right;
  rbtreenode<K>* _parent;
  K _key;
  Colour _col;
  
  rbtreenode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)//节点的双亲(红黑树需要旋转，为了实现简单给
出该字段)
    , _key(key)
    , _col(RED)  // 节点的颜色
    
  {}
};

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

这是因为方便新插入的节点的颜色

那我们新插入的结点应该选择插入红色还是黑色呢？？

对于这个问题，如果插入的黑色节点，会打破哪个规则，如果插入的是红色节点又会打破哪个规则?

如果插入黑色节点，需要打破规则4，要检查每个路径很难

如果插入红色节点，需要打破规则3，这时候只需要处理父亲是否为红

所以插入最好是红色，所以初始化列表的颜色为红色

红黑树插入

红黑树也是二叉搜索树，插入可以复用之前的代码

bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new node(key);
      _root->_col = BLACK;
      return true;
    }
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new node(key);
    if (parent->_key > key)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    //红黑树插入处理颜色逻辑
}

红黑树插入处理颜色逻辑

红黑树插入操作详解（一）

如果父亲节点为黑色的话就不用管了，如果插入的结点父亲是红色，此时违背了规则3，此时需要进行处理

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

情况一: cur为红，p为红，g为黑，u存在且为红 (g为根节点)

解决方式：将p,u改为黑，g改为红

情况二: cur为红，p为红，g为黑，u存在且为红 (g不为根节点)

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

红黑树插入操作详解（二）

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

p为g的左孩子，cur为p的左孩子，则进行右单旋转；p、g变色–p变黑，g变红

红黑树插入操作详解（三）

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

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，则转换成了情况3

代码实现插入

bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new node(key);
      _root->_col = BLACK;
      return true;
    }
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new node(key);
    if (parent->_key > key)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      node* grandfather = parent->_parent;
      if (parent == grandfather->_left)
      {
        node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            spinright(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            spinleft(parent);
            spinright(grandfather);
            cur->_col = BLACK;//这里注意情况3转情况4的时候cur会对应情况3的p,情况3的p会变成黑色，这里我们将cur变成黑色即可
            grandfather->_col = RED;
          }
          break;
               }
      }
    
    }
    _root->_col = BLACK;//为了保险起见，最后直接把根节点变黑
    return true;
  }

针对以上情况，可能出现左右镜像的情况，逻辑一模一样，把上面所以关于方向的变量用他的相反代替，就得到

bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new node(key);
      _root->_col = BLACK;
      return true;
    }
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new node(key);
    if (parent->_key > key)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      node* grandfather = parent->_parent;
      if (parent == grandfather->_left)
      {
        node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            spinright(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            spinleft(parent);
            spinright(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_left)
          {
            spinleft(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            spinright(parent);
            spinleft(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return true;
  }

红黑树的验证

我们需要验证根如果是红色就不是红黑树，并且如果相邻的两个节点是红色的话，也不是红黑树

bool Check(node* cur)
  {
    if (cur == nullptr)
      return true;
    if (cur->_col == RED && cur->_parent->_col == RED)//如果要判断当前节点和子节点的话，一个节点要判断两次，所以和父亲结点比较，只需一次
    {
      cout << cur->_key<< "存在连续的红色节点" << endl;
      return false;
    }
    return Check(cur->_left)
      && Check(cur->_right);
  }
  bool IsBalance()
  {
    if (_root && _root->_col == RED)
      return false;
    return Check(_root);
  }

整体代码：

#include<iostream>
#include<string>
using namespace std;
enum Colour
{
  RED,
  BLACK
};
template<class  K>
struct rbtreenode
{
  rbtreenode<K>* _left;
  rbtreenode<K>* _right;
  rbtreenode<K>* _parent;
  K _key;
  Colour _col;
  
  rbtreenode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _key(key)
    , _col(RED)
    
  {}
};
template<class  K>
class rbtree
{
  typedef  rbtreenode<K> node;
public:
  void spinleft(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    parent->_right = subrl;
    if (subrl)
      subrl->_parent = parent;
    subr->_left = parent;
    node* ppnode = parent->_parent;
    parent->_parent = subr;
    if (ppnode == nullptr)
    {
      _root = subr;
      subr->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subr;
        subr->_parent = ppnode;
      }
      else
      {
        ppnode->_right = subr;
        subr->_parent = ppnode;
      }
    }
  
  }
  void spinright(node* parent)
  {
    node* subl = parent->_left;
    node* sublr = subl->_right;
    parent->_left = sublr;
    if (sublr)
      sublr->_parent = parent;
    subl->_right = parent;
    node* ppnode = parent->_parent;
    parent->_parent = subl;
    if (ppnode == nullptr)
    {
      _root = subl;
      subl->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subl;
        subl->_parent = ppnode;
      }
      else
      {
        ppnode->_right = subl;
        subl->_parent = ppnode;
      }
    }
  
  }
  void spinlr(node* parent)
  {
    node* subl = parent->_left;
    node* sublr = subl->_right;
    //int bf = sublr->_bf;
    spinleft(parent->_left);
    spinright(parent);
  /*  if (bf == 1)
    {
      subl->_bf = -1;
      sublr->_bf = 0;
      parent->_bf = 0;
    }
    else if (bf == -1)
    {
      subl->_bf = 0;
      sublr->_bf = 0;
      parent->_bf = 1;
    }
    else
    {
      subl->_bf = 0;
      sublr->_bf = 0;
      parent->_bf = 0;
    }*/
  }
  void spinrl(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    //int bf = subrl->_bf;
    spinright(subr);
    spinleft(parent);
  /*  if (bf == 1)
    {
      parent->_bf = -1;
      subr->_bf = 0;
      subrl->_bf = 0;
    }
    else if (bf == -1)
    {
      parent->_bf = 0;
      subr->_bf = 1;
      subrl->_bf = 0;
    }
    else
    {
      subr->_bf = 0;
      subrl->_bf = 0;
      parent->_bf = 0;
    }*/
  }
  bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new node(key);
      _root->_col = BLACK;
      return true;
    }
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new node(key);
    if (parent->_key > key)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      node* grandfather = parent->_parent;
      if (parent == grandfather->_left)
      {
        node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            spinright(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            spinleft(parent);
            spinright(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_left)
          {
            spinleft(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            spinright(parent);
            spinleft(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return true;
  }
  bool Check(node* cur)
  {
    if (cur == nullptr)
      return true;
    if (cur->_col == RED && cur->_parent->_col == RED)
    {
      cout << cur->_key<< "存在连续的红色节点" << endl;
      return false;
    }
    return Check(cur->_left)
      && Check(cur->_right);
  }
  bool IsBalance()
  {
    if (_root && _root->_col == RED)
      return false;
    return Check(_root);
  }
  void inorder()
  {
    _inorder(_root);
  }
  void _inorder(node* root)
  {
    if (root == nullptr)
      return;
    _inorder(root->_left);
    cout << root->_key  << endl;
    _inorder(root->_right);
  }
  node* Find(const int& key)
  {
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return cur;
      }
    }
  
  
    return nullptr;
  
  
  
  
  
  
  
  }
  
private:
  int treeheight(node* root)
  {
    if (root == nullptr)
      return 0;
    int leftheight = treeheight(root->_left);
    int rightheight = treeheight(root->_right);
    return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
  }
  node* _root = nullptr;
};
int main()
{
  rbtree<int>st;
  int a[] = //{ 16,3,1 };//测试右旋
        //{ 16,32,58 };//测试左旋
    //{ 8,3,1,10,6,4};//测试右左旋
  { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
  for (auto e : a)
  {
    st.insert(e);
  }
  st.inorder();
  int ret = st.IsBalance();
  cout << endl;
  cout << ret;
}
文章标签：
C++
关系型数据库
关键词：
C++红黑树
嘎嘎旺
目录
相关文章
懒懒学c
|
7月前
|
C++
c++的学习之路：27、红黑树
c++的学习之路：27、红黑树
懒懒学c
58 4
诡异森林。
|
7月前
|
测试技术 C++
C++进阶--红黑树
C++进阶--红黑树
诡异森林。
47 1
慕斯(˘▽˘)っ
|
7月前
|
编译器 C++ 容器
【C++学习手札】基于红黑树封装模拟实现map和set
【C++学习手札】基于红黑树封装模拟实现map和set
慕斯(˘▽˘)っ
104 0
chian-ocean
|
1月前
|
存储 C++
【C++】红黑树
红黑树是一种自平衡二叉搜索树，通过节点颜色（红或黑）及特定规则维持平衡，确保操作效率。其性质包括：每个节点非红即黑，根节点必黑，红节点的子节点必黑，从任一节点到其每个叶子的所有路径含相同数量的黑节点。实现上，通过节点结构定义、基本操作（插入、删除、旋转等）、维护平衡性质等步骤完成。代码示例展示了节点定义、插入操作及旋转调整方法。
chian-ocean
32 2
【C++】红黑树
炫酷的伊莉娜
|
7月前
|
C++ 容器
【C++】红黑树模拟实现STL中的map与set
【C++】红黑树模拟实现STL中的map与set
炫酷的伊莉娜
59 0
枫叶丹4
|
4月前
|
关系型数据库 C++ 容器
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——红黑树
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——红黑树
枫叶丹4
43 0
დ旧言~
|
5月前
|
Java C++ Python
【C++】手撕红黑树
【C++】手撕红黑树
დ旧言~
32 1
GR鲸鱼
|
7月前
|
Java C语言 C++
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（上）
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现
GR鲸鱼
61 4
GR鲸鱼
|
7月前
|
C语言
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现（下）
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现
GR鲸鱼
55 3
炫酷的伊莉娜
|
7月前
|
算法 关系型数据库 Java
【C++】红黑树（下）
【C++】红黑树（下）
炫酷的伊莉娜
46 1