C++之红黑树认识与实现

RBTree

• 一.红黑树的概念
• • 红黑树的结构
• 二.红黑树的定义与特性
• • 一.红黑树的插入操作
  • • 1. 插入节点
    • 2. 修复红黑树
    • 插入操作的步骤
    • • 1. 插入新节点
      • 2. 修复红黑树的性质
      • • 修复逻辑
        • 修复情况
      • 3. 根节点的颜色
    • 代码逻辑解析
  • 二.红黑树的删除操作（作为了解即可）
  • • 1. 删除节点
    • 2. 修复红黑树
  • 三.红黑树的查找操作
  • 四.红黑树的验证
  • • 代码中的检查逻辑
    • • 1. `IsBalance`函数
      • 2. `Check`函数
  • 红黑树 vs AVL树

一.红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

红黑树的结构

// 枚举值表⽰颜⾊ enum Colour{ RED, BLACK};template<class K, class V>struct RBTreeNode{ // 这⾥更新控制平衡也要加⼊parent指针  pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {}};template<class K, class V>class RBTree{ typedef RBTreeNode<K, V> Node;public:private: Node* _root = nullptr;};

二.红黑树的定义与特性

红黑树是一种自平衡的二叉查找树，它满足以下五条基本性质：

1. 节点是红色或黑色：每个节点都有一个颜色属性，红色或黑色。
2. 根节点是黑色：树的根节点必须是黑色。
3. 叶子节点是黑色：叶子节点（即空节点或NULL节点）是黑色。
4. 红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点都是黑色。
5. 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点：这确保了树的平衡性。

这些性质保证了红黑树在插入和删除操作后能够保持大致平衡，从而使得查找、插入和删除操作的时间复杂度都能保持在(O(log n))。

一.红黑树的插入操作

插入操作是红黑树中最复杂的部分之一。插入一个新节点后，可能会破坏红黑树的性质，因此需要通过一系列的调整来恢复这些性质。插入操作可以分为以下几个步骤：

1. 插入节点

首先，将新节点插入到红黑树中，就像在普通二叉查找树中插入一样。新插入的节点会被标记为红色，因为插入红色节点比插入黑色节点更容易保持树的平衡。

2. 修复红黑树

插入红色节点后，可能会违反红黑树的性质4（红色节点的子节点是黑色）。因此，需要通过以下几种情况进行调整：

• 情况1：新节点的父节点是黑色
  这种情况下，插入的红色节点不会破坏红黑树的性质，无需进行任何调整。

• 情况2：新节点的父节点和叔叔节点都是红色
  这种情况下，将父节点和叔叔节点变为黑色，祖父节点变为红色。然后，将祖父节点作为新的当前节点，继续向上调整。

• 情况3：新节点的父节点是红色，叔叔节点是黑色或为空
  这种情况下，不仅仅需要变色，还需要进行旋转来调整。

插入操作的步骤

1. 插入新节点

• 如果树为空（_root == nullptr），直接创建一个黑色节点作为根节点并返回。
• 如果树不为空，从根节点开始，通过比较键值来找到插入位置。如果键值已经存在，则返回false，表示插入失败。
• 找到插入位置后，创建一个红色节点（新节点默认为红色），并将其插入到合适的位置（作为某个节点的左子节点或右子节点）。

2. 修复红黑树的性质

插入红色节点后，可能会违反红黑树的性质（尤其是第4条性质：不能有两个连续的红色节点）。因此需要通过旋转和变色操作来修复。

修复逻辑

• 循环条件：只要当前节点的父节点是红色，就需要进行修复。
• 祖父节点和叔叔节点：
  • 祖父节点是当前节点的父节点的父节点。
  • 叔叔节点是祖父节点的另一个子节点（与父节点不同）。

修复情况

1. 叔叔节点存在且为红色：

   • 父节点和叔叔节点都变色为黑色。
   • 祖父节点变色为红色。
   • 将当前节点更新为祖父节点，继续向上检查。
     

2. 叔叔节点不存在或者为黑色：

   • 如果父节点是祖父节点的左子节点：
     • 如果当前节点是父节点的左子节点：
       • 右旋祖父节点。
       • 父节点变色为黑色，祖父节点变色为红色。
     • 如果当前节点是父节点的右子节点：
       • 左旋父节点。
       • 右旋祖父节点。
       • 当前节点变色为黑色，祖父节点变色为红色。
   • 如果父节点是祖父节点的右子节点：
     • 如果当前节点是父节点的右子节点：
       • 左旋祖父节点。
       • 父节点变色为黑色，祖父节点变色为红色。
     • 如果当前节点是父节点的左子节点：
       • 右旋父节点。
       • 左旋祖父节点。
       • 当前节点变色为黑色，祖父节点变色为红色。
         单旋：
         
         双旋：
         

3. 根节点的颜色

• 最后，确保根节点是黑色。

代码逻辑解析

