当前位置： 首页 > article >正文

【C++第二十章】红黑树

article 2025/2/23 10:22:47

【C++第二十章】红黑树

红黑树介绍🧐

  红黑树是一种自平衡的二叉搜索树，通过颜色标记和特定规则保持树的平衡性，从而在动态插入、删除等操作中维持较高的效率。它的最长路径不会超过最短路径的两倍，它的查找效率比AVL树更慢(对于CPU来说可以忽略不计)，但是它不会像AVL树那样花费更大的代价去实现严格平衡(旋转)。

1.红黑树与AVL树🔎

特性红黑树AVL树
平衡标准通过颜色规则约束，允许一定不平衡严格平衡（左右子树高度差≤1）
插入/删除效率旋转次数少，调整频率低可能需要多次旋转，调整频率高
查询效率平均稍慢（高度≤2log(n+1)）更快（高度严格为O(log n)）
适用场景频繁插入/删除（如内存数据库、STL Map）查询密集（如字典、静态数据集）
实现复杂度较复杂（需处理颜色标记和多种情况）相对简单（仅维护平衡因子）

2.设计思想🔎

  1. 平衡与效率的折衷：
    红黑树通过放宽平衡条件（允许局部不平衡），减少插入/删除时的调整次数，适合写多读少的场景。AVL树追求绝对平衡，适合读多写少的场景。
  2. 模拟B树结构：
    红黑树可视为一种“二叉化”的B树（如2-3-4树），每个节点隐含多个键值，通过颜色标记合并逻辑，减少树的高度。
  3. 工业界应用：
    • 红黑树：Java的 TreeMap、C++的 std::map、Linux内核调度器。
    • AVL树：Windows内核对象管理、需要快速查找的静态数据库。

  所以，若需要高频插入/删除，我们可以选择红黑树，若需要快速查询，不怎么变动数据，选择AVL树。

3.红黑树的性质🔎

  1. 每个节点不是红色就是黑色。
  2. 根节点一定是黑色的。
  3. 如果一个节点是红色的，则它的两个孩子节点是黑色的。(不能出现连续的红色节点)。
  4. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。(每条路径黑色节点数量相同)。
  5. 每个叶子节点都是黑色的(这里的叶子节点指的是空指针节点，也称NIL节点)

  其中，路径的条数是从根节点到NIL节点来计算的，并且NIL节点的黑色也要统计到每条路径的黑色节点数量中。红黑树的最长和最短路径不一定存在。

1

红黑树插入实现🧐

  红黑树的平衡方式为：直接变色、旋转变色，所以我们还是要用到AVL树中的旋转代码。

1.红黑树的节点定义🔎

enum Color //定义颜色枚举，增加可读性
{
	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; //这里使用的是KV模型
	Color _col; //颜色
	RBTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED) //默认设置为红色，如果默认为黑色，则每次插入必定违反性质4
	{}
};

2.左单旋、右单旋🔎

  与AVL树中一摸一样的方法。

//左单旋
void RotateL(Node* parent)
{
 Node* subR = parent->_right;
 Node* subRL = subR->_left;

 parent->_right = subRL;
 subR->_left = parent;

 Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根

 parent->_parent = subR;
 if (subRL) //subRL不为空才处理
     subRL->_parent = parent;

 if (_root == parent) //当parent就是整个树的根，直接改变
 {
     _root = subR;
     subR->_parent = nullptr;
 }
 else
 {
     //如果不是，结点在父左边就将左边置为subR，否则右边
     if (parentParent->_left == parent)
     {
         parentParent->_left = subR;
     }
     else
     {
         parentParent->_right = subR;
     }
     subR->_parent = parentParent; //父节点也要改变
 }
}

//右单旋
void RotateR(Node* parent)
{
 Node* subL = parent->_left;
 Node* subLR = subL->_right;

 parent->_left = subLR;
 if (subLR) //subLR不为空才处理
     subLR->_parent = parent;
 //放在subL下面，不然parentParent可能为空
 Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根

 subL->_right = parent;
 parent->_parent = subL;

 if (_root == parent) //当parent就是整个树的根，直接改变
 {
     _root = subL;
     subL->_parent = nullptr;
 }
 else
 {
     //如果不是，结点在父左边就将左边置为subL，否则右边
     if (parentParent->_left == parent)
     {
         parentParent->_left = subL;
     }
     else
     {
         parentParent->_right = subL;
     }
     subL->_parent = parentParent; //subL父节点也要改变
 }
}

3.插入🔎

  我们在节点定义时就将默认颜色设置为红色，是因为将默认颜色设置为黑色的话，那么一个正常的红黑树突然插入一个黑色必定违反性质4，则每次都需要调整。

而插入红色时我们进行分析得：

1.当插入节点的父亲节点为黑色时，没有违反任何性质，不需要处理。

2.当插入节点的父亲节点为红色时，违反性质3，需要处理。

由此再次对红黑树分情况讨论：

我们首先约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红

解决方法：

  将p，u改为黑，g改为红，如果g是根节点，那么再改为黑，如果不是根节点且违反性质4，那么将g看为cur，再次进行调整。
