ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++ 红黑树 [打印本页]

---

作者: 乌市泽哥    时间: 2024-7-24 05:53
标题: C++ 红黑树
目录
  
  ​
  0.媒介
  1.红黑树概念
  2.红黑树性质
  3.红黑树节点定义
  节点属性详解
  4.红黑树结构
  4.1带头节点的红黑树结构
  4.2不带头节点的红黑树结构
  5.红黑树插入节点操作
  5.1 按照二叉搜刮树的规则插入新节点
  5.2 检测新节点插入后，红黑树的性质是否遭到粉碎
  5.2.1 环境一: cur为红，p为红，g为黑，u存在且为红
  5.2.2 环境二: cur为红，p为红，g为黑，u不存在/u存在且为黑（需要单旋）
  5.2.3 环境三: cur为红，p为红，g为黑，u不存在/u存在且为黑（需要双旋）
  6.红黑树删除节点操作
  6.1 按照二叉搜刮树的规则删除节点
  6.2. 检测删除节点后，红黑树的性质是否遭到粉碎，并进行修复
  7.红黑树的性能
  7.1红黑树的复杂度分析
  7.2与 AVL 树的比力
  8.红黑树的迭代器设计
  8.1迭代器结构
  8.2前向迭代（operator++）
  8.3后向迭代（operator--）
  9.红黑树的模拟实现代码
  10.基于红黑树的map模拟实现
  11.结语
  

---

  
  

（图像由AI天生） 
0.媒介

在之前的文章中，我们先容了 C++ 尺度库中的 map 和 set 容器的使用，以及 AVL 树的实现。尽管 AVL 树在均衡性方面表现优秀，但在插入和删除操作频仍的应用中，红黑树（Red-Black Tree）由于其较少的旋转操作次数，每每能提供更优的性能。本篇博客将详细先容红黑树的概念、性质、节点定义、结构、插入与删除操作、性能、迭代器设计，并展示基于红黑树的模拟实现代码及其在 map 容器中的应用。
1.红黑树概念

红黑树（Red-Black Tree）是一种自均衡二叉搜刮树，在每个节点上增长一个存储位表示节点的颜色，可以是红色（Red）或玄色（Black）。红黑树通过对从根到叶子的路径上各个节点的着色方式进行限制，确保没有任何一条路径比其他路径长出两倍，从而实现近似的均衡。
红黑树最早由 Rudolf Bayer 于 1972 年提出，最初被称为对称二叉 B 树（Symmetric Binary B-trees）。厥后，Leonidas J. Guibas 和 Robert Sedgewick 对其进行了改进和推广，正式提出了红黑树的概念。红黑树的设计思想是通过简单的规则和操作，确保树在插入和删除操作后保持均衡，从而提供高效的查找性能。
红黑树广泛应用于各种实际场景中，其性质使得它在实现高效数据结构时具有很大优势。比方：

• STL 容器：C++ 尺度模板库（STL）中的 map 和 set 容器通常基于红黑树实现，以保证快速的插入、删除和查找操作。
  
• 数据库索引：很多数据库系统使用红黑树来实现索引结构，以提高数据检索的服从。
  
• 内核调理：一些操作系统内核使用红黑树来管理进程调理，以确保系统能够高效地处理任务。
  

2.红黑树性质

（图片泉源：知乎@王大帅 特此鸣谢） 
红黑树具有以下五个重要性质，这些性质保证了红黑树的均衡性和高效性：

• 每个节点不是红色就是玄色：
  
  
  
  • 红黑树的每个节点都有一个颜色属性，这个颜色要么是红色，要么是玄色。通过颜色属性的限制，红黑树能够在结构上保持均衡。
    
  
  
• 根节点是玄色的：
  
  
  
  • 红黑树的根节点始终是玄色的。这一性质确保了树的均衡性从根节点开始，并且为树的其他均衡规则提供了底子。
    
  
  
• 如果一个节点是红色的，则它的两个孩子节点是玄色的：
  
  
  
  • 这一性质制止了两个连续的红色节点出如今从根到叶子的路径上。通过限制红色节点的排列方式，红黑树能够防止路径长度的不均衡增长。
    
  
  
• 对于每个节点，从该节点到其全部子女叶节点的简单路径上，均包罗相同数目的玄色节点：
  
  
  
  • 这一性质也称为玄色均衡性（black-height）。它保证了从任一节点到其叶节点的路径长度相似，从而使红黑树接近均衡。这意味着在插入或删除节点时，红黑树可以通过重新着色和旋转操作来恢复均衡，而不需要像 AVL 树那样频仍调解。
    
  
  
• 每个叶子节点都是玄色的（此处的叶子节点指的是空节点）：
  
  
  
  • 红黑树中的叶子节点实际上是树中的空节点（NIL 节点），这些节点也被视为玄色。即使树中没有显式存储这些 NIL 节点，明白它们的存在对于分析红黑树的均衡性是至关重要的。
    
  
  

3.红黑树节点定义

在红黑树中，每个节点不仅存储数据，还包罗指向其子节点和父节点的指针，以及节点的颜色属性。下面是红黑树节点的定义代码：

