devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ 红黑树

作者：weixin_40725706 | 2024-07-28 13:56:11

赞

踩

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.红黑树性质

（图片来源：知乎@王大帅 特此鸣谢） 

红黑树具有以下五个重要性质，这些性质保证了红黑树的平衡性和高效性：

  1. 每个节点不是红色就是黑色：

    • 红黑树的每个节点都有一个颜色属性，这个颜色要么是红色，要么是黑色。通过颜色属性的限制，红黑树能够在结构上保持平衡。

  2. 根节点是黑色的：

    • 红黑树的根节点始终是黑色的。这一性质确保了树的平衡性从根节点开始，并且为树的其他平衡规则提供了基础。

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

    • 这一性质避免了两个连续的红色节点出现在从根到叶子的路径上。通过限制红色节点的排列方式，红黑树能够防止路径长度的不平衡增长。

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

    • 这一性质也称为黑色平衡性（black-height）。它保证了从任一节点到其叶节点的路径长度相似，从而使红黑树接近平衡。这意味着在插入或删除节点时，红黑树可以通过重新着色和旋转操作来恢复平衡，而不需要像 AVL 树那样频繁调整。

  5. 每个叶子节点都是黑色的（此处的叶子节点指的是空节点）：

    • 红黑树中的叶子节点实际上是树中的空节点（NIL 节点），这些节点也被视为黑色。即使树中没有显式存储这些 NIL 节点，理解它们的存在对于分析红黑树的平衡性是至关重要的。

3.红黑树节点定义

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

  1. enum Color { RED, BLACK };
  2.  
  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;  // 节点的颜色
  11.  
  12.     // 构造函数，初始化节点的数据和指针，默认颜色为红色
  13.     RBTreeNode(const T& data)
  14.         : _data(data)
  15.         , _left(nullptr)
  16.         , _right(nullptr)
  17.         , _parent(nullptr)
  18.         , _color(RED)
  19.     {}
  20. };

节点属性详解

  1. _data:

    • 存储节点的数据。这个数据可以是任何类型，由模板参数 T 决定。

  2. _left:

    • 指向左子节点的指针。如果左子节点不存在，则该指针为 nullptr。

  3. _right:

    • 指向右子节点的指针。如果右子节点不存在，则该指针为 nullptr。

  4. _parent:

    • 指向父节点的指针。这在红黑树的插入和删除操作中非常重要，因为这些操作需要通过父节点来进行旋转和重新着色。

  5. _color:

    • 节点的颜色属性，可以是红色（RED）或黑色（BLACK）。颜色属性在保持红黑树的平衡性中起到关键作用。
    • 在构造函数中，节点的颜色被默认设置为红色（RED）。这是因为插入新节点时，默认情况下设置为红色更易于保持树的平衡，并通过后续的旋转和重新着色操作来调整树的结构。

4.红黑树结构

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

4.1带头节点的红黑树结构

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

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

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

不带头节点的红黑树则不使用额外的头节点，直接通过根节点进行操作。在这种结构中，树的边界处理和遍历操作相对复杂一些，因为没有头节点来存储额外的指针信息。

为定义方便起见，后文中红黑树结构采用无头结点方式。