image-20250220162857523

情况二：cur为红，p为红，g为黑，u不存在或者u存在且为黑

解决方法：

  如果p是g的左孩子，cur为p的左孩子，则进行右单旋；如果p是g的右孩子，cur为p的右孩子，则进行左单旋。然后进行p、g变色，p变黑，g变红。

image-20250220163422304

情况三：cur为红，p为红，g为黑，u不存在或者存在且为黑。

解决方法：

  如果p是g的左孩子，cur为p的右孩子，则进行左单旋；如果p是g的右孩子，cur为p的左孩子，则进行右单旋。然后转换为情况二处理。
image-20250220170256043

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;
  cur->_parent = parent;
}
else
{
  parent->_left = 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)、
      {
          //    g
          //   p u
          //  c
          //变色
          parent->_col = uncle->_col = BLACK; // 父叔变黑
          grandfather->_col = RED; // 祖父变红

          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
      }
      // 叔节点不存在或为黑（需要旋转）
      else
      {
			// 当前节点是父的左孩子
          if (cur == parent->_left)
          {
              //     g
              //    p
              //   c
              RotateR(grandfather);
              parent->_col = BLACK; // 原父节点变黑
              grandfather->_col = RED; //祖父变红
          }
          // 当前节点是父的右孩子
          else
          {
              //     g
              //    p
              //     c
              RotateL(parent); // 先左旋父节点转换为情况二
              RotateR(grandfather);
              cur->_col = BLACK; //当前节点变黑
              grandfather->_col = RED; //祖父变红
          }
          break; // 旋转后子树平衡，退出循环
      }
  }
  // 父节点是祖父的右孩子
  else
  {
      //    g
      //   u p
      //      c
      Node* uncle = grandfather->_left;
      // 叔节点存在且为红
      if (uncle && uncle->_col == RED)
      {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;

          cur = grandfather;
          parent = cur->_parent;
      }
      // 叔节点不存在或为黑
      else
      {
          // 当前节点是父的右孩子
          if (cur == parent->_right)
          {
              //     g
              //      p
              //       c
              RotateL(grandfather); // 左旋祖父节点
              parent->_col = BLACK;
              grandfather->_col = RED;
          }
          // 当前节点是父的左孩子
          else
          {
              //     g
              //       p
              //     c
              RotateR(parent); // 先右旋父节点转换为情况二
              RotateL(grandfather); // 再左旋祖父节点
              grandfather->_col = RED;
              cur->_col = BLACK;
          }
          break;
      }
  }
}
_root->_col = BLACK; //直接根变黑，不在需要考虑根的颜色问题

return true;
}

4.平衡检测🔎

//根节点到当前结点的黑色数量
bool Check(Node* root, int blacknum, const int refVal)
{
 if (root == nullptr)
 {
     if (blacknum != refVal)
     {
         cout << "存在黑色结点数量不相等的路径!" << endl;
         return false;
     }
     return true;
 }

 if (root->_col == RED && root->_parent->_col == RED)
 {
     //当两个结点都为红，就出问题了
     cout << "有连续的红色" << endl;
     return false;
 }
 if (root->_col == BLACK)
 {
     ++blacknum;
 }
 return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);
}

bool IsBalance()
{
 if (_root == nullptr)
     return true;
 if (_root->_col == RED)
     return false;
 int refVal = 0;
 Node* cur = _root;
 while (cur)
 {
     if (cur->_col == BLACK)
     {
         ++refVal;
     }
     cur = cur->_left;
 }
 int blacknum = 0;
 return Check(_root, blacknum, refVal);
}

结尾👍

  以上便是红黑树的介绍和插入分析，如果有疑问或者建议都可以私信笔者交流，大家互相学习，互相进步！🌹


http://www.kler.cn/a/555557.html

相关文章：

  • Unity 聊天气泡根据文本内容适配
  • 深度学习-2.机械学习基础
  • 影刀RPA中级证书-Excel进阶-开票清单
  • 2025最新智能优化算法：鲸鱼迁徙算法（Whale Migration Algorithm，WMA）求解23个经典函数测试集，MATLAB
  • 访问者模式 Visitor Pattern
  • Elasticsearch 数据建模：从原理到实战的降维打击指南
  • MySQL Binlog 监听：Canal + Spring Boot 实战指南
  • 【分布式理论14】分布式数据库存储：分表分库、主从复制与数据扩容策略
  • 网络协议相关知识有哪些？
  • 一次交换机故障导致的云平台（opensatck+ceph）不可用的记录
  • Compose 定制UI视图
  • Netty入门详解
  • pyside6学习专栏(二):程序图像资源的加载方式
  • 庙算兵棋推演AI开发初探（5-数据处理）
  • 阿里云子账号管理ECS权限配置全指南
  • Canvas进阶-2、可视化应用
  • C# 中关于补位的写法 PadLeft，PadRight 函数
  • 猎板PCB百科——键盘PCB
  • cesium（vue）一些面试问题（包含Three.js）
  • el-tree选中数据重组成树