1. enum Color { RED, BLACK };
3. template<class T>
4. struct RBTreeNode
5. {
6.     T _data;  // 存储的数据
7.     RBTreeNode<T>* _left;  // 指向左子节点的指针
8.     RBTreeNode<T>* _right;  // 指向右子节点的指针
9.     RBTreeNode<T>* _parent;  // 指向父节点的指针
10.     Color _color;  // 节点的颜色
12.     // 构造函数，初始化节点的数据和指针，默认颜色为红色
13.     RBTreeNode(const T& data)
14.         : _data(data)
15.         , _left(nullptr)
16.         , _right(nullptr)
17.         , _parent(nullptr)
18.         , _color(RED)
19.     {}
20. };

复制代码

节点属性详解

• _data:
  
  
  
  • 存储节点的数据。这个数据可以是任何范例，由模板参数 T 决定。
    
  
  
• _left:
  
  
  
  • 指向左子节点的指针。如果左子节点不存在，则该指针为 nullptr。
    
  
  
• _right:
  
  
  
  • 指向右子节点的指针。如果右子节点不存在，则该指针为 nullptr。
    
  
  
• _parent:
  
  
  
  • 指向父节点的指针。这在红黑树的插入和删除操作中非常重要，因为这些操作需要通过父节点来进行旋转和重新着色。
    
  
  
• _color:
  
  
  
  • 节点的颜色属性，可以是红色（RED）或玄色（BLACK）。颜色属性在保持红黑树的均衡性中起到关键作用。
    
  • 在构造函数中，节点的颜色被默认设置为红色（RED）。这是因为插入新节点时，默认环境下设置为红色更易于保持树的均衡，并通过后续的旋转和重新着色操作来调解树的结构。
    
  
  

4.红黑树结构

红黑树可以带有头节点（header）或者不带头节点。在带头节点的红黑树结构中，头节点提供了便利的指针，可以快速访问树的最小节点、最大节点以及根节点。这种设计在实现中有助于简化边界环境的处理。
4.1带头节点的红黑树结构

带头节点的红黑树使用一个特殊的头节点（header），它的颜色通常设为红色，并且其指针指向树中的特殊节点。详细来说，头节点的指针结构如下：

• header->parent 指向树的根节点。
  
• header->left 指向树中最小的节点（leftmost）。
  
• header->right 指向树中最大的节点（rightmost）。
  

4.2不带头节点的红黑树结构

不带头节点的红黑树则不使用额外的头节点，直接通过根节点进行操作。在这种结构中，树的边界处理和遍历操作相对复杂一些，因为没有头节点来存储额外的指针信息。
为定义方便起见，后文中红黑树结构采用无头结点方式。
5.红黑树插入节点操作

红黑树是在二叉搜刮树的底子上加上其均衡限制条件，因此红黑树的插入操作可以分为两个步骤：

• 按照二叉搜刮树的规则插入新节点
  
• 检测新节点插入后，红黑树的性质是否遭到粉碎，并进行修复
  

5.1 按照二叉搜刮树的规则插入新节点

首先，我们按照二叉搜刮树的规则找到新节点的插入位置，并将其插入到树中。插入的新节点默认颜色为红色。以下是详细的实现代码：

1. pair<Iterator, bool> Insert(const T& data) {
2.     if (_root == nullptr) {
3.         _root = new Node(data);
4.         _root->_color = BLACK;  // 根节点必须是黑色
5.         return make_pair(Iterator(_root, _root), true);
6.     }
8.     KeyOfT kot;  // 获取键值
9.     Node* parent = nullptr;
10.     Node* cur = _root;
11.     while (cur) {
12.         if (kot(cur->_data) == kot(data)) {
13.             return make_pair(Iterator(cur, _root), false);  // 如果数据已经存在，直接返回
14.         }
15.         parent = cur;
16.         if (kot(cur->_data) > kot(data)) {
17.             cur = cur->_left;
18.         } else {
19.             cur = cur->_right;
20.         }
21.     }
23.     cur = new Node(data);
24.     Node* newNode = cur;
25.     if (KeyOfT()(data) < KeyOfT()(parent->_data)) {
26.         parent->_left = cur;
27.     } else {
28.         parent->_right = cur;
29.     }
30.     cur->_parent = parent;
32.     // 检测并修复红黑树性质，伪代码
33.     FixInsert(cur);
35.     return make_pair(Iterator(newNode, _root), true);
36. }

复制代码

5.2 检测新节点插入后，红黑树的性质是否遭到粉碎

在插入节点后，可能会粉碎红黑树的性质，需要进行修复。红黑树的性质有五条：

• 每个节点不是红色就是玄色。
  
• 根节点是玄色的。
  
• 如果一个节点是红色的，则它的两个孩子节点是玄色的。
  
• 对于每个节点，从该节点到其全部子女叶节点的简单路径上，均包罗相同数目的玄色节点。
  
• 每个叶子节点都是玄色的（此处的叶子节点指的是空节点）。
  

为了修复红黑树的性质，我们需要考虑以下几种环境：

• 环境 1：新节点的父节点是玄色的。这种环境下，插入操作不会粉碎红黑树的任何性质，因此不需要进行任何操作。
  