5.红黑树插入节点操作

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

  1. 按照二叉搜索树的规则插入新节点
  2. 检测新节点插入后，红黑树的性质是否遭到破坏，并进行修复

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.     }
  7.  
  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.     }
  22.  
  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;
  31.  
  32.     // 检测并修复红黑树性质，伪代码
  33.     FixInsert(cur);
  34.  
  35.     return make_pair(Iterator(newNode, _root), true);
  36. }

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

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

  1. 每个节点不是红色就是黑色。
  2. 根节点是黑色的。
  3. 如果一个节点是红色的，则它的两个孩子节点是黑色的。
  4. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
  5. 每个叶子节点都是黑色的（此处的叶子节点指的是空节点）。

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

  • 情况 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（红节点的子节点必须是黑色）。解决方式如下：

  1. 将p和u改为黑色。
  2. 将g改为红色。
  3. 将当前节点cur移动到g，继续向上调整。
  1. void FixInsert(Node* node) {
  2.     Node* parent = nullptr;
  3.     Node* grandFather = nullptr;
  4.  
  5.     // 当前节点不在根节点且其父节点为红色时，需要调整
  6.     while (node != _root && node->_parent->_color == RED) {
  7.         parent = node->_parent;
  8.         grandFather = parent->_parent;
  9.  
  10.         if (parent == grandFather->_left) {
  11.             Node* uncle = grandFather->_right;
  12.  
  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;
  24.  
  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.     }
  36.  
  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;
  4.  
  5.     // 当前节点不在根节点且其父节点为红色时，需要调整
  6.     while (node != _root && node->_parent->_color == RED) {
  7.         parent = node->_parent;
  8.         grandFather = parent->_parent;
  9.  
  10.         if (parent == grandFather->_left) {
  11.             Node* uncle = grandFather->_right;
  12.  
  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;
  32.  
  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.     }
  52.  
  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;
  4.  
  5.     // 当前节点不在根节点且其父节点为红色时，需要调整
  6.     while (node != _root && node->_parent->_color == RED) {
  7.         parent = node->_parent;
  8.         grandFather = parent->_parent;
  9.  
  10.         if (parent == grandFather->_left) {
  11.             Node* uncle = grandFather->_right;
  12.  
  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;
  32.  
  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.     }
  52.  
  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;  // 节点不存在，直接返回
  5.  
  6.     Node* y = z;
  7.     Node* x;
  8.     Color y_original_color = y->_color;
  9.  
  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.     }
  32.  
  33.     delete z;
  34.  
  35.     if (y_original_color == BLACK) {
  36.         FixDelete(root, x);
  37.     }
  38.  
  39.     return root;
  40. }

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

删除节点后，可能会破坏红黑树的性质，需要进行修复。常见的调整情况如下：

情况一：当前节点x是红色或其父节点是红色

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

情况二：当前节点x是黑色，其兄弟节点是红色

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

情况三：当前节点x是黑色，其兄弟节点是黑色，兄弟节点的子节点都是黑色

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

情况四：当前节点x是黑色，其兄弟节点是黑色，兄弟节点的一个子节点是红色

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

7.红黑树的性能

7.1红黑树的复杂度分析

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

  1. 查找：

    • 红黑树的查找操作与二叉搜索树类似，通过比较节点值从根节点逐层向下查找。由于红黑树的高度最多为 O(logn)，因此查找操作的复杂度为O(logn)。

  2. 插入：

    • 插入操作首先按照二叉搜索树的规则找到插入位置，复杂度为O(logn)。然后，通过重新着色和旋转来保持红黑树的平衡。每次插入操作最多需要进行两次旋转，因此插入操作的复杂度为 O(logn)。

  3. 删除：

    • 删除操作也首先按照二叉搜索树的规则找到要删除的节点，复杂度为 O(logn)。删除后，通过重新着色和旋转来保持红黑树的平衡。每次删除操作最多需要进行三次旋转，因此删除操作的复杂度为O(logn)。

7.2与 AVL 树的比较

红黑树与 AVL 树都是自平衡二叉搜索树，但它们在具体实现和性能特性上有所不同。以下是两者的比较：

  1. 平衡性：

    • AVL 树：高度平衡，确保每个节点的左右子树高度差最多为 1。这意味着 AVL 树通常比红黑树更加平衡。
    • 红黑树：通过颜色和旋转规则保持平衡，但允许更松散的平衡条件。这使得红黑树的高度可能稍高于 AVL 树，但仍然在 O(logn) 范围内。

  2. 插入和删除操作：

    • AVL 树：由于严格的平衡条件，插入和删除操作可能需要进行较多的旋转。插入操作的平均旋转次数为 1.44 次，删除操作的平均旋转次数为 2.44 次。
    • 红黑树：由于较为宽松的平衡条件，插入和删除操作所需的旋转次数通常较少。插入操作最多需要进行两次旋转，删除操作最多需要进行三次旋转。

  3. 查找性能：

    • AVL 树：由于更严格的平衡条件，AVL 树的查找性能在理论上优于红黑树。然而，在实际应用中，这种性能差异通常并不明显，尤其是在数据规模较大时。

  4. 适用场景：

    • 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;
  6.  
  7. 	Node* _node;  // 当前节点
  8. 	Node* _root;  // 树根节点
  9.  
  10. 	RBTreeIterator(Node* node, Node* root)
  11. 		: _node(node)
  12. 		, _root(root)
  13. 	{}
  14.  
  15. 	Self& operator++();//待实现
  16. 	Self& operator--();//待实现
  17.  
  18. 	Ref operator*()
  19. 	{
  20. 		return _node->_data;
  21. 	}
  22.  
  23. 	Ptr operator->()
  24. 	{
  25. 		return &_node->_data;
  26. 	}
  27.  
  28. 	bool operator!= (const Self& s)
  29. 	{
  30. 		return _node != s._node;
  31. 	}
  32.  
  33. 	bool operator== (const Self& s)
  34. 	{
  35. 		return _node == s._node;
  36. 	}
  37. };

8.2前向迭代（operator++）

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

  1. 当前节点有右子树：如果当前节点有右子树，则下一个节点是右子树的最左节点。

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

  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. 	}
  25.  
  26. 	return *this;
  27. }