• 插入新节点：

  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; }}

  从根节点开始，通过比较键值找到插入位置。如果键值已存在，返回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; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { 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) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } }}

  根据父节点和叔叔节点的颜色，以及当前节点的位置，选择合适的旋转和变色操作来修复红黑树的性质。

• 确保根节点为黑色：

  _root->_col = BLACK;

二.红黑树的删除操作（作为了解即可）

删除操作比插入操作更为复杂，因为它可能会破坏红黑树的平衡。删除操作可以分为以下几个步骤：

1. 删除节点

首先，找到需要删除的节点。如果该节点有两个子节点，则需要找到它的后继节点（右子树中的最小节点）来替换它。然后，将该节点的值替换为后继节点的值，并将后继节点删除。

2. 修复红黑树

删除节点后，可能会违反红黑树的性质。需要通过以下几种情况进行调整：

• 情况1：被删除的节点是红色
  这种情况下，直接删除该节点不会破坏红黑树的性质。

• 情况2：被删除的节点是黑色，且其子节点是红色
  这种情况下，将子节点变为黑色，然后删除该节点。

• 情况3：被删除的节点是黑色，且其子节点是黑色
  这种情况下，需要通过一系列复杂的调整来恢复红黑树的性质，包括颜色调整和旋转操作。

三.红黑树的查找操作

按⼆叉搜索树逻辑实现即可，搜索效率为O(logN)

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;}

四.红黑树的验证

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 所有叶子节点（空节点）是黑色。
4. 如果一个节点是红色，则它的两个子节点都是黑色（不能有两个连续的红色节点）。
5. 从任何节点到其每个叶子的所有路径都包含相同数量的黑色节点。

代码中的检查逻辑

1. IsBalance函数

这个函数是入口函数，用于初始化检查过程。

bool IsBalance(){ if (_root == nullptr) return true; // 如果树为空，直接返回true，空树满足红黑树的性质 if (_root->_col == RED) return false; // 根节点必须是黑色，否则直接返回false // 计算从根节点到最左边叶子节点的黑色节点数量作为参考值 int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++refNum; // 如果当前节点是黑色，增加黑色节点计数 cur = cur->_left; // 沿着左子树向下遍历 } // 使用参考值调用Check函数检查整棵树 return Check(_root, 0, refNum);}

• 检查根节点颜色：如果根节点是红色，直接返回false，因为红黑树的根节点必须是黑色。
• 计算参考值refNum：从根节点开始，沿着左子树一直向下，统计路径上的黑色节点数量。这个值将作为后续路径检查的参考值。
• 调用Check函数：使用计算出的refNum，从根节点开始递归检查整棵树。

2. Check函数

这个函数是递归函数，用于检查树的每个路径是否满足红黑树的性质。

bool Check(Node* root, int blackNum, const int refNum){ if (root == nullptr) { // 前序遍历走到空节点，意味着一条路径走完了 if (refNum != blackNum) { cout << \"存在黑色节点的数量不相等的路径\" << endl; return false; // 如果当前路径的黑色节点数量与参考值不同，返回false } return true; } // 检查是否存在连续的红色节点 if (root->_col == RED && root->_parent->_col == RED) { cout << root->_kv.first << \"存在连续的红色节点\" << endl; return false; // 如果当前节点和父节点都是红色，返回false } if (root->_col == BLACK) { blackNum++; // 如果当前节点是黑色，增加黑色节点计数 } // 递归检查左右子树 return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}

• 检查路径结束：如果当前节点是空节点（root == nullptr），说明已经到达路径的末端。此时检查当前路径的黑色节点数量blackNum是否与参考值refNum相等。如果不相等，说明违反了红黑树的第5条性质。
• 检查连续红色节点：如果当前节点是红色，并且它的父节点也是红色，直接返回false，因为这违反了红黑树的第4条性质。
• 统计黑色节点：如果当前节点是黑色，将blackNum加1。
• 递归检查子树：递归调用Check函数，分别检查当前节点的左子树和右子树。只有当左右子树都满足红黑树的性质时，当前节点才满足性质。

bool Check(Node* root, int blackNum, const int refNum){ if (root == nullptr) { // 前序遍历⾛到空时，意味着⼀条路径⾛完了  //cout << blackNum << endl; if (refNum != blackNum) { cout << \"存在⿊⾊结点的数量不相等的路径\" << endl; return false; } return true; } // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了  if (root->_col == RED && root->_parent->_col == RED) { cout << root->_kv.first << \"存在连续的红⾊结点\" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);} bool IsBalance(){ if (_root == nullptr) return true; if (_root->_col == RED) return false; // 参考值  int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } return Check(_root, 0, refNum);}

红黑树 vs AVL树

特性 红黑树 AVL树 平衡严格度 宽松（最长路径≤2×最短） 严格（高度差≤1） 插入/删除 更快（平均更少旋转） 较慢（旋转次数多） 查找效率 稍慢（高度略高） 更快（高度最小化） 适用场景 频繁修改的关联容器（如map） 查询密集型场景