• 环境 2：新节点的父节点是红色的。由于红黑树的性质 3 被粉碎（两个连续的红色节点），我们需要进行修复操作。详细分为以下几种子环境：
  
  
  
  • 环境 2.1：新节点的叔叔节点（父节点的兄弟节点）是红色的。这种环境下，父节点和叔叔节点都变为玄色，祖父节点变为红色，然后将当前节点指向祖父节点，继续检测祖父节点。
    
  • 环境 2.2：新节点的叔叔节点是玄色的，且新节点是父节点的右孩子。此时，我们需要进行左旋操作，将新节点变成父节点，然后进行环境 2.3 的处理。
    
  • 环境 2.3：新节点的叔叔节点是玄色的，且新节点是父节点的左孩子。这种环境下，我们进行右旋操作，将父节点变成新节点，调解颜色后结束修复。
    
  
  

我们不妨约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。
5.2.1 环境一: cur为红，p为红，g为黑，u存在且为红

在这种环境下，当前节点cur的父节点p和叔叔节点u都是红色，祖父节点g是玄色。这种环境粉碎了红黑树性质3（红节点的子节点必须是玄色）。解决方式如下：

• 将p和u改为玄色。
  
• 将g改为红色。
  
• 将当前节点cur移动到g，继续向上调解。
  

1. void FixInsert(Node* node) {
2.     Node* parent = nullptr;
3.     Node* grandFather = nullptr;
5.     // 当前节点不在根节点且其父节点为红色时，需要调整
6.     while (node != _root && node->_parent->_color == RED) {
7.         parent = node->_parent;
8.         grandFather = parent->_parent;
10.         if (parent == grandFather->_left) {
11.             Node* uncle = grandFather->_right;
13.             if (uncle && uncle->_color == RED) {
14.                 // 情况 1: 叔叔是红色
15.                 parent->_color = BLACK;
16.                 uncle->_color = BLACK;
17.                 grandFather->_color = RED;
18.                 node = grandFather; // 将当前节点上移到祖父节点继续调整
19.             } else {
20.                 // 处理情况 2 和 3
21.             }
22.         } else {
23.             Node* uncle = grandFather->_left;
25.             if (uncle && uncle->_color == RED) {
26.                 // 情况 1: 叔叔是红色
27.                 parent->_color = BLACK;
28.                 uncle->_color = BLACK;
29.                 grandFather->_color = RED;
30.                 node = grandFather; // 将当前节点上移到祖父节点继续调整
31.             } else {
32.                 // 处理情况 2 和 3
33.             }
34.         }
35.     }
37.     _root->_color = BLACK;  // 根节点始终是黑色
38. }

复制代码

5.2.2 环境二: cur为红，p为红，g为黑，u不存在/u存在且为黑（需要单旋）

在这种环境下，当前节点cur的父节点p是红色，叔叔节点u是玄色或不存在。根据cur和p的相对位置，需要进行单旋操作。

• 如果cur是p的右子节点，p是g的左子节点，需要进行左旋。
  
• 如果cur是p的左子节点，p是g的右子节点，需要进行右旋。
  

1. void FixInsert(Node* node) {
2.     Node* parent = nullptr;
3.     Node* grandFather = nullptr;
5.     // 当前节点不在根节点且其父节点为红色时，需要调整
6.     while (node != _root && node->_parent->_color == RED) {
7.         parent = node->_parent;
8.         grandFather = parent->_parent;
10.         if (parent == grandFather->_left) {
11.             Node* uncle = grandFather->_right;
13.             if (uncle && uncle->_color == RED) {
14.                 parent->_color = BLACK;
15.                 uncle->_color = BLACK;
16.                 grandFather->_color = RED;
17.                 node = grandFather; // 将当前节点上移到祖父节点继续调整
18.             } else {
19.                 if (node == parent->_right) {
20.                     // 情况 2: 叔叔是黑色且当前节点是右子节点，需要左旋
21.                     RotateL(parent);
22.                     node = parent;
23.                     parent = node->_parent;
24.                 }
25.                 // 单旋后调整颜色
26.                 RotateR(grandFather);
27.                 swap(parent->_color, grandFather->_color);
28.                 node = parent;
29.             }
30.         } else {
31.             Node* uncle = grandFather->_left;
33.             if (uncle && uncle->_color == RED) {
34.                 parent->_color = BLACK;
35.                 uncle->_color = BLACK;
36.                 grandFather->_color = RED;
37.                 node = grandFather; // 将当前节点上移到祖父节点继续调整
38.             } else {
39.                 if (node == parent->_left) {
40.                     // 情况 2: 叔叔是黑色且当前节点是左子节点，需要右旋
41.                     RotateR(parent);
42.                     node = parent;
43.                     parent = node->_parent;
44.                 }
45.                 // 单旋后调整颜色
46.                 RotateL(grandFather);
47.                 swap(parent->_color, grandFather->_color);
48.                 node = parent;
49.             }
50.         }
51.     }
53.     _root->_color = BLACK;  // 根节点始终是黑色
54. }

复制代码

5.2.3 环境三: cur为红，p为红，g为黑，u不存在/u存在且为黑（需要双旋）

在这种环境下，当前节点cur的父节点p是红色，叔叔节点u是玄色或不存在。根据cur和p的相对位置，需要进行双旋操作。

• 如果cur是p的左子节点，p是g的左子节点，且cur是p的右子节点（需要右旋后左旋）。
  
• 如果cur是p的右子节点，p是g的右子节点，且cur是p的左子节点（需要左旋后右旋）。
  

