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

从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（下）

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

从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（上）：https://developer.aliyun.com/article/1522282

3.4 红黑树插入完整代码

（旋转还是用AVL树写的旋转，把平衡因子删掉，所以只需复制两个单旋）

  bool Insert(const pair<K, V>& kv)
  {
    if (_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);
    cur->_col = RED; // 默认插入红色结点
    if (parent->_kv.first < kv.first) // 找到位置后插入结点
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
 
    while (parent && parent->_col == RED) // 父亲存在且为红才需要处理
    {
      Node* grandfather = parent->_parent;
      assert(grandfather); // 确定的可以断言下，否则就是插入前就不是红黑树
      assert(grandfather->_col == BLACK);
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红(可以直接复制到下面uncle在左边)
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if(cur == parent->_left) // 情况二的右旋+变色(parent在左)
          {
            //     g      
            //   p   u
            // c
            RotateR(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的左右双旋+变色(parent在左)
          {
            //      g      
                        //   p     u
                        //    c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if (cur == parent->_right) // 情况二的左旋+变色(parent在右)
          {
            //     g      
            //   u   p
            //        c
            RotateL(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的右左双旋+变色(parent在右)
          {
            //       g      
            //    u     p
            //         c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    
    _root->_col = BLACK;
    return true;
  }

4. 红黑树的验证和完整代码

4.1 验证是不是搜索树：

  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
protected:
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }

先拿AVL树的测试过来，Test.c:

#include "RedBlackTree.h"
 
void TestRBTree1()
{
  //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
  RBTree<int, int> t1;
  for (const auto& e : arr)
  {
    t1.Insert(make_pair(e, e));
  }
 
  t1.InOrder();
  //cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
int main()
{
  TestRBTree1();
 
  return 0;
}

4.2 验证是不是红黑树：

       但中序有序只能证明是二叉搜索树，给你验证一颗树是不是红黑树你会怎么验证？是验证最长路径不超过最短路径的两倍还是红黑树的那几条性质？

       要证明二叉树是红黑树还需验证该二叉树是否满足红黑树的性质。因为最长路径不超过最短路径的两倍也不能保证是红黑树，只有满足全部红黑树的性质的才是。

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个空结点都是黑色的（这里的空结点也叫NIL结点，只是为了方便知道有多少条路径）


  • 第一条，枚举就能保证。
  • 第二条，红色就false，一句代码解决。
  • 第三条，我们可以遍历这颗树，用逆向思维，遇到红色结点就反过来判断它的父亲是不是红色的。
  • 第四条，我们可以用前序遍历，遍历第一遍的时候保存黑色结点个数，后面不同就false。
  • 第五条，不用管。

4.3 红黑树完整代码：

RedBlackTree.h：

#pragma once
 
#include <iostream>
#include <assert.h>
#include <time.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; // 比AVL树少了平衡因子，多了颜色
 
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};
 
template<class K, class V>
struct RBTree
{
  typedef RBTreeNode<K, V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_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);
    cur->_col = RED; // 默认插入红色结点
    if (parent->_kv.first < kv.first) // 找到位置后插入结点
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
 
    while (parent && parent->_col == RED) // 父亲存在且为红才需要处理
    {
      Node* grandfather = parent->_parent;
      assert(grandfather); // 确定的可以断言下，否则就是插入前就不是红黑树
      assert(grandfather->_col == BLACK);
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红(可以直接复制到下面uncle在左边)
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if(cur == parent->_left) // 情况二的右旋+变色(parent在左)
          {
            //     g      
            //   p   u
            // c
            RotateR(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的左右双旋+变色(parent在左)
          {
            //      g      
                        //   p     u
                        //    c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if (cur == parent->_right) // 情况二的左旋+变色(parent在右)
          {
            //     g      
            //   u   p
            //        c
            RotateL(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的右左双旋+变色(parent在右)
          {
            //       g      
            //    u     p
            //         c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    
    _root->_col = BLACK;
    return true;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
  bool IsBalance()
  {
    if (_root == nullptr)
    {
      return true;
    }
 
    if (_root->_col == RED) // 验证性质二
    {
      cout << "根节点不是黑色" << endl;
      return false;
    }
 
    int benchmark = 0; // 黑色节点数量基准值
    //Node* cur = _root; // 这种方法是先遍历一遍，然后传值，不过我们可以传引用
    //while (cur)
    //{
    //  if (cur->_col == BLACK)
    //  {
    //    ++benchmark;
    //  }
    //  cur = cur->_left;
    //}
    return PrevCheck(_root, 0, benchmark); // 验证性质三和四
  }
 
protected:
  bool PrevCheck(Node* root, int blackNum, int& benchmark)
  {
    if (root == nullptr)
    {
      if (benchmark == 0)
      {
        benchmark = blackNum;
        return true;
      }
 
      if (blackNum != benchmark) // 验证性质三
      {
        cout << "某条黑色节点的数量不相等" << endl;
        return false;
      }
      else
      {
        return true;
      }
    }
 
    if (root->_col == BLACK)
    {
      ++blackNum;
    }
 
    if (root->_col == RED && root->_parent->_col == RED) // 验证性质四
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
 
    return PrevCheck(root->_left, blackNum, benchmark)
      && PrevCheck(root->_right, blackNum, benchmark);
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
 
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right; // 动了三个标记了的结点，共更新六个指针，这更新两个指针
    Node* subRL = subR->_left;
 
    parent->_right = subRL;
    if (subRL) // subRL不为空才更新
    {
      subRL->_parent = parent;
    }
 
    Node* ppNode = parent->_parent; // 记录parent的parent，防止parent是一颗子树的头结点
 
    subR->_left = parent; // 再更新两个指针
    parent->_parent = subR;
 
    if (_root == parent)  // 最后更新两个指针
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else // parent是一颗子树的头结点
    {
      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 (_root == parent) // 最后更新两个结点
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
 
      subL->_parent = ppNode;
    }
  }
 
  Node* _root = nullptr;
};

Test.c:

#include "RedBlackTree.h"
 
void TestRBTree1()
{
  //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
  RBTree<int, int> t1;
  for (const auto& e : arr)
  {
    t1.Insert(make_pair(e, e));
  }
 
  t1.InOrder();
  cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
void TestRBTree2()
{
  size_t N = 10000;
  srand(time(0));
  RBTree<int, int> t1;
  for (size_t i = 0; i < N; ++i)
  {
    int x = rand();
    cout << "Insert:" << x << ":" << i << endl;
    t1.Insert(make_pair(x, i));
  }
  cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
int main()
{
  TestRBTree2();
 
  return 0;
}

5. 红黑树笔试选择题

1.关于红黑树以下说法正确的是（）

A.空树不是红黑树，因为红黑树要求根节点必须为黑色，而空树中没有根节点

B.红黑树也是二叉搜索树，因此其按照前序遍历可以得到有序序列


C.红黑树是一棵真正平衡的二叉树


D.红黑树最长路径中节点个数可能会等于最短路径中节点个数的两倍


2. 红黑树的插入算法复杂度最坏情况是 （）


A.O(n)


B.O(log(n))


C.O(nlog(n))


D.其他都不对


3. 下面关于红黑树的特性说法错误的是（）


A.红黑树最左侧节点一定是最小的，最右侧节点一定是最大的


B.红黑树在实现时必须要有头结点


C.红黑树中可能会出现连在一起的黑色节点


D.红黑树的旋转不需要依靠平衡因子


4. 关于AVL树和红黑树的区别说法不正确的是（）


A.AVL树和红黑树保证平衡性的方式不同


B.AVL树和红黑树都是平衡树，因此查找的时间复杂度都是O(log_2N)


C.AVL树和红黑树的性质遭到破坏时，都需要进行旋转


D.AVL树和红黑树中序遍历都可以得到有序序列，因为它们都是二叉搜索树

答案：

1. D

A：错误，空树也是红黑树，性质5中规定树中的空指针域为叶子节点，因此空树也是有节点的


B：错误，红黑树也是二叉搜索树，按照中序遍历才可以得到有序序列


C：红黑树不像AVL树那么严格，是一棵近似平衡的二叉搜索树


D：正确，比如红黑树中只有两个节点


2. B


红黑树是近似的平衡树，没有什么最坏情况，插入的时间复杂度为O(log(N))


3. B


A：该题不严谨，这个取决于红黑树中元素的比较规则，最左侧节点可能是最大的，也可能是最小的，没有规定，取决于创建树时的比较方式


B：错误，红黑树在实现时可以没有头节点，这个根据需要是否给出这里头结点和带头双向顺序链表的差不多（我们实现的红黑树就没有）


C：正确，但是一定不能出现连在一起的红色节点


D：正确，红黑树是通过节点颜色以及红黑树的性质来保证其平衡性的，AVL树需要平衡因子保证


4. C


A：正确，AVL树通过节点的平衡因子保证，红黑树通过节点的颜色以及红黑树的特性保证


B：正确，AVL树是严格平衡的，红黑树虽然是近似平衡，但其性能往往比AVL树好，而且实现简 单，因此他们的查找    效率都是O(logN)


C：错误，AVL树是一定需要旋转，红黑树不一定，红黑树有时只需要改变节点的颜色即可


D：正确，参考概念

6. 红黑树的零碎知识

红黑树的删除和AVL树一样不做讲解，有兴趣可参考《STL源码剖析》

红黑树与AVL树的比较

       红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O（logN）。


       红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数。所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树插入动图

1. 以升序插入构建红黑树

2. 以降序插入构建红黑树

随机插入的找不到动图了，放个图片看看：（都是一样保持基本平衡的）

红黑树的应用

1. C++ STL库 -- map / set、mutil_map / mutil_set

2. Java 库

3. linux内核

4. 其他一些库

本篇完。

下一篇：改造红黑树用来封装set和map（红黑树迭代器的实现），再下一篇：哈希。

文章标签：
C语言
C++
Java
Linux
算法
关键词：
C语言C++
C++ c语言
C++概念
C语言红黑树
C语言概念
GR鲸鱼
目录
相关文章
徐霞客320
|
2月前
|
安全 编译器 C语言
C++入门1——从C语言到C++的过渡
C++入门1——从C语言到C++的过渡
徐霞客320
62 2
土木林森
|
4月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树：一场数据结构与算法的华丽舞蹈，让你的程序效率飙升，直击性能巅峰！"
【8月更文挑战第20天】红黑树是自平衡二叉查找树，通过旋转和重着色保持平衡，确保高效执行插入、删除和查找操作，时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中，节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架，用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
土木林森
106 1
LuckiBit
|
2天前
|
算法 编译器 C语言
【C语言】C++ 和 C 的优缺点是什么？
C 和 C++ 是两种强大的编程语言，各有其优缺点。C 语言以其高效性、底层控制和简洁性广泛应用于系统编程和嵌入式系统。C++ 在 C 语言的基础上引入了面向对象编程、模板编程和丰富的标准库，使其适合开发大型、复杂的软件系统。 在选择使用 C 还是 C++ 时，开发者需要根据项目的需求、语言的特性以及团队的技术栈来做出决策。无论是 C 语言还是 C++，了解其优缺点和适用场景能够帮助开发者在实际开发中做出更明智的选择，从而更好地应对挑战，实现项目目标。
LuckiBit
18 0
c的前世今生
|
2月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中，`static`关键字主要用于变量声明，使得该变量的作用域被限制在其被声明的函数内部，且在整个程序运行期间保留其值。而在C++中，除了继承了C的特性外，`static`还可以用于类成员，使该成员被所有类实例共享，同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景，不仅限于控制变量的作用域和生存期。
c的前世今生
59 10
sunrr
|
3月前
|
算法 机器人 C语言
ROS仿真支持C++和C语言
ROS仿真支持C++和C语言
sunrr
77 1
Codelinghu
|
2月前
|
C语言 C++
实现两个变量值的互换[C语言和C++的区别]
实现两个变量值的互换[C语言和C++的区别]
Codelinghu
23 0
monGyrate
|
4月前
|
算法 应用服务中间件 C语言
【C语言】红黑树
【C语言】红黑树
monGyrate
33 1
【C语言】红黑树
蓝易云
|
2月前
|
程序员 C++ 开发者
C++入门教程：掌握函数重载、引用与内联函数的概念
通过上述介绍和实例，我们可以看到，函数重载提供了多态性；引用提高了函数调用的效率和便捷性；内联函数则在保证代码清晰的同时，提高了程序的运行效率。掌握这些概念，对于初学者来说是非常重要的，它们是提升C++编程技能的基石。
蓝易云
23 0
半截诗
|
4月前
|
机器学习/深度学习 C语言
【C语言篇】递归详细介绍（基础概念习题及汉诺塔等进阶问题）
要保持最小的步数，每一次汉诺塔问题（无论是最初还是递归过程中的），如果此时初始柱盘子数为偶数，我们第一步是把最上面的盘子移动到中转柱，如果为奇数，我们第一步则是将其移动到目标柱。
半截诗
84 0
【C语言篇】递归详细介绍（基础概念习题及汉诺塔等进阶问题）
大柏怎么被偷了
|
4月前
|
编译器 Linux C语言
【C++小知识】为什么C语言不支持函数重载，而C++支持
【C++小知识】为什么C语言不支持函数重载，而C++支持
大柏怎么被偷了
50 1