C++ 红黑树

这篇具有很好参考价值的文章主要介绍了C++ 红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.红黑树的概念

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

C++ 红黑树,算法

2.红黑树的性质

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

2. 根节点是黑色的 

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

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

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

3.红黑树节点的定义 

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
 RBTreeNode(const ValueType& data = ValueType(),Color color = RED)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
     , _data(data), _color(color)
 {}
 RBTreeNode<ValueType>* _pLeft;   // 节点的左孩子
 RBTreeNode<ValueType>* _pRight;  // 节点的右孩子
 RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转,为了实现简单给
出该字段)
 ValueType _data;            // 节点的值域
 Color _color;               // 节点的颜色
};

4.红黑树结构

为了后续实现关联式容器简单,红黑树的实现中增加一个头结点,因为跟节点必须为黑色,为了 与根节点进行区分,将头结点给成黑色,并且让头结点的 pParent 域指向红黑树的根节点,pLeft 域指向红黑树中最小的节点,_pRight域指向红黑树中最大的节点,如下:

C++ 红黑树,算法

5. 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

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

template<class ValueType>
class RBTree
{
    //……
 bool Insert(const ValueType& data)
 {
 PNode& pRoot = GetRoot();
 if (nullptr == pRoot)
 {
 pRoot = new Node(data, BLACK);
 // 根的双亲为头节点
 pRoot->_pParent = _pHead;
            _pHead->_pParent = pRoot;
 }
 else
 {
 // 1. 按照二叉搜索的树方式插入新节点
             // 2. 检测新节点插入后,红黑树的性质是否造到破坏,
 //   若满足直接退出,否则对红黑树进行旋转着色处理
 }
 // 根节点的颜色可能被修改,将其改回黑色
 pRoot->_color = BLACK;
 _pHead->_pLeft = LeftMost();
 _pHead->_pRight = RightMost();
 return true;
 }
private:
 PNode& GetRoot(){ return _pHead->_pParent;}
 // 获取红黑树中最小节点,即最左侧节点
 PNode LeftMost();
 // 获取红黑树中最大节点,即最右侧节点
 PNode RightMost();
private:
 PNode _pHead;
};

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

因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:

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

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

 C++ 红黑树,算法

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

C++ 红黑树,算法

p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反, p为g的右孩子,cur为p的右孩子,则进行左单旋转 p、g变色--p变黑,g变红

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

p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;

相反, p为g的右孩子,cur为p的左孩子,则针对p做右单旋转

则转换成了情况2

6.红黑树的验证

红黑树的检测分为两步:

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

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

相关代码

bool IsValidRBTree()
{
     PNode pRoot = GetRoot();
 // 空树也是红黑树
 if (nullptr == pRoot)
 return true;
 // 检测根节点是否满足情况
 if (BLACK != pRoot->_color)
 {
 cout << "违反红黑树性质二:根节点必须为黑色" << endl;
 return false;
 }
 // 获取任意一条路径中黑色节点的个数
 size_t blackCount = 0;
PNode pCur = pRoot;
 while (pCur)
 {
 if (BLACK == pCur->_color)
 blackCount++;
 pCur = pCur->_pLeft;
 }
 // 检测是否满足红黑树的性质,k用来记录路径中黑色节点的个数
 size_t k = 0;
 return _IsValidRBTree(pRoot, k, blackCount);
 }
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{
    //走到null之后,判断k和black是否相等
 if (nullptr == pRoot)
     {
         if (k != blackCount)
 {
 cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;
 return false;
 }
         return true;
     }
 // 统计黑色节点的个数
 if (BLACK == pRoot->_color)
 k++;
 // 检测当前节点与其双亲是否都为红色
 PNode pParent = pRoot->_pParent;
 if (pParent && RED == pParent->_color && RED == pRoot->_color)
 {
 cout << "违反性质三:没有连在一起的红色节点" << endl;
 return false;
 }
 return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&
    _IsValidRBTree(pRoot->_pRight, k, blackCount);
 }

7.红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O($log_2 N$),红黑树不追 求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数, 所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红 黑树更多。 文章来源地址https://www.toymoban.com/news/detail-744308.html

到了这里,关于C++ 红黑树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】红黑树

    正文开始前给大家推荐个网站,前些天发现了一个巨牛的 人工智能 学习网站, 通俗易懂,风趣幽默 ,忍不住分享一下给大家。 点击跳转到网站。 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的

    2024年01月16日
    浏览(44)
  • C++ 红黑树

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

    2024年02月05日
    浏览(38)
  • C++ 实现红黑树

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

    2024年02月05日
    浏览(39)
  • C++红黑树

    前置说明: 需要学习AVL树的旋转之后再来看红黑树的旋转 因为红黑树的旋转是复用的AVL树的旋转的: 大家可以看我的这篇博客,里面详细介绍了AVL树的四种旋转 C++ AVL树(四种旋转,插入) 对于颜色我们采用枚举类型定义 对于红黑树节点,依旧采用Key-Value模型存储pair 1.共识 首先我们

    2024年02月04日
    浏览(36)
  • 【C++】实现红黑树

    红黑树是一个二叉搜索树,与AVL树相比,红黑树不再使用平衡因子来控制树的左右子树高度差,而是用颜色来控制平衡,颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色,就可以确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 红黑树的规

    2024年03月25日
    浏览(39)
  • C++手撕红黑树

    概念 和AVL树一样,红黑树也是一种二叉搜索树,是解决二叉搜索树不平衡的另一种方案,他在每个节点上增加一个存储位,用于表示节点的颜色,是Red或者Black 红黑树的核心思想是通过一些着色的条件限制,达到一种最长路径不超过最短路径的两倍的状态 所以说红黑树并不

    2024年04月12日
    浏览(41)
  • 【C++】手撕红黑树

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:能直接手撕红黑树。 毒鸡汤:行到水穷处,坐看云起时。。 望小伙伴们点赞👍收藏✨加关注哟💕💕  相信大家肯定听过在C++大名鼎鼎的两颗树,这两颗树分别

    2024年03月23日
    浏览(35)
  • C++之红黑树

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

    2024年02月09日
    浏览(40)
  • 【C++】:红黑树

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关多态的知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 C + + 专 栏   : C++ Linux 专 栏

    2024年02月04日
    浏览(38)
  • C++数据结构--红黑树

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

    2024年02月09日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包