1. void FixInsert(Node* node) {
2.     Node* parent = nullptr;
3.     Node* grandFather = nullptr;
5.     // 当前节点不在根节点且其父节点为红色时，需要调整
6.     while (node != _root && node->_parent->_color == RED) {
7.         parent = node->_parent;
8.         grandFather = parent->_parent;
10.         if (parent == grandFather->_left) {
11.             Node* uncle = grandFather->_right;
13.             if (uncle && uncle->_color == RED) {
14.                 parent->_color = BLACK;
15.                 uncle->_color = BLACK;
16.                 grandFather->_color = RED;
17.                 node = grandFather; // 将当前节点上移到祖父节点继续调整
18.             } else {
19.                 if (node == parent->_right) {
20.                     // 情况 3: 叔叔是黑色且当前节点是右子节点，需要左旋后右旋
21.                     RotateL(parent);
22.                     node = parent;
23.                     parent = node->_parent;
24.                 }
25.                 // 双旋后调整颜色
26.                 RotateR(grandFather);
27.                 swap(parent->_color, grandFather->_color);
28.                 node = parent;
29.             }
30.         } else {
31.             Node* uncle = grandFather->_left;
33.             if (uncle && uncle->_color == RED) {
34.                 parent->_color = BLACK;
35.                 uncle->_color = BLACK;
36.                 grandFather->_color = RED;
37.                 node = grandFather; // 将当前节点上移到祖父节点继续调整
38.             } else {
39.                 if (node == parent->_left) {
40.                     // 情况 3: 叔叔是黑色且当前节点是左子节点，需要右旋后左旋
41.                     RotateR(parent);
42.                     node = parent;
43.                     parent = node->_parent;
44.                 }
45.                 // 双旋后调整颜色
46.                 RotateL(grandFather);
47.                 swap(parent->_color, grandFather->_color);
48.                 node = parent;
49.             }
50.         }
51.     }
53.     _root->_color = BLACK;  // 根节点始终是黑色
54. }

复制代码

6.红黑树删除节点操作

在红黑树中，删除节点操作分为两个部分：首先按照二叉搜刮树的规则删除节点，然后通过调解（旋转和重新着色）来修复可能粉碎的红黑树性质。
6.1 按照二叉搜刮树的规则删除节点

删除节点时，首先找到要删除的节点，并进行删除操作。如果节点有两个子节点，需要找到后继节点更换被删除节点，并删除后继节点。

1. Node* Delete(Node* root, const T& data) {
2.     // 查找并删除节点，返回新根节点
3.     Node* z = FindNode(root, data);  // 找到要删除的节点
4.     if (!z) return root;  // 节点不存在，直接返回
6.     Node* y = z;
7.     Node* x;
8.     Color y_original_color = y->_color;
10.     if (z->_left == nullptr) {
11.         x = z->_right;
12.         Transplant(root, z, z->_right);
13.     } else if (z->_right == nullptr) {
14.         x = z->_left;
15.         Transplant(root, z, z->_left);
16.     } else {
17.         y = Minimum(z->_right);  // 找到后继节点
18.         y_original_color = y->_color;
19.         x = y->_right;
20.         if (y->_parent == z) {
21.             if (x) x->_parent = y;
22.         } else {
23.             Transplant(root, y, y->_right);
24.             y->_right = z->_right;
25.             y->_right->_parent = y;
26.         }
27.         Transplant(root, z, y);
28.         y->_left = z->_left;
29.         y->_left->_parent = y;
30.         y->_color = z->_color;
31.     }
33.     delete z;
35.     if (y_original_color == BLACK) {
36.         FixDelete(root, x);
37.     }
39.     return root;
40. }

复制代码

6.2. 检测删除节点后，红黑树的性质是否遭到粉碎，并进行修复

删除节点后，可能会粉碎红黑树的性质，需要进行修复。常见的调解环境如下：
环境一：当前节点x是红色或其父节点是红色

• 不需要做任何调解，因为删除一个红色节点不会粉碎红黑树的性质。
  

环境二：当前节点x是玄色，其兄弟节点是红色

• 将父节点变为红色，兄弟节点变为玄色，然后进行旋转，转为环境三或四进行处理。
  

环境三：当前节点x是玄色，其兄弟节点是玄色，兄弟节点的子节点都是玄色

• 将兄弟节点变为红色，继续向上调解，直到根节点或调解完毕。
  

环境四：当前节点x是玄色，其兄弟节点是玄色，兄弟节点的一个子节点是红色

• 根据兄弟节点子节点的位置，进行旋转和重新着色。
  

7.红黑树的性能

7.1红黑树的复杂度分析

红黑树是一种自均衡二叉搜刮树，能够确保在最坏环境下的操作复杂度为O(logn)，此中 n 是树中节点的数目。这种性能保证源于红黑树的均衡性质，使得树的高度始终保持在 O(logn) 范围内。以下是对红黑树重要操作的复杂度分析：

• 查找：
  
  
  
  • 红黑树的查找操作与二叉搜刮树雷同，通过比力节点值从根节点逐层向下查找。由于红黑树的高度最多为 O(logn)，因此查找操作的复杂度为O(logn)。
    
  
  
• 插入：
  
  
  
  • 插入操作首先按照二叉搜刮树的规则找到插入位置，复杂度为O(logn)。然后，通过重新着色和旋转来保持红黑树的均衡。每次插入操作最多需要进行两次旋转，因此插入操作的复杂度为 O(logn)。
    
  
  