8.3后向迭代（operator--）

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

  1. 当前节点是 end()：如果当前节点是 end()（空节点），则下一个节点是整棵树的最右节点。

  2. 当前节点有左子树：如果当前节点有左子树，则下一个节点是左子树的最右节点。

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

  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. 	}
  35.  
  36. 	return *this;
  37. }

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

  1. #pragma once
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cassert>
  5. #include<vector>
  6. using namespace std;
  7.  
  8. enum Color { RED, BLACK };
  9.  
  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;
  18.  
  19. 	RBTreeNode(const T& data)
  20. 		:_data(data)
  21. 		, _left(nullptr)
  22. 		, _right(nullptr)
  23. 		, _parent(nullptr)
  24. 		, _color(RED)
  25. 	{}
  26. };
  27.  
  28. template<class T, class Ref, class Ptr>
  29. struct RBTreeIterator
  30. {
  31. 	typedef RBTreeNode<T> Node;
  32. 	typedef RBTreeIterator<T, Ref, Ptr> Self;
  33.  
  34. 	Node* _node;
  35. 	Node* _root;
  36.  
  37. 	RBTreeIterator(Node* node, Node* root)
  38. 		:_node(node)
  39. 		, _root(root)
  40. 	{}
  41.  
  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. 			}
  52.  
  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. 			}
  65.  
  66. 			_node = parent;
  67. 		}
  68.  
  69. 		return *this;
  70. 	}
  71.  
  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. 			}
  82.  
  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. 			}
  93.  
  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. 			}
  106.  
  107. 			_node = parent;
  108.  
  109. 		}
  110.  
  111. 		return *this;
  112. 	}
  113.  
  114. 	Ref operator*()
  115. 	{
  116. 		return _node->_data;
  117. 	}
  118.  
  119. 	Ptr operator->()
  120. 	{
  121. 		return &_node->_data;
  122. 	}
  123.  
  124. 	bool operator!= (const Self& s)
  125. 	{
  126. 		return _node != s._node;
  127. 	}
  128.  
  129. 	bool operator== (const Self& s)
  130. 	{
  131. 		return _node == s._node;
  132. 	}
  133. };
  134.  
  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;
  144.  
  145. 	Iterator Begin()
  146. 	{
  147. 		Node* cur = _root;
  148. 		while (cur && cur->_left)
  149. 		{
  150. 			cur = cur->_left;
  151. 		}
  152.  
  153. 		return Iterator(cur, _root);
  154. 	}
  155.  
  156. 	Iterator End()
  157. 	{
  158. 		return Iterator(nullptr, _root);
  159. 	}
  160.  
  161. 	ConstIterator Begin() const
  162. 	{
  163. 		Node* cur = _root;
  164. 		while (cur && cur->_left)
  165. 		{
  166. 			cur = cur->_left;
  167. 		}
  168.  
  169. 		return ConstIterator(cur, _root);
  170. 	}
  171.  
  172. 	ConstIterator End() const
  173. 	{
  174. 		return ConstIterator(nullptr, _root);
  175. 	}
  176.  
  177. 	RBTree() = default;
  178. 	RBTree(const RBTree& t)
  179. 	{
  180. 		_root = _Copy(t._root);
  181. 	}
  182.  
  183. 	RBTree& operator=(RBTree t)
  184. 	{
  185. 		swap(_root, t._root);//交换根节点
  186. 		return *this;
  187. 	}
  188.  
  189. 	~RBTree()
  190. 	{
  191. 		_Destroy(_root);
  192. 		_root = nullptr;
  193. 	}
  194.  
  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. 		}
  203.  
  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. 		}
  223.  
  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;
  235.  
  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;
  251.  
  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;
  296.  
  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. 	}
  365.  
  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;
  378.  
  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;
  400.  
  401. 		parent->_right = subRL;
  402. 		if (subRL)
  403. 			subRL->_parent = parent;
  404.  
  405. 		Node* parentParent = parent->_parent;
  406.  
  407. 		subR->_left = parent;
  408. 		parent->_parent = subR;
  409.  
  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. 			}
  425.  
  426. 			subR->_parent = parentParent;
  427. 		}
  428. 	}
  429. 	void RotateR(Node* parent)
  430. 	{
  431. 		Node* subL = parent->_left;
  432. 		Node* subLR = subL->_right;
  433.  
  434. 		parent->_left = subLR;
  435. 		if (subLR)
  436. 			subLR->_parent = parent;
  437.  
  438. 		Node* parentParent = parent->_parent;
  439.  
  440. 		subL->_right = parent;
  441. 		parent->_parent = subL;
  442.  
  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. 			}
  458.  
  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;
  5.  
  6.     KeyValuePair(const Key& k = Key(), const Value& v = Value())
  7.         : first(k), second(v) {}
  8.  
  9.     bool operator<(const KeyValuePair& kv) const {
  10.         return first < kv.first;
  11.     }
  12.  
  13.     bool operator>(const KeyValuePair& kv) const {
  14.         return first > kv.first;
  15.     }
  16.  
  17.     bool operator==(const KeyValuePair& kv) const {
  18.         return first == kv.first;
  19.     }
  20. };
  21.  
  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;
  26.  
  27. public:
  28.     typedef typename RBTree<KeyValuePair<Key, Value>, KeyValuePair<Key, Value>&, KeyValuePair<Key, Value>*>::Iterator Iterator;
  29.  
  30.     Map() {}
  31.  
  32.     pair<Iterator, bool> Insert(const Key& key, const Value& value) {
  33.         return _tree.Insert(KeyValuePair<Key, Value>(key, value));
  34.     }
  35.  
  36.     bool Erase(const Key& key) {
  37.         return _tree.Delete(KeyValuePair<Key, Value>(key));
  38.     }
  39.  
  40.     Iterator Find(const Key& key) {
  41.         return _tree.Find(KeyValuePair<Key, Value>(key));
  42.     }
  43.  
  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.     }
  53.  
  54.     Iterator Begin() {
  55.         return _tree.Begin();
  56.     }
  57.  
  58.     Iterator End() {
  59.         return _tree.End();
  60.     }
  61. };

11.结语

红黑树作为一种高效的自平衡二叉查找树，在实际应用中得到了广泛使用。它通过重新着色和旋转操作保持树的平衡，保证了插入、删除和查找操作的时间复杂度为 O(log n)。与 AVL 树相比，红黑树在插入和删除操作中具有更高的效率，非常适合频繁更新的场景。希望通过本文的介绍，大家能更好地理解和应用红黑树。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/894440
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号