• 删除：
  
  
  
  • 删除操作也首先按照二叉搜刮树的规则找到要删除的节点，复杂度为 O(logn)。删除后，通过重新着色和旋转来保持红黑树的均衡。每次删除操作最多需要进行三次旋转，因此删除操作的复杂度为O(logn)。
    
  
  

7.2与 AVL 树的比力

红黑树与 AVL 树都是自均衡二叉搜刮树，但它们在详细实现和性能特性上有所不同。以下是两者的比力：

• 均衡性：
  
  
  
  • AVL 树：高度均衡，确保每个节点的左右子树高度差最多为 1。这意味着 AVL 树通常比红黑树更加均衡。
    
  • 红黑树：通过颜色和旋转规则保持均衡，但允许更松散的均衡条件。这使得红黑树的高度可能稍高于 AVL 树，但仍旧在 O(logn) 范围内。
    
  
  
• 插入和删除操作：
  
  
  
  • AVL 树：由于严格的均衡条件，插入和删除操作可能需要进行较多的旋转。插入操作的平均旋转次数为 1.44 次，删除操作的平均旋转次数为 2.44 次。
    
  • 红黑树：由于较为宽松的均衡条件，插入和删除操作所需的旋转次数通常较少。插入操作最多需要进行两次旋转，删除操作最多需要进行三次旋转。
    
  
  
• 查找性能：
  
  
  
  • AVL 树：由于更严格的均衡条件，AVL 树的查找性能在理论上优于红黑树。然而，在实际应用中，这种性能差异通常并不显着，尤其是在数据规模较大时。
    
  
  
• 实用场景：
  
  
  
  • AVL 树：实用于查找操作较为频仍、插入和删除操作较少的场景，如数据库索引和只读数据结构。
    
  • 红黑树：实用于插入和删除操作较为频仍的场景，如操作系统的任务调理和动态集合操作。红黑树在这些场景中由于旋转次数较少，能够提供更好的整体性能。
    
  
  

8.红黑树的迭代器设计

红黑树的迭代器设计需要支持遍历树中的全部节点，并能够实行前向和后向遍历操作。迭代器在红黑树中的作用雷同于指针，能够指向树中的节点，并提供便捷的节点访问和遍历功能。
8.1迭代器结构

红黑树的迭代器通过模板参数支持泛型，并包罗当前节点和树根节点的指针。下面是迭代器的定义：

1. template<class T, class Ref, class Ptr>
2. struct RBTreeIterator
3. {
4.         typedef RBTreeNode<T> Node;
5.         typedef RBTreeIterator<T, Ref, Ptr> Self;
7.         Node* _node;  // 当前节点
8.         Node* _root;  // 树根节点
10.         RBTreeIterator(Node* node, Node* root)
11.                 : _node(node)
12.                 , _root(root)
13.         {}
15.         Self& operator++();//待实现
16.         Self& operator--();//待实现
18.         Ref operator*()
19.         {
20.                 return _node->_data;
21.         }
23.         Ptr operator->()
24.         {
25.                 return &_node->_data;
26.         }
28.         bool operator!= (const Self& s)
29.         {
30.                 return _node != s._node;
31.         }
33.         bool operator== (const Self& s)
34.         {
35.                 return _node == s._node;
36.         }
37. };

复制代码

8.2前向迭代（operator++）

前向迭代操作用于遍历树的下一个节点。根据当前节点的位置，前向迭代的实现分为两种环境：

• 当前节点有右子树：如果当前节点有右子树，则下一个节点是右子树的最左节点。
  
• 当前节点没有右子树：如果当前节点没有右子树，则沿着父节点向上移动，直到找到一个节点，该节点是其父节点的左子节点。这个父节点就是下一个节点。
  

1. Self& operator++()
2. {
3.         if (_node->_right)
4.         {
5.                 // 当前节点有右子树，找到右子树的最左节点
6.                 Node* leftMost = _node->_right;
7.                 while (leftMost->_left)
8.                 {
9.                         leftMost = leftMost->_left;
10.                 }
11.                 _node = leftMost;
12.         }
13.         else
14.         {
15.                 // 当前节点没有右子树，向上找第一个是左子节点的祖先
16.                 Node* cur = _node;
17.                 Node* parent = cur->_parent;
18.                 while (parent && cur == parent->_right)
19.                 {
20.                         cur = parent;
21.                         parent = cur->_parent;
22.                 }
23.                 _node = parent;
24.         }
26.         return *this;
27. }

复制代码

8.3后向迭代（operator--）

后向迭代操作用于遍历树的前一个节点。根据当前节点的位置，后向迭代的实现分为三种环境：

• 当前节点是 end()：如果当前节点是 end()（空节点），则下一个节点是整棵树的最右节点。
  
• 当前节点有左子树：如果当前节点有左子树，则下一个节点是左子树的最右节点。
  
• 当前节点没有左子树：如果当前节点没有左子树，则沿着父节点向上移动，直到找到一个节点，该节点是其父节点的右子节点。这个父节点就是下一个节点。
  

1. Self& operator--()
2. {
3.         if (_node == nullptr) // end()
4.         {
5.                 // 当前节点是end()，找到最右节点
6.                 Node* rightMost = _root;
7.                 while (rightMost && rightMost->_right)
8.                 {
9.                         rightMost = rightMost->_right;
10.                 }
11.                 _node = rightMost;
12.         }
13.         else if (_node->_left)
14.         {
15.                 // 当前节点有左子树，找到左子树的最右节点
16.                 Node* rightMost = _node->_left;
17.                 while (rightMost->_right)
18.                 {
19.                         rightMost = rightMost->_right;
20.                 }
21.                 _node = rightMost;
22.         }
23.         else
24.         {
25.                 // 当前节点没有左子树，向上找第一个是右子节点的祖先
26.                 Node* cur = _node;
27.                 Node* parent = cur->_parent;
28.                 while (parent && cur == parent->_left)
29.                 {
30.                         cur = parent;
31.                         parent = cur->_parent;
32.                 }
33.                 _node = parent;
34.         }
36.         return *this;
37. }

复制代码

9.红黑树的模拟实现代码

1. #pragma once
2. #include<iostream>
3. #include<algorithm>
4. #include<cassert>
5. #include<vector>
6. using namespace std;
8. enum Color { RED, BLACK };
10. template<class T>
11. struct RBTreeNode
12. {
13.         T _data;
14.         RBTreeNode<T>* _left;
15.         RBTreeNode<T>* _right;
16.         RBTreeNode<T>* _parent;
17.         Color _color;
19.         RBTreeNode(const T& data)
20.                 :_data(data)
21.                 , _left(nullptr)
22.                 , _right(nullptr)
23.                 , _parent(nullptr)
24.                 , _color(RED)
25.         {}
26. };
28. template<class T, class Ref, class Ptr>
29. struct RBTreeIterator
30. {
31.         typedef RBTreeNode<T> Node;
32.         typedef RBTreeIterator<T, Ref, Ptr> Self;
34.         Node* _node;
35.         Node* _root;
37.         RBTreeIterator(Node* node, Node* root)
38.                 :_node(node)
39.                 , _root(root)
40.         {}
42.         Self& operator++()
43.         {
44.                 if (_node->_right)
45.                 {
46.                         // 右不为空，右子树最左节点就是中序第一个
47.                         Node* leftMost = _node->_right;
48.                         while (leftMost->_left)
49.                         {
50.                                 leftMost = leftMost->_left;
51.                         }
53.                         _node = leftMost;
54.                 }
55.                 else
56.                 {
57.                         // 孩子是父亲左的那个祖先
58.                         Node* cur = _node;
59.                         Node* parent = cur->_parent;
60.                         while (parent && cur == parent->_right)
61.                         {
62.                                 cur = parent;
63.                                 parent = cur->_parent;
64.                         }
66.                         _node = parent;
67.                 }
69.                 return *this;
70.         }
72.         Self& operator--()
73.         {
74.                 if (_node == nullptr) // end()
75.                 {
76.                         // --end()，特殊处理，走到中序最后一个节点，整棵树的最右节点
77.                         Node* rightMost = _root;
78.                         while (rightMost && rightMost->_right)
79.                         {
80.                                 rightMost = rightMost->_right;
81.                         }
83.                         _node = rightMost;
84.                 }
85.                 else if (_node->_left)
86.                 {
87.                         // 左子树不为空，中序左子树最后一个
88.                         Node* rightMost = _node->_left;
89.                         while (rightMost->_right)
90.                         {
91.                                 rightMost = rightMost->_right;
92.                         }
94.                         _node = rightMost;
95.                 }
96.                 else
97.                 {
98.                         // 孩子是父亲右的那个祖先
99.                         Node* cur = _node;
100.                         Node* parent = cur->_parent;
101.                         while (parent && cur == parent->_left)
102.                         {
103.                                 cur = parent;
104.                                 parent = cur->_parent;
105.                         }
107.                         _node = parent;
109.                 }
111.                 return *this;
112.         }
114.         Ref operator*()
115.         {
116.                 return _node->_data;
117.         }
119.         Ptr operator->()
120.         {
121.                 return &_node->_data;
122.         }
124.         bool operator!= (const Self& s)
125.         {
126.                 return _node != s._node;
127.         }
129.         bool operator== (const Self& s)
130.         {
131.                 return _node == s._node;
132.         }
133. };
135. template<class K, class T,class KeyOfT>
136. class RBTree
137. {
138.         typedef RBTreeNode<T> Node;
139. private:
140.         Node* _root = nullptr;
141. public:
142.         typedef RBTreeIterator<T, T&, T*> Iterator;
143.         typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
145.         Iterator Begin()
146.         {
147.                 Node* cur = _root;
148.                 while (cur && cur->_left)
149.                 {
150.                         cur = cur->_left;
151.                 }
153.                 return Iterator(cur, _root);
154.         }
156.         Iterator End()
157.         {
158.                 return Iterator(nullptr, _root);
159.         }
161.         ConstIterator Begin() const
162.         {
163.                 Node* cur = _root;
164.                 while (cur && cur->_left)
165.                 {
166.                         cur = cur->_left;
167.                 }
169.                 return ConstIterator(cur, _root);
170.         }
172.         ConstIterator End() const
173.         {
174.                 return ConstIterator(nullptr, _root);
175.         }
177.         RBTree() = default;
178.         RBTree(const RBTree& t)
179.         {
180.                 _root = _Copy(t._root);
181.         }
183.         RBTree& operator=(RBTree t)
184.         {
185.                 swap(_root, t._root);//交换根节点
186.                 return *this;
187.         }
189.         ~RBTree()
190.         {
191.                 _Destroy(_root);
192.                 _root = nullptr;
193.         }
195.         pair<Iterator, bool> Insert(const T& data)
196.         {
197.                 if (_root == nullptr)
198.                 {
199.                         _root = new Node(data);
200.                         _root->_color = BLACK;
201.                         return make_pair(Iterator(_root, _root), true);
202.                 }
204.                 KeyOfT kot;//获取键值
205.                 Node* parent = nullptr;
206.                 Node* cur = _root;
207.                 while (cur)
208.                 {
209.                         if (kot(cur->_data) == kot(data))
210.                         {
211.                                 return make_pair(Iterator(cur, _root), false);
212.                         }
213.                         parent = cur;
214.                         if (kot(cur->_data) > kot(data))
215.                         {
216.                                 cur = cur->_left;
217.                         }
218.                         else //kot(cur->_data) > kot(data)
219.                         {
220.                                 cur = cur->_right;
221.                         }
222.                 }
224.                 cur = new Node(data);
225.                 Node* newNode = cur;
226.                 if (KeyOfT()(data) < KeyOfT()(parent->_data))
227.                 {
228.                         parent->_left = cur;
229.                 }
230.                 else
231.                 {
232.                         parent->_right = cur;
233.                 }
234.                 cur->_parent = parent;
236.                 while (parent && parent->_color == RED)
237.                 {
238.                         Node* grandFather = parent->_parent;
239.                         //   g
240.                         //  / \
241.                         // p   u
242.                         if (parent == grandFather->_left)
243.                         {
244.                                 Node* uncle = grandFather->_right;
245.                                 if (uncle && uncle->_color == RED)
246.                                 {
247.                                         // 叔叔是红色，变色再继续向上调整
248.                                         parent->_color = BLACK;
249.                                         uncle->_color = BLACK;
250.                                         grandFather->_color = RED;
252.                                         cur = grandFather;
253.                                         parent = cur->_parent;
254.                                 }
255.                                 else
256.                                 {
257.                                         // 叔叔是黑色/叔叔为空，旋转+变色
258.                                         if (cur == parent->_left)
259.                                         {
260.                                                 //    g
261.                                                 //   / \
262.                                                 //  p   u
263.                                                 // /
264.                                                 //c
265.                                                 RotateR(grandFather);
266.                                                 parent->_color = BLACK;
267.                                                 grandFather->_color = RED;
268.                                         }
269.                                         else
270.                                         {
271.                                                 //    g
272.                                                 //   / \
273.                                                 //  p   u
274.                                                 //   \
275.                                                 //    c
276.                                                 RotateL(parent);
277.                                                 RotateR(grandFather);
278.                                                 cur->_color = BLACK;
279.                                                 grandFather->_color = RED;
280.                                         }
281.                                         break;
282.                                 }
283.                         }
284.                         else
285.                         {
286.                                 //   g
287.                                 //  / \
288.                                 // u   p
289.                                 Node* uncle = grandFather->_left;
290.                                 // 叔叔是红色，变色再继续向上调整
291.                                 if (uncle && uncle->_color == RED)
292.                                 {
293.                                         parent->_color = BLACK;
294.                                         uncle->_color = BLACK;
295.                                         grandFather->_color = RED;
297.                                         cur = grandFather;
298.                                         parent = cur->_parent;
299.                                 }
300.                                 else // 叔叔是黑色/叔叔为空，旋转+变色
301.                                 {
302.                                         //          g
303.                                         //         / \
304.                                         //        u   p
305.                                         //             \
306.                                         //              c
307.                                         if (cur == parent->_right)
308.                                         {
309.                                                 RotateL(grandFather);
310.                                                 parent->_color = BLACK;
311.                                                 grandFather->_color = RED;
312.                                         }
313.                                         else
314.                                         {
315.                                                 //          g
316.                                                 //         / \
317.                                                 //        u   p
318.                                                 //           /
319.                                                 //          c
320.                                                 RotateR(parent);
321.                                                 //          g
322.                                                 //         / \
323.                                                 //        u   c
324.                                                 //             \
325.                                                 //              p
326.                                                 RotateL(grandFather);
327.                                                 cur->_color = BLACK;
328.                                                 grandFather->_color = RED;
329.                                         }
330.                                         break;
331.                                 }
332.                         }
333.                 }
334.                 _root->_color = BLACK;
335.                 return make_pair(Iterator(newNode, _root), true);
336.         }
337.         void InOrder()
338.         {
339.                 _InOrder(_root);
340.                 cout << endl;
341.         }
342.         int Size()
343.         {
344.                 return _Size(_root);
345.         }
346.         int Height()
347.         {
348.                 return _Height(_root);
349.         }
350. private:
351.         Node* _Copy(Node* root)
352.         {
353.                 if (root == nullptr)
354.                         return nullptr;
355.                 Node* newRoot = new Node(root->_data);
356.                 newRoot->_color = root->_color;
357.                 newRoot->_left = _Copy(root->_left);
358.                 newRoot->_right = _Copy(root->_right);
359.                 if (newRoot->_left)
360.                         newRoot->_left->_parent = newRoot;
361.                 if (newRoot->_right)
362.                         newRoot->_right->_parent = newRoot;
363.                 return newRoot;
364.         }
366.         void _Destroy(Node* root)
367.         {
368.                 if (root == nullptr)
369.                         return;
370.                 _Destroy(root->_left);
371.                 _Destroy(root->_right);
372.                 delete root;
373.         }
374.         void _InOrder(Node* root)
375.         {
376.                 if (root == nullptr)
377.                         return;
379.                 _InOrder(root->_left);
380.                 //cout << root->_kv.first << " " << root->_kv.second << endl;
381.                 cout<<root->_data<<" ";
382.                 _InOrder(root->_right);
383.         }
384.         int _Size(Node* root)
385.         {
386.                 if (root == nullptr)
387.                         return 0;
388.                 return 1 + _Size(root->_left) + _Size(root->_right);
389.         }
390.         int _Height(Node* root)
391.         {
392.                 if (root == nullptr)
393.                         return 0;
394.                 return 1 + max(_Height(root->_left), _Height(root->_right));
395.         }
396.         void RotateL(Node* parent)
397.         {
398.                 Node* subR = parent->_right;
399.                 Node* subRL = subR->_left;
401.                 parent->_right = subRL;
402.                 if (subRL)
403.                         subRL->_parent = parent;
405.                 Node* parentParent = parent->_parent;
407.                 subR->_left = parent;
408.                 parent->_parent = subR;
410.                 if (parentParent == nullptr)
411.                 {
412.                         _root = subR;
413.                         subR->_parent = nullptr;
414.                 }
415.                 else
416.                 {
417.                         if (parent == parentParent->_left)
418.                         {
419.                                 parentParent->_left = subR;
420.                         }
421.                         else
422.                         {
423.                                 parentParent->_right = subR;
424.                         }
426.                         subR->_parent = parentParent;
427.                 }
428.         }
429.         void RotateR(Node* parent)
430.         {
431.                 Node* subL = parent->_left;
432.                 Node* subLR = subL->_right;
434.                 parent->_left = subLR;
435.                 if (subLR)
436.                         subLR->_parent = parent;
438.                 Node* parentParent = parent->_parent;
440.                 subL->_right = parent;
441.                 parent->_parent = subL;
443.                 if (parentParent == nullptr)
444.                 {
445.                         _root = subL;
446.                         subL->_parent = nullptr;
447.                 }
448.                 else
449.                 {
450.                         if (parent == parentParent->_left)
451.                         {
452.                                 parentParent->_left = subL;
453.                         }
454.                         else
455.                         {
456.                                 parentParent->_right = subL;
457.                         }
459.                         subL->_parent = parentParent;
460.                 }
461.         }
462. };

复制代码

10.基于红黑树的map模拟实现

以下是基于红黑树实现的 map 类的代码，此中复用了红黑树的实现。这里的 map 类使用红黑树来存储键值对，并提供插入、删除和查找操作。

1. template <class Key, class Value>
2. struct KeyValuePair {
3.     Key first;
4.     Value second;
6.     KeyValuePair(const Key& k = Key(), const Value& v = Value())
7.         : first(k), second(v) {}
9.     bool operator<(const KeyValuePair& kv) const {
10.         return first < kv.first;
11.     }
13.     bool operator>(const KeyValuePair& kv) const {
14.         return first > kv.first;
15.     }
17.     bool operator==(const KeyValuePair& kv) const {
18.         return first == kv.first;
19.     }
20. };
22. template<class Key, class Value, class KeyOfT = KeyValuePair<Key, Value>>
23. class Map {
24. private:
25.     RBTree<KeyValuePair<Key, Value>, KeyValuePair<Key, Value>&, KeyValuePair<Key, Value>*> _tree;
27. public:
28.     typedef typename RBTree<KeyValuePair<Key, Value>, KeyValuePair<Key, Value>&, KeyValuePair<Key, Value>*>::Iterator Iterator;
30.     Map() {}
32.     pair<Iterator, bool> Insert(const Key& key, const Value& value) {
33.         return _tree.Insert(KeyValuePair<Key, Value>(key, value));
34.     }
36.     bool Erase(const Key& key) {
37.         return _tree.Delete(KeyValuePair<Key, Value>(key));
38.     }
40.     Iterator Find(const Key& key) {
41.         return _tree.Find(KeyValuePair<Key, Value>(key));
42.     }
44.     Value& operator[](const Key& key) {
45.         Iterator it = Find(key);
46.         if (it != _tree.End()) {
47.             return it->second;
48.         } else {
49.             auto result = Insert(key, Value());
50.             return result.first->second;
51.         }
52.     }
54.     Iterator Begin() {
55.         return _tree.Begin();
56.     }
58.     Iterator End() {
59.         return _tree.End();
60.     }
61. };

复制代码

11.结语

红黑树作为一种高效的自均衡二叉查找树，在实际应用中得到了广泛使用。它通过重新着色和旋转操作保持树的均衡，保证了插入、删除和查找操作的时间复杂度为 O(log n)。与 AVL 树相比，红黑树在插入和删除操作中具有更高的服从，非常得当频仍更新的场景。希望通过本文的先容，各人能更好地明白和应用红黑树。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4