《 C++ 修炼全景指南：十八》穿越数据的红与黑：掌握数据平衡的极致艺术

这篇博客深入探讨了红黑树的各个方面，包括其理论基础、结构与性质，以及插入、删除、查找、前中后序和旋转操作的具体实现。我们分析了红黑树的性能、优化策略，并探讨其在实际应用中的广泛用途，如操作系统和数据库索引。此外，还涵盖了红黑树的高级主题、遍历方法、树的销毁以及验证红黑树合法性的算法。通过这篇博客，读者将全面掌握红黑树的工作原理和实际应用。

Lenyiin

5112人浏览 · 2024-09-19 14:07:55

Lenyiin · 2024-09-19 14:07:55 发布

摘要

本篇博客所涉及的所有代码均可从 CSDN 下载区下载

1、引言

红黑树(Red-Black Tree)是一种自平衡二叉搜索树(Balanced Binary Search Tree)，在计算机科学中具有重要地位。它通过在节点上引入颜色属性和特定的调整规则，确保树的高度始终保持在 O(log n) 的范围内，从而在最坏情况下也能提供高效的查找、插入和删除操作。这种特性使得红黑树成为许多实际应用中的首选数据结构，例如在高级语言的标准库中（如 C++ 的std::map、std::set，Java 的TreeMap、TreeSet），以及数据库系统、内存管理等领域，都可以看到红黑树的广泛应用。

1.1、红黑树的背景和意义

在数据结构领域，二叉搜索树(BST)是最常见的树结构之一。BST 的每个节点都满足左子树的所有节点小于该节点，右子树的所有节点大于该节点，这一特性使得在理想情况下，可以在 O(log n) 时间复杂度内完成查找、插入和删除操作。然而，在最坏情况下（例如当输入数据有序时），普通 BST 会退化成一条链表，导致时间复杂度上升到 O(n)。为了克服这个问题，平衡树的概念被引入，其中红黑树就是一种典型的平衡树。

红黑树的独特之处在于它通过简单的颜色属性和一组严格的调整规则，来维护树的近似平衡，而不像其他平衡树（如 AVL 树）那样频繁地调整结构。红黑树的每个节点被赋予一种颜色（红或黑），通过限制节点间的颜色排列方式，红黑树可以在 O(log n) 的时间内确保树的高度不会过高。与 AVL 树相比，红黑树在插入和删除操作时往往需要更少的旋转操作，因此在插入和删除操作频繁的场景中更具优势。

关于二叉搜索树的更多细节请见我的这篇博客：《 C++ 修炼全景指南：十六》打破编程瓶颈！掌握二叉搜索树的高效实现与技巧

关于 AVL 树的更多细节请见我的这篇博客：《 C++ 修炼全景指南：十七》自平衡的艺术：深入了解 AVL 树的核心原理与实现

1.2、红黑树的研究目的

本博客旨在全面深入地剖析红黑树，从理论到实践，详细阐述其基本结构、操作原理、实现细节、性能分析与优化，以及在实际应用中的表现。我们将从红黑树的基础概念入手，逐步深入到其核心技术，包括插入和删除操作的调整过程，左旋和右旋的具体实现，以及如何通过维护红黑树的五个性质来保持树的平衡。随后，我们将提供红黑树的 C++ 实现代码，分步解析关键算法，并通过实验数据对其性能进行分析。最后，讨论红黑树在现代计算机系统中的实际应用，并探讨其在并行和多线程环境中的扩展。

1.3、内容结构

为了让读者能够系统地理解红黑树，我们将以逻辑严密的方式展开内容。首先，我们将介绍红黑树的理论基础，包括其相对于其他平衡树的优势和设计思想。接着，我们将深入讨论红黑树的结构和性质，详细分析其五个核心性质是如何确保树的平衡。然后，我们将详细剖析红黑树的操作，包括插入、删除和查找操作的实现，以及它们在维护树的平衡时所涉及的调整过程。

在实现部分，我们将提供红黑树的完整 C++ 代码，详细解释每个操作的实现细节，包括节点的旋转和颜色调整。我们还将讨论红黑树的性能分析，比较其与其他平衡树的优劣，并提供优化策略。为了让理论知识更具实用性，我们还将讨论红黑树在实际应用中的案例，包括在标准库和数据库系统中的应用。

通过本博客，读者将获得对红黑树的全面认识，不仅掌握其基本操作，还能理解其背后的设计思想和实际应用场景。希望这份深入的技术指南能帮助读者更好地理解和运用红黑树，为其在计算机科学领域的学习和实践提供有力支持。

2、红黑树的理论基础

2.1、二叉搜索树的局限性

二叉搜索树 (BST) 是一种基于节点间有序关系的树形数据结构，广泛应用于各种查找和排序操作中。BST 的每个节点满足如下性质：左子树中所有节点的值小于该节点的值，右子树中所有节点的值大于该节点的值。得益于这一性质，理想情况下 BST 的查找、插入、删除操作的时间复杂度均为 O(log n)，这使其成为很多应用场景的首选。然而，BST 的性能严重依赖于其形态：当树接近平衡时，操作效率较高；但在最坏情况下，BST 可能退化为一条线性链表（例如插入有序数据时），此时时间复杂度将上升至 O(n)，显著降低了操作效率。

为了克服这一问题，需要一种能够自动保持树形结构平衡的机制。于是，自平衡二叉搜索树的概念被提出，红黑树正是其中一种重要的实现。

2.2、平衡树的概念

平衡树的主要目标是保证树的高度接近 O(log n)，从而确保在最坏情况下也能高效地执行查找、插入和删除等操作。常见的平衡树包括 AVL 树、红黑树、B 树等。其中，红黑树是一种弱平衡树，通过一组颜色属性和调整规则，限制了节点的排列方式，使得树保持近似平衡。

相比于其他平衡树，红黑树在插入和删除操作时的调整较为简单。比如，AVL 树在每次插入和删除后，都需要严格调整树的平衡状态，通过多次旋转操作确保左右子树高度的差异不超过 1。尽管 AVL 树的查找操作效率较高，但频繁的旋转操作在插入和删除频繁的场景中会造成性能损耗。而红黑树则通过引入颜色属性，容忍一定程度的不平衡，允许左、右子树的高度差达到 2 倍以内。这种设计降低了维护平衡所需的调整代价，使红黑树在插入和删除操作频繁的情况下更具性能优势。

2.3、红黑树的起源

红黑树的设计最早可以追溯到 1972 年 Bayer 和 McCreight 提出的 2-3-4 树（或称 2-4 树），这是一种能够自动保持平衡的多路搜索树。2-3-4 树的节点可以包含 2 至 4 个子节点，并通过节点分裂和合并操作来维持树的平衡。尽管 2-3-4 树的操作相对复杂，但其思想直接启发了红黑树的设计。

1987 年，Guibas 和 Sedgewick 提出了红黑树，将 2-3-4 树的多节点结构转化为二叉树结构，并引入了红色和黑色两种颜色来标识节点的状态。通过颜色属性和严格的规则，红黑树实现了类似 2-3-4 树的平衡特性，但使用二叉树的形式，使得实现和理解更加简洁。在红黑树中，每个红色节点代表 2-3-4 树中的节点与父节点合并的状态，而黑色节点则对应 2-3-4 树的正常节点状态。

2.4、红黑树的结构与性质

红黑树的高效性能主要归功于其结构和一组严格的性质，这些性质确保了树的平衡性。通过颜色标记和特定规则的维护，红黑树成功地避免了普通二叉搜索树退化成链表的情况，并保持了查找、插入和删除操作的时间复杂度在 O(log n) 范围内。在这一节中，我们将详细剖析红黑树的结构以及维持平衡的五大性质，并解释其在保持树平衡和优化操作性能方面的重要作用。

2.4.1、红黑树的节点结构

红黑树的节点与普通二叉搜索树的节点类似，但多了一个颜色属性。每个节点主要包含以下几个部分：

键值对（_kv）：节点中存储的数据，通常用于比较和查找操作。
颜色（_colour）：节点的颜色属性，取值为红色或黑色。
左子节点（_left）：指向当前节点的左子树。
右子节点（_right）：指向当前节点的右子树。
父节点（_parent）：指向当前节点的父节点，用于在调整时向上回溯。

颜色属性是红黑树区别于其他二叉搜索树的重要特征。通过为节点指定红色或黑色，并根据特定规则调整节点之间的颜色关系，红黑树在执行插入和删除操作时，能有效地维持近似平衡状态。

2.4.2、红黑树的五大性质

红黑树依赖以下五大性质来维持其平衡状态：

性质 1：节点颜色
每个节点要么是红色，要么是黑色。
- 这一性质为红黑树的自平衡机制奠定了基础。通过对节点颜色的限制，红黑树可以在插入和删除操作后通过颜色调整来保持树的平衡。
性质 2：根节点必须是黑色
红黑树的根节点必须是黑色。
- 这确保了从根节点到叶子节点的所有路径至少包含一个黑色节点，有助于维持树的整体平衡。
性质 3：红色节点的子节点必须是黑色
如果一个节点是红色的，则它的子节点必须是黑色的。
- 换句话说，在红黑树中，不允许出现两个连续的红色节点。
- 该性质确保了红黑树不会有过多的红色节点连在一起，这有效地限制了树的高度，避免了退化成链表的情况。
性质 4：每个节点到叶子节点的所有路径包含相同数量的黑色节点
从任一节点到其每个叶子节点的路径上必须具有相同数量的黑色节点。
- 这被称为红黑树的 “黑色平衡” 性质，它限制了树的高度，从而确保了 O(log n) 的操作时间复杂度。
- 该性质的存在意味着，红黑树从根到叶子节点的最长路径不会超过最短路径的两倍。正是这个特性，使得红黑树能够在最坏情况下依然保持较好的性能。
性质 5：叶子节点都是黑色
所有的叶子节点（NIL）都是黑色，并且它们不存储任何关键字。
- 叶子节点在红黑树的实现中通常作为哨兵节点存在，这简化了插入和删除操作的代码逻辑。
- 它们的存在确保了在调整树结构时，不需要特殊处理空节点的情况。

通过这五大性质，红黑树能有效地限制树的高度，保持较好的平衡状态，从而使查找、插入和删除操作的时间复杂度始终维持在 O(log n) 内。接下来，我们将进一步讨论这些性质是如何在插入和删除操作中得到维护的。

2.4.3、红黑树的颜色调整与树旋转

红黑树在插入和删除节点时，可能会打破其性质，需要进行调整以恢复平衡。这种调整主要通过颜色变换和树旋转来实现。

颜色变换：指改变某些节点的颜色，以重新满足红黑树的性质。颜色变换是一种简单而有效的调整方式，通常与树旋转结合使用。
树旋转：包括左旋和右旋两种操作，通过旋转来改变节点的相对位置，从而调整树的结构。
- 左旋（Left Rotation）：将某个节点的右子节点提升为父节点，原节点成为新父节点的左子节点。
- 右旋（Right Rotation）：与左旋相反，将某个节点的左子节点提升为父节点，原节点成为新父节点的右子节点。
树旋转的目的是改变树的形态，以减少树的高度或调整子树的平衡性。在插入和删除操作中，旋转通常结合颜色变换一起使用，以恢复红黑树的五大性质。

2.5、红黑树的平衡性分析

红黑树的平衡性相对较弱，允许树在一定程度上偏离完美平衡。通过颜色属性和五大性质，确保从根节点到叶子节点的最长路径长度不会超过最短路径长度的两倍。这意味着红黑树的高度最多为 2*log(n+1)，其中 n 是节点数。这一高度限制直接决定了红黑树的查找、插入和删除操作的时间复杂度为 O(log n)。

相对于其他平衡树，如 AVL 树，红黑树的高度稍微高一些，但由于其在插入和删除操作中需要的调整次数较少，性能通常更为优越。红黑树的插入和删除操作最多需要三次旋转，而 AVL 树在某些情况下需要多次旋转。这使得红黑树在插入和删除操作频繁的场景中更具效率。

另外，红黑树的实现相对简单，代码量较少，且由于其性能稳定且接近 O(log n)，在很多编程语言的标准库中被广泛采用。例如，在 C++ STL 中，std::map 和 std::set 都是通过红黑树实现的，保证了这些容器在最坏情况下的操作效率。

2.6、红黑树在实际应用中的优势

红黑树的结构和性质使其成为实际应用中常用的数据结构之一。由于红黑树能够在最坏情况下保证 O(log n) 的时间复杂度，并且在插入和删除操作中具有较高的效率，因此在许多编程语言的标准库中（如 C++ 的 std::map 和 std::set，Java 的 TreeMap 和 TreeSet）都采用了红黑树作为底层实现。此外，在数据库系统、操作系统中的进程调度、事件驱动模拟等领域，红黑树也被广泛使用。例如，Linux 内核中的完全公平调度器(CFS)就利用了红黑树来管理进程调度，实现了高效的时间片分配和抢占。

通过深入理解红黑树的理论基础，我们可以更好地掌握其设计思想、性质以及在不同应用场景中的优势和局限，为后续深入探讨红黑树的结构、操作和实现奠定基础。在接下来的部分中，我们将详细剖析红黑树的插入、删除和查找操作，展示其如何通过颜色调整和树旋转来保持树的平衡。

3、红黑树的实现

红黑树的高效性不仅体现在其结构和性质上，更体现在其操作和维护过程中。红黑树通过精巧的设计，使得在插入、删除和查找操作中始终能保持较好的平衡状态。为了实现这一点，红黑树依赖于颜色调整和树旋转等机制。接下来，我们将深入探讨红黑树的核心操作——插入、删除和查找，重点分析这些操作如何在维持红黑树性质的同时，保持高效性。

3.1、红黑树节点结构

红黑树的插入操作相对复杂，因为它需要在插入新节点的同时维护红黑树的性质。这包括颜色调整、树旋转等操作，以确保红黑树的平衡。我们将以你提供的红黑树节点结构 RBTreeNode 为基础，详细讨论插入操作的实现。

首先，我们看一下你定义的红黑树节点结构：

namespace Lenyiin
{
	enum Colour
    {
        RED,
        BLACK
    };

    template <class K, class V>
    struct RBTreeNode
    {
        RBTreeNode<K, V> *_left;
        RBTreeNode<K, V> *_right;
        RBTreeNode<K, V> *_parent;

        std::pair<K, V> _kv;
        Colour _colour;

        RBTreeNode(const std::pair<K, V> &kv)
            : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _colour(RED)
        {
        }
    };
    
    template <class K, class V>
    class RBTree
    {
    private:
    	typedef RBTreeNode<K, V> Node;
    	
    	RBTree(Node* root = nullptr)
    		: _root(root)
    	{}
    	
    	~RBTree()
        {
            DeleteTree(_root);
        }
    	
    	Node* _root;
    };
}

这个节点结构定义了红黑树中每个节点应有的属性，包括左右子节点、父节点、键值对（_kv）、以及节点的颜色。初始颜色被设为红色，这是因为在红黑树的插入操作中，新节点被插入为红色有助于降低插入调整的复杂度。

3.2、旋转操作

在红黑树中，旋转操作是保持红黑树性质的核心步骤之一。在执行插入或删除操作时，红黑树可能会违反其性质，这时候通过旋转操作可以重新调整树的结构，使其满足红黑树的平衡要求。旋转操作主要分为两种：左旋和右旋。通过这两种操作，我们可以在局部调整树的形状，使得其符合红黑树的性质。

3.2.1、左旋

左旋操作是将节点向左旋转，使其右子节点上升为其父节点，而原节点下降为其右子节点的左子节点。这种旋转主要用于调整在右孩子方向上失衡的情况。

场景：当新节点插入到某个节点的右子树的右子节点时，可能导致该节点失衡。此时，需要进行左旋操作来恢复平衡。

旋转过程：

假设不平衡节点为 A，其右子节点为 B。
B 的左子树 BL 将成为 A 的右子树。
B 成为新的子树根节点，而 A 成为 B 的左子节点。

示例图：

插入导致的结构：

单左旋后的结构：

    B
   / \
  A   C

代码实现：

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

	parent->_right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	parent->_parent = subR;

	// 1. 原来 parent 是这棵树的根, 现在 subR 是根
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
		subR->_parent = ppNode;
	}
}

解释：

subR 指向 A 的右子节点 B。
B 的左子树 subRL 被挂接到 A 的右子树。
B 成为新的根节点，A 成为 B 的左子节点。

3.2.2、右旋

右旋操作是左旋的镜像操作。它将节点向右旋转，使其左子节点上升为其父节点，而原节点下降为其左子节点的右子节点。右旋主要用于调整在左孩子方向上失衡的情况。

场景：当新节点插入到某个节点的左子树的左子节点时，可能导致该节点失衡。此时，需要进行右单旋操作来恢复平衡。

旋转过程：

假设不平衡节点为 A，其左子节点为 B。
B 的右子树 BR 将成为 A 的左子树。
B 成为新的子树根节点，而 A 成为 B 的右子节点。

示例图：

插入导致的结构：

    A
   / 
  B   
 / 
C

单右旋后的结构：

    B
   / \
  C   A

代码实现

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

	parent->_left = subLR;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	parent->_parent = subL;

	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}
}

详细解释：

parent 是节点 A
subL 指向 A 的左子节点 B。
B 的右子树 subLR 被挂接到 A 的左子树。
B 成为新的根节点，A 成为 B 的右子节点。

3.2.3、旋转操作的技术细节

在红黑树的插入和删除操作中，我们使用旋转操作来调整树的平衡。具体来说，旋转操作的目的是减少树的高度，或者说是重新分配子树的高度，使得整个树的结构更加平衡。在红黑树中，执行旋转操作不会破坏二叉搜索树的性质，即中序遍历的顺序仍然保持不变。

左旋与右旋的对称性：左旋和右旋是对称操作，左旋将节点的右子树移至父节点，而右旋将节点的左子树移至父节点。两者的实现过程是对称的，这也使得在红黑树的调整中可以灵活运用两者来维护树的平衡。
复杂度：单次旋转操作的时间复杂度为 O(1) 。旋转操作只涉及指针的改变，不需要遍历树的节点，因此是一个非常高效的操作。
调整树的高度：通过左旋或右旋，红黑树可以减少某个子树的高度，或者在某个方向上增加子树的高度。这样就能在插入或删除节点后，通过旋转调整，保持红黑树的高度平衡，进而保证操作的时间复杂度为 O(log⁡n) 。

3.2.4、旋转操作在插入和删除中的作用

在红黑树的插入和删除操作中，我们主要通过旋转操作来维护红黑树的性质：

插入调整：在插入操作中，可能会出现连续的红色节点违背红黑树的性质。通过旋转和重新着色，可以确保红黑树的平衡。例如，在插入一个节点后，如果出现 “红-红” 冲突，则根据叔叔节点的颜色不同，我们需要执行左旋或者右旋，或者双旋操作来调整树的结构。
删除调整：删除操作可能会破坏红黑树的平衡，特别是当删除一个黑色节点时，可能导致黑高不平衡。这时候通过旋转和重新着色，可以重新平衡红黑树。例如，在删除节点后，如果当前节点的兄弟节点是黑色的且其子节点中有一个是红色，则我们可以通过旋转和重新着色，使得整棵树重新满足红黑树的性质。

通过上述两种旋转操作和调整逻辑，红黑树能够在插入和删除操作后，依然保持其性质，从而确保查找、插入、删除操作的时间复杂度始终保持在 O(log⁡n) 。这就是红黑树高效性和实用性的重要原因之一。

3.3、插入操作

插入操作主要包括两个步骤：

常规二叉搜索树（BST）的插入：
将新节点按照二叉搜索树的插入规则插入到树中。
维护红黑树的性质：
通过颜色调整和树旋转操作，确保插入后的树满足红黑树的性质。

3.3.1、常规BST插入

首先，将新节点按照二叉搜索树的规则插入到树中。初始插入时，新节点默认被着色为红色，这样可以避免违反性质4（从根到叶子节点的所有路径必须包含相同数量的黑色节点），但有可能违反性质3（红色节点的子节点必须是黑色）。红色节点的默认插入有利于在后续的调整中减少旋转次数，因为插入红色节点不影响其父节点到根节点的黑色节点数量。

bool Insert(const std::pair<K, V> &kv)
{
    // 1. 按照搜索树的规则进行插入
    // 如果树为空，直接将新节点设为根节点，并染成黑色
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_colour = BLACK; // 根节点是黑色的
        return true;
    }

    // 遍历树找到插入位置
    Node *parent = nullptr;
    Node *cur = _root;
    while (cur)
    {
    	if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
        	return false; // 待插入的节点已经存在
        }
    }

    // 找到位置 插入新节点
    cur = new Node(kv);
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
        cur->_parent = parent;
    }
    else
    {
        parent->_right = cur;
        cur->_parent = parent;
    }

    // 插入调整
    InsertFixUp(parent, cur);

    return true;
}

在这个代码片段中，我们创建一个新的红黑树节点。如果树为空，我们直接将新结点设置为根节点并将其染成黑色。否则，我们按照二叉搜索树的插入规则找到适当的插入位置，将新结点插入到树中，并设置其父节点。

3.3.2、调整树以恢复红黑树的性质

插入新节点后，需要通过颜色调整和树旋转来恢复红黑树的性质。调整过程根据新节点的位置和父节点的颜色，可分为三种情形：

情况 1：父节点为黑色
若新节点的父节点为黑色，直接插入不会违反红黑树的性质。这种情况下，不需要任何调整，直接结束插入操作。
情况 2：父节点为红色，且叔叔节点（父节点的兄弟节点）也是红色
若父节点和叔叔节点均为红色，这种情况会违反性质3，需要进行颜色翻转。
- 将父节点和叔叔节点重新着色为黑色，将祖父节点重新着色为红色。
- 将祖父节点作为新插入节点，并递归进行插入调整。这一过程可能会递归至根节点，如果最终根节点被着色为红色，则将其重新着色为黑色以保持性质2。
情况 3：父节点为红色，叔叔节点为黑色或不存在
在这种情况下，新节点的父节点和叔叔节点的颜色不一致，且可能违反性质3，需要进行树旋转和颜色调整：
- 左旋或右旋：根据新节点的位置，选择进行左旋或右旋以调整树结构，使其符合红黑树的性质。具体操作如下：
  - 如果新节点是父节点的右子节点且父节点是祖父节点的左子节点，首先对父节点进行左旋，使新节点成为父节点。
  - 接着，将祖父节点作为旋转节点进行右旋，将新节点的父节点（原父节点）提升为祖父节点的位置。
  - 如果是相反的情况，则进行右旋和左旋的组合操作。
- 颜色调整：旋转后，将新节点的父节点重新着色为黑色，将祖父节点重新着色为红色，以保持红黑树的性质。

void InsertFixUp(Node *parent, Node *cur)
{
    // 调整结点颜色
    // 新结点给红的还是黑的?	红色
    // 1. 空树。插入结点做根, 把他变黑。
    // 2. 插入红色节点, 他的父亲是黑色的, 结束。
    // 3. 插入红色节点, 他的父亲是红色的, 可以推断他的祖父存在且一定为黑色。关键看叔叔
    //	a. 如果叔叔存在且为红, 把父亲和叔叔变黑, 祖父变红, 继续往上处理。
    //	b. 如果叔叔存在且为黑, 或者不存在。旋转（单旋 or 双旋）+ 变色
    while (parent && parent->_colour == RED)
    {
        // 关键看叔叔
        Node *grandfather = parent->_parent;
        if (grandfather->_left == parent)
        {
            Node *uncle = grandfather->_right;

            // 情况1: uncle 存在, 且为红
            if (uncle && uncle->_colour == RED)
            {
                parent->_colour = uncle->_colour = BLACK;
                grandfather->_colour = RED;

                // 继续向上调整
                cur = grandfather;
                parent = cur->_parent;
            }
            // 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑
            else
            {
                // 情况 3: 双旋 -> 变成单旋
                if (cur == parent->_right)
                {
                    RotateL(parent);
                    std::swap(parent, cur);
                }

                // 第二种情况 (ps: 有可能是第三种情况变过来的)
                RotateR(grandfather);
                grandfather->_colour = RED;
                parent->_colour = BLACK;

                break;
            }
        }
        else
        {
            Node *uncle = grandfather->_left;

            // 情况1: uncle 存在, 且为红
            if (uncle && uncle->_colour == RED)
            {
                parent->_colour = BLACK;
                uncle->_colour = BLACK;
                grandfather->_colour = RED;

                // 继续向上调整
                cur = grandfather;
                parent = cur->_parent;
            }
            // 情况2 or 情况3: uncle 不存在 or uncle 存在且为黑
            else
            {
                // 情况3: 双旋 -> 变为单旋
                if (cur == parent->_left)
                {
                    RotateR(parent);
                    std::swap(parent, cur);
                }

                // 第二种情况 (ps: 有可能是第三种情况变来的)
                RotateL(grandfather);
                grandfather->_colour = RED;
                parent->_colour = BLACK;

                break;
            }
        }
    }

	// 保证根节点为黑色
    _root->_colour = BLACK;
}

在 InsertFixUp 函数中，我们通过 while 循环处理可能违反红黑树性质的节点。在每次调整中，我们首先判断新节点的父节点是祖父节点的左子节点还是右子节点，然后根据叔叔节点的颜色来决定调整方式。

左旋和右旋：在调整过程中，我们使用了左旋和右旋操作。左旋操作将子树进行顺时针旋转，而右旋操作将子树进行逆时针旋转。通过旋转调整子树的结构，可以维持红黑树的性质。
颜色调整：在旋转操作之后，我们需要调整节点的颜色以确保树的平衡。通常情况下，父节点会被重新着色为黑色，而祖父节点被重新着色为红色。

通过上述调整，红黑树能够在插入新节点后依然保持平衡，保证树的高度不超过 O(log n) 。

3.3.3、插入操作的复杂度

红黑树的插入操作在最坏情况下的时间复杂度为 O(log n)，这是由于红黑树的高度始终保持在 O(log n) 内。插入操作中的调整最多需要三次旋转，因此具有较高的效率。在实际应用中，红黑树的插入操作通常比其他平衡树（如 AVL 树）更为高效，因为红黑树的旋转次数较少。

通过插入操作的实现，我们可以看到红黑树是如何通过精巧的颜色调整和树旋转来保持平衡，确保其在各种操作中的高效性。接下来，我们将探讨红黑树的删除操作，了解其在复杂情况下的平衡维持能力。

3.4、删除操作

红黑树的删除操作比插入更为复杂，因为删除节点可能同时破坏多条路径上的红黑树性质。删除操作主要涉及以下步骤：

红黑树的删除操作比插入更为复杂，因为它不仅需要删除指定的节点，还需要维护红黑树的平衡特性。删除操作可能导致多条路径上的红黑树性质的破坏，尤其是删除黑色节点时可能影响树的黑色平衡，需要通过调整来恢复红黑树的性质。解下来我们将详细讨论删除操作的实现。删除操作主要涉及以下步骤：

常规二叉搜索树（BST）的删除：按照 BST 的删除规则找到并删除节点。
维护红黑树的性质：通过颜色调整和树旋转操作，确保删除后的树仍满足红黑树的性质。

3.4.1、常规BST删除

首先，我们按照 BST 的规则找到并删除指定的节点。红黑树的删除操作可以分为以下几种情况：

节点没有子节点：直接删除该节点。
节点只有一个子节点：删除该节点，并将其子节点与其父节点连接。
节点有两个子节点：找到该节点的中序后继，用中序后继的值替换该节点，然后删除中序后继。

// 删除操作
bool Erase(const K &key)
{
    // 查找节点
    Node *nodeToDelete = _root;
    while (nodeToDelete)
    {
        if (nodeToDelete->_kv.first > key)
        {
        	nodeToDelete = nodeToDelete->_left;
        }
        else if (nodeToDelete->_kv.first < key)
        {
        	nodeToDelete = nodeToDelete->_right;
        }
        else
        {
        	break; // 找到待删除的节点
        }
    }

    // 如果未找到节点
    if (nodeToDelete == nullptr)
    {
    	return false;
    }

    // 执行删除操作
    Node *parent, *child;
    Colour originalColour = nodeToDelete->_colour;

    if (nodeToDelete->_left == nullptr)
    {
        child = nodeToDelete->_right;
        parent = nodeToDelete->_parent;
        Transplant(nodeToDelete, nodeToDelete->_right);
    }
    else if (nodeToDelete->_right == nullptr)
    {
        child = nodeToDelete->_left;
        parent = nodeToDelete->_parent;
        Transplant(nodeToDelete, nodeToDelete->_left);
    }
    else
    {
        Node *successor = Minimum(nodeToDelete->_right);
        originalColour = successor->_colour;
        child = successor->_right;
        if (successor->_parent == nodeToDelete)
        {
        	parent = successor;
        }
        else
        {
            Transplant(successor, successor->_right);
            successor->_right = nodeToDelete->_right;
            successor->_right->_parent = successor;
            parent = successor->_parent;
        }
        Transplant(nodeToDelete, successor);
        successor->_left = nodeToDelete->_left;
        successor->_left->_parent = successor;
        successor->_colour = nodeToDelete->_colour;
    }

    delete nodeToDelete;

    // 如果删除的节点是黑色，需要进行调整
    if (originalColour == BLACK)
    {
    	EraseFixUp(child, parent);
    }

    return true;
}

在这段代码中，我们首先找到要删除的节点，然后根据节点的子节点情况进行删除操作：

没有子节点或只有一个子节点：直接用子节点替换被删除的节点。
有两个子节点：找到该节点的中序后继，用后继节点替换要删除的节点，然后删除后继节点。

3.4.2、维护红黑树的性质

删除操作可能会破坏红黑树的性质，特别是删除黑色节点时。我们通过 EraseFixUp 函数来调整红黑树，确保其性质不被破坏。调整的过程包括：

删除节点为红色：
若删除的节点为红色，不会影响红黑树的性质。这种情况下，无需进行额外调整，直接完成删除操作。
删除节点为黑色：
若删除的节点为黑色，会违反红黑树的性质4，因此需要进行一系列调整。调整的主要目标是保持树的 “黑色平衡”。以下是调整的主要情形：
- 情况 1：兄弟节点为红色
  若删除节点的兄弟节点为红色，则此时兄弟节点必有两个黑色子节点。为了调整树平衡，我们首先对父节点进行左旋（如果兄弟节点是右子节点，则进行右旋），并重新着色：
  - 将父节点着色为红色。
  - 将兄弟节点着色为黑色。
  - 旋转后，新的兄弟节点必为黑色，接下来根据新的兄弟节点的子节点情况继续调整。
- 情况 2：兄弟节点为黑色，且兄弟节点的两个子节点均为黑色
  这种情况下，我们可以将兄弟节点重新着色为红色，以补偿删除节点的黑色缺失。这可能导致父节点的黑色平衡被破坏，因此将父节点作为新删除节点，递归进行调整。
- 情况 3：兄弟节点为黑色，兄弟节点的左子节点为红色，右子节点为黑色
  对兄弟节点进行右旋，使兄弟节点的左子节点成为兄弟节点，并交换兄弟节点与其左子节点的颜色。这将情形转化为情况4。
- 情况 4：兄弟节点为黑色，且兄弟节点的右子节点为红色
  对父节点进行左旋，将兄弟节点提升为父节点，并将兄弟节点的右子节点（旋转后的左子节点）重新着色为黑色。这一调整恢复了树的平衡，完成删除操作。

void EraseFixUp(Node *x, Node *parent)
{
    while (x != _root && (x == nullptr || x->_colour == BLACK))
    {
        if (x == parent->_left)
        {
            Node *w = parent->_right;
            // 情况1: x的兄弟节点w是红色的
            if (w->_colour == RED)
            {
                w->_colour = BLACK;
                parent->_colour = RED;
                RotateL(parent);
                w = parent->_right;
            }
            // 情况2: x的兄弟节点w是黑色的，且w的两个子节点都是黑色的
            if ((w->_left == nullptr || w->_left->_colour == BLACK) &&
            (w->_right == nullptr || w->_right->_colour == BLACK))
            {
                w->_colour = RED;
                x = parent;
                parent = x->_parent;
        	}
            else
            {
                // 情况3: w是黑色的，并且w的左子节点是红色，右子节点是黑色
                if (w->_right == nullptr || w->_right->_colour == BLACK)
                {
                    if (w->_left)
                    w->_left->_colour = BLACK;
                    w->_colour = RED;
                    RotateR(w);
                    w = parent->_right;
                }
                // 情况4: w是黑色的，并且w的右子节点是红色
                if (w)
                {
                    w->_colour = parent->_colour;
                    parent->_colour = BLACK;
                    if (w->_right)
                    w->_right->_colour = BLACK;
                    RotateL(parent);
                }
                x = _root;
                break;
            }
        }
        else
        {
            Node *w = parent->_left;
            // 情况1: x的兄弟节点w是红色的
            if (w->_colour == RED)
            {
                w->_colour = BLACK;
                parent->_colour = RED;
                RotateR(parent);
                w = parent->_left;
            }
            // 情况2: x的兄弟节点w是黑色的，且w的两个子节点都是黑色的
            if ((w->_left == nullptr || w->_left->_colour == BLACK) &&
            (w->_right == nullptr || w->_right->_colour == BLACK))
            {
                w->_colour = RED;
                x = parent;
                parent = x->_parent;
            }
            else
            {
                // 情况3: w是黑色的，并且w的右子节点是红色，左子节点是黑色
                if (w->_left == nullptr || w->_left->_colour == BLACK)
                {
                    if (w->_right)
                    w->_right->_colour = BLACK;
                    w->_colour = RED;
                    RotateL(w);
                    w = parent->_left;
                }
                // 情况4: w是黑色的，并且w的左子节点是红色
                if (w)
                {
                    w->_colour = parent->_colour;
                    parent->_colour = BLACK;
                    if (w->_left)
                    w->_left->_colour = BLACK;
                    RotateR(parent);
                }
                x = _root;
                break;
            }
        }
    }

    if (x)
    	x->_colour = BLACK;
}

在 EraseFixUp 函数中，我们通过 while 循环处理可能破坏红黑树性质的节点。在每次调整中，我们首先判断节点是父节点的左子节点还是右子节点，然后根据兄弟节点及其子节点的颜色来决定调整方式。

左旋和右旋：与插入操作类似，删除操作中的调整也可能需要左旋和右旋操作，以调整子树的结构并维持红黑树的性质。
颜色调整：调整过程中，我们需要适当改变节点的颜色以保持树的平衡。

通过这四种情况的处理，我们可以确保删除操作后的红黑树仍然满足其性质，保持平衡。

3.4.3、辅助函数

Node *Minimum(Node *node)
{
    while (node->_left != nullptr)
    {
    	node = node->_left;
    }
    return node;
}

void Transplant(Node *u, Node *v)
{
    if (u->_parent == nullptr)
    {
    	_root = v;
    }
    else if (u == u->_parent->_left)
    {
    	u->_parent->_left = v;
    }
    else
    {
    	u->_parent->_right = v;
    }

    if (v != nullptr)
    {
    	v->_parent = u->_parent;
    }
}

Minimum 函数：找到子树中的最小节点，用于在删除操作中查找后继节点。

Transplant 函数：替换树中的子树，用于删除操作。

3.5、查找操作

在红黑树中，查找操作的核心在于利用二叉搜索树的性质，即对于任一节点，其左子树的所有节点值均小于该节点值，右子树的所有节点值均大于该节点值。红黑树是一种自平衡二叉搜索树，它在确保了插入和删除操作的平衡性后，也使得查找操作的时间复杂度保持在 O(log⁡n) 。红黑树查找的步骤和普通的二叉搜索树类似，但它能够在大量插入和删除操作后，仍然保证较优的查找效率。

3.5.1、查找操作的基本步骤

查找操作在红黑树中与在普通二叉搜索树中相似。我们从根节点开始，比较目标值和当前节点的键值，然后根据比较结果递归或迭代地进入左子树或右子树。直到找到目标值或遇到叶子节点（即没有匹配的键值）时结束。

从根节点开始：从根节点 _root 开始，初始化当前节点 cur 为 _root。
比较键值：比较目标键 key 和当前节点 cur->_kv.first ：
- 如果 key 小于 cur->_kv.first，则进入左子树 cur->_left。
- 如果 key 大于 cur->_kv.first，则进入右子树 cur->_right。
- 如果 key 等于 cur->_kv.first，则找到了目标节点，返回当前节点。
迭代查找：重复以上步骤，直到找到目标节点或者遍历完整个树。

3.5.2、查找操作的实现

下面是查找操作的代码实现：

Node* Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        // 比较目标键值和当前节点的键值
        if (key < cur->_kv.first)
        {
            cur = cur->_left; // 向左子树查找
        }
        else if (key > cur->_kv.first)
        {
            cur = cur->_right; // 向右子树查找
        }
        else
        {
            return cur; // 找到目标节点
        }
    }
    return nullptr; // 未找到目标节点
}

3.5.3、查找操作的技术细节

在查找过程中，我们重点关注以下几个方面：

递归与迭代：查找操作可以通过递归或迭代方式实现。上面的实现使用了迭代方式，这种方式相对来说更加高效，因为它避免了递归调用带来的额外开销，特别是在树的深度较大时，递归调用可能导致栈溢出。
时间复杂度：由于红黑树是平衡二叉搜索树，它的高度始终维持在 O(log⁡n) 的级别。因此，查找操作的时间复杂度也为 O(log⁡n) 。这比普通的非平衡二叉搜索树在最坏情况下（退化为链表，时间复杂度为 O(n) 要优越得多。
数据类型的比较：查找过程中涉及节点键值的比较，这就要求节点存储的键类型 K 支持比较操作。通常情况下，我们需要确保类型 K 定义了 < 和 > 操作符，以便进行比较。

3.6、删除整颗红黑树操作

删除整个红黑树的操作需要慎重处理，因为在删除过程中，我们必须确保释放每个节点占用的内存，以防止内存泄漏。这个操作通常使用后序遍历来实现，因为我们需要先删除子节点，然后才能删除父节点，这样可以避免试图访问已经被删除的节点。

3.6.1、删除整个红黑树的步骤

后序遍历删除节点： 采用后序遍历的方式，从叶子节点开始逐层删除节点。对于每个节点，先删除其左右子节点，再删除自身。
释放节点内存： 逐个释放每个节点的内存，确保不会造成内存泄漏。
重置根节点： 在所有节点删除后，将树的根节点指针置为 nullptr，以确保树被完全清空。

3.6.2、删除整个红黑树的实现：

下面是使用后序遍历来删除整个红黑树的实现代码：

// 删除整个红黑树
void DeleteTree(Node* root) 
{
    if (root == nullptr) 
    {
    	return;
    }

    // 递归删除左子树
    DeleteTree(root->_left);
    // 递归删除右子树
    DeleteTree(root->_right);

    // 删除当前节点
    delete root;
}

代码说明：

后序遍历删除节点：
- DeleteTree 函数采用后序遍历方式，先递归删除左子树，然后递归删除右子树，最后删除当前节点。由于后序遍历是 “左子树 -> 右子树 -> 根节点” 的顺序，这样可以确保我们在删除当前节点之前，已经删除了其子节点。
释放节点内存：
- 对于每个节点，在遍历到时直接使用 delete 运算符释放节点的内存，确保不会造成内存泄漏。
析构函数：
- 在 RBTree 类的析构函数中调用 DeleteTree，确保当 RBTree 对象被销毁时，整个树也会被正确地删除，释放所有节点的内存。

删除整个红黑树的操作通过后序遍历实现，确保我们能从叶子节点开始，逐层删除树中的节点，防止在删除父节点后继续访问已被删除的子节点。这个过程不仅能正确地清除所有节点，而且能有效避免内存泄漏，是在管理动态内存时的一个重要技术细节。

4、红黑树的拓展

除了基本的插入、查找、删除等操作，红黑树还可以实现一些高级操作，如前序遍历、中序遍历、后序遍历、层序遍历、查找前驱和后继、区间查询、树的高度、判断是否是红黑树等。这些操作可以扩展红黑树的功能，增加其实用性。

4.1、红黑树的遍历

红黑树的遍历与普通二叉搜索树的遍历类似，可以通过三种常见的遍历方式：前序遍历、中序遍历和后序遍历来进行。红黑树本质上是一种二叉搜索树，因此它的遍历方式也遵循二叉搜索树的规则。然而，由于红黑树的平衡特性，我们可以更有效地进行遍历操作。在深入了解红黑树的遍历之前，我们先回顾一下三种基本的遍历方式：

前序遍历（Pre-order Traversal）：
按照 “根节点 -> 左子树 -> 右子树” 的顺序进行访问。在红黑树中，前序遍历可以用来复制树结构，或者在调试时观察节点的插入顺序。
中序遍历（In-order Traversal）：
按照 “左子树 -> 根节点 -> 右子树” 的顺序进行访问。由于红黑树是一种二叉搜索树，中序遍历可以将红黑树中的元素按关键字的升序进行输出，这也是红黑树在数据检索方面的一个重要特性。
后序遍历（Post-order Traversal）：
按照 “左子树 -> 右子树 -> 根节点” 的顺序进行访问。后序遍历通常用于删除操作，例如在删除树中的所有节点时，我们可以使用后序遍历来确保先删除子节点，再删除父节点。

下面我们将详细讨论如何在红黑树中实现这些遍历，并给出每种遍历方式的实现代码。

4.1.1、前序遍历（Pre-order Traversal）

前序遍历的特点是先访问根节点，然后递归地访问左子树和右子树。在红黑树中，由于需要保持树的平衡性，我们在遍历过程中可以观察节点的颜色和结构，了解树的状态。以下是红黑树的前序遍历实现：

前序遍历的递归实现：

// 前序遍历的递归实现
// 辅助函数
void _PreOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	
	// 访问根节点
	std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
	_PreOrder(root->_left);   // 访问左子树
	_PreOrder(root->_right);  // 访问右子树
}

void PreOrder()
{
    std::cout << "前序遍历: ";
    _PreOrder(_root);
    std::cout << std::endl;
}

前序遍历的非递归实现（使用栈）：

// 前序遍历的非递归实现
void PreOrder()
{
    if (_root == nullptr)
    {
    	return;
    }

    std::stack<Node *> stack;
    stack.push(_root);

    std::cout << "前序遍历: ";
    while (!stack.empty())
    {
        Node *cur = stack.top();
        stack.pop();
        // 访问根节点
        std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";

        // 先压入右子树再压入左子树（确保左子树先处理）
        if (cur->_right != nullptr)
        {
        	stack.push(cur->_right);
        }
        if (cur->_left != nullptr)
        {
        	stack.push(cur->_left);
        }
    }
    std::cout << std::endl;
}

4.1.2、中序遍历（In-order Traversal）

中序遍历是红黑树中最常用的遍历方式，因为它能够以升序输出树中的元素。在红黑树中进行中序遍历的过程与普通二叉搜索树类似，唯一的区别是我们可以在遍历时观察每个节点的颜色，这对于调试红黑树的平衡性非常有帮助。中序遍历的实现如下：

中序遍历的递归实现：

// 中序遍历
void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	_InOrder(root->_left);
	// 访问根节点
    std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
	_InOrder(root->_right);
}

void InOrder()
{
	std::cout << "中序遍历: ";
	_InOrder(_root);
	std::cout << std::endl;
}

中序遍历的非递归实现（使用栈）：

// 中序遍历 非递归
void InOrder()
{
	std::stack<Node*> stack;
	Node* cur = _root;

	std::cout << "中序遍历: ";
	while (cur != nullptr || !stack.empty()) {
		// 找到最左边的节点
		while (cur != nullptr) {
			stack.push(cur);
			cur = cur->_left;
		}

		// 处理当前节点
		cur = stack.top();
		stack.pop();
		// 访问根节点
        std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";

		// 转向右子树
		cur = cur->_right;
	}
	std::cout << std::endl;
}

4.1.3、后序遍历（Post-order Traversal）

后序遍历的特点是先访问子节点，然后访问根节点。对于红黑树，后序遍历通常用于需要在操作完成后对树进行清理的场景，例如删除整个树。通过后序遍历，我们可以确保在删除父节点之前先删除其子节点。以下是红黑树的后序遍历实现：

后序遍历的递归实现：

// 后序遍历的递归实现
// 辅助函数
void _PostOrder(Node* root) {
	if (root == nullptr)
	{
		return;
	}

	_PostOrder(root->_left);    // 访问左子树
	_PostOrder(root->_right);   // 访问右子树
	// 访问根节点
    std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
}

void PostOrder()
{
	std::cout << "后序遍历: ";
	_PostOrder(_root);
	std::cout << std::endl;
}

后序遍历的非递归实现（使用栈）：

// 后序遍历的非递归实现
void PostOrder()
{
	if (_root == nullptr)
	{
		return;
	}

	std::stack<Node*> st;
	Node* cur = _root;
	Node* lastNode = nullptr; // 最近访问的节点
	std::cout << "后序遍历: ";
	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->_left;
		}

		Node* top = st.top();
		if ((top->_right == nullptr) || (lastNode == top->_right))
		{
			// 访问根节点
			std::cout << top->_kv.first << " (" << (top->_colour == RED ? "RED" : "BLACK") << ") ";
			lastNode = top;
			st.pop();
		}
		else {
			cur = top->_right;
		}
	}
	std::cout << std::endl;
}

4.1.4、层序遍历（Level-order Traversal）

层序遍历是按层次逐层访问节点，先访问根节点，再访问其左右子节点，依次类推。可以使用队列来实现。

层序遍历的实现：

// 层序遍历
void LevelOrder()
{
    if (_root == nullptr)
    {
    	return;
    }

    std::queue<Node *> queue;
    queue.push(_root);

    std::cout << "层序遍历: " << std::endl;
    while (!queue.empty())
    {
        int size = queue.size();
        while (size--)
        {
            Node *cur = queue.front();
            queue.pop();
            // 访问当前节点
            std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";

            if (cur->_left != nullptr)
            {
            	queue.push(cur->_left); // 将左子树压入队列
            }
            if (cur->_right != nullptr)
            {
            	queue.push(cur->_right); // 将右子树压入队列
            }
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

测试代码：

int main
{
	int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    RBTree<int, int> t;
    for (const auto &e : a)
    {
        t.Insert(std::make_pair(e, e));
    }

    t.PreOrder();
    t.InOrder();
    t.PostOrder();
    t.LevelOrder();

	return 0;
}

4.1.5、遍历的复杂度分析

对于红黑树的遍历，无论是哪种遍历方式，时间复杂度均为 O(n) ，其中 n 为树中的节点数。这是因为遍历的过程需要访问树中的每个节点一次。由于红黑树的高度最多为 2log⁡(n+1) ，因此空间复杂度取决于递归调用的栈深度，为 O(log⁡n) 。

4.1.6、总结

红黑树的遍历与普通二叉搜索树的遍历相似，但它们在红黑树中的应用更为广泛。通过遍历操作，我们不仅可以按需访问红黑树中的数据，还能在调试和优化过程中观察树的结构和平衡性。中**序遍历是最常用的遍历方法之一，特别是在需要输出一个有序序列时。层序遍历则常用于按层次输出或分析树的结构。**每种遍历方法都有其独特的应用场景，了解和掌握红黑树的遍历对于深入理解其内部机制以及更好地应用红黑树至关重要。

4.2、查找后继节点

前驱是指比某个节点值小的最大节点，后继则是比某个节点值大的最小节点。在 AVL 树中，查找前驱和后继是常见的操作，尤其在区间查询或范围搜索时非常有用。

查找后继的递归实现：

// 查找后继节点
Node* findMin(Node* node)
{
	while (node->_left != nullptr)
	{
		node = node->_left;
	}
	return node;
}

Node *FindSuccessor(Node *node)
{
    if (node->_right != nullptr)
    {
    	return Minimum(node->_right);
    }

    Node *cur = _root;
    Node *successor = nullptr;
    while (cur != nullptr)
    {
        if (node->_kv.first < cur->_kv.first)
        {
            successor = cur;
            cur = cur->_left;
        }
        else if (node->_kv.first > cur->_kv.first)
        {
        	cur = cur->_right;
        }
        else
        {
        	break;
        }
    }
    return successor;
}

查找后继时，如果节点有右子树，则后继为右子树中最小的节点；否则，后继为第一个大于该节点的祖先节点。

4.3、查找前驱节点

查找前驱的递归实现：

// 查找前驱节点
Node* findMax(Node* node)
{
	while (node->_right != nullptr)
	{
		node = node->_right;
	}
	return node;
}

Node* FindPredecessor(Node* node)
{
	if (node->_left != nullptr)
	{
		return findMax(node->_left);
	}

	Node* cur = _root;
	Node* predecessor = nullptr;
	while (cur != nullptr)
	{
		if (node->_kv.first < cur->_kv.first)
		{
			cur = cur->_left;
		}
		else if (node->_kv.first > cur->_kv.first)
		{
			predecessor = cur;
			cur = cur->_right;
		}
		else
		{
			break;
		}
	}
	return predecessor;
}

前驱的查找逻辑与后继类似，只是方向相反。

4.4、判断是否是红黑树

判断一个二叉树是否为红黑树，需要验证红黑树的所有性质。红黑树有以下五个基本性质：

节点颜色性质： 每个节点要么是红色，要么是黑色。
根节点性质： 根节点必须是黑色。
叶子节点性质： 每个叶子节点（NIL或空节点）必须是黑色。
红色节点性质： 如果一个节点是红色，则它的两个子节点必须是黑色（即红色节点不能有红色的子节点）。
黑色高度性质： 从任何节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

判断是否为红黑树的步骤：

检查节点颜色： 确保所有节点的颜色合法。
检查根节点颜色： 确保根节点是黑色。
检查叶子节点颜色： 确保所有叶子节点是黑色。
检查红色节点性质： 确保所有红色节点的子节点是黑色。
检查黑色高度： 确保从根节点到每个叶子节点的路径上包含相同数量的黑色节点。

检测是否是红黑树的代码实现：

// 判断是否是红黑树
bool IsRBTree()
{
    // 空树也是红黑树
    if (_root == nullptr)
    {
    	return true;
    }

    // 1. 根是黑色
    if (_root->_colour != BLACK)
    {
        std::cout << "根节点不是黑色" << std::endl;
        return false;
    }

    // 获取任意一条路径上黑色节点的数量
    size_t blackCount = 0;
    Node *cur = _root;
    while (cur)
    {
    	if (cur->_colour == BLACK)
        {
        	blackCount++;
        }
        cur = cur->_left;
    }

    // 判断是否满足红黑树的性质, k 用来记录路径中黑色节点的个数
    size_t k = 0;
    return _IsRBTree(_root, k, blackCount);
}

bool _IsRBTree(Node *root, size_t k, size_t blackCount)
{
    // 走到 nullptr 之后, 判断 k 和 blackCount 是否相等
    if (root == nullptr)
    {
        // 最终黑色节点个数
        if (blackCount != k)
        {
            std::cout << "违反性质四: 每条路径中黑色节点的个数必须相等" << std::endl;
            return false;
        }
        return true;
    }

    // 统计黑色节点个数
    if (root->_colour == BLACK)
    {
    	k++;
    }

    // 检测当前节点与其父亲节点是否都为红色
    Node *parent = root->_parent;
    if (parent && parent->_colour == RED && root->_colour == RED)
    {
        std::cout << "违反了性质三: 红色节点的孩子必须是黑色" << std::endl;
        return false;
    }

    return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
}

判断一个二叉树是否为红黑树需要验证其是否满足红黑树的所有基本性质。通过递归地检查节点的颜色、根节点颜色、红色节点性质以及黑色高度，可以有效地判断一个二叉树是否符合红黑树的要求。这个检查过程确保了红黑树在插入和删除操作后能够保持其平衡特性，从而保证了其优良的时间复杂度性能。

5、完整实现代码和测试

5.1、RBTree.hpp

#pragma once

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

namespace Lenyiin
{
    enum Colour
    {
        RED,
        BLACK
    };

    template <class K, class V>
    struct RBTreeNode
    {
        RBTreeNode<K, V> *_left;
        RBTreeNode<K, V> *_right;
        RBTreeNode<K, V> *_parent;

        std::pair<K, V> _kv;
        Colour _colour;

        RBTreeNode(const std::pair<K, V> &kv)
            : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _colour(RED)
        {
        }
    };

    template <class K, class V>
    class RBTree
    {
    private:
        typedef RBTreeNode<K, V> Node;

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

            parent->_right = subRL;
            if (subRL)
            {
                subRL->_parent = parent;
            }
            subR->_left = parent;
            parent->_parent = subR;

            // 1. 原来 parent 是这棵树的根, 现在 subR 是根
            if (parent == _root)
            {
                _root = subR;
                subR->_parent = nullptr;
            }
            // 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置
            else
            {
                if (ppNode->_left == parent)
                {
                    ppNode->_left = subR;
                }
                else
                {
                    ppNode->_right = subR;
                }
                subR->_parent = ppNode;
            }
        }

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

            parent->_left = subLR;
            if (subLR)
            {
                subLR->_parent = parent;
            }
            subL->_right = parent;
            parent->_parent = subL;

            if (parent == _root)
            {
                _root = subL;
                subL->_parent = nullptr;
            }
            else
            {
                if (ppNode->_left == parent)
                {
                    ppNode->_left = subL;
                }
                else
                {
                    ppNode->_right = subL;
                }
                subL->_parent = ppNode;
            }
        }

        // 删除整个红黑树
        void DeleteTree(Node *root)
        {
            if (root == nullptr)
            {
                return;
            }

            // 递归删除左子树
            DeleteTree(root->_left);
            // 递归删除右子树
            DeleteTree(root->_right);

            // 删除当前节点
            delete root;
        }

    public:
        RBTree(Node *root = nullptr)
            : _root(root)
        {
        }

        ~RBTree()
        {
            DeleteTree(_root);
        }

        // 1. 空树。插入结点做根，把他变黑。
        // 2. 插入红色节点，他的父亲是黑色的，结束。
        // 3. 插入红色节点，他的父亲是红色的，可以推断他的祖父存在且一定为黑色。关键看叔叔
        //	a. 如果叔叔存在且为红，把父亲和叔叔变黑，祖父变红，继续往上处理。
        //	b. 如果叔叔存在且为黑，或者不存在。旋转（单旋 or 双旋）+ 变色
        bool Insert(const std::pair<K, V> &kv)
        {
            // 1. 按照搜索树的规则进行插入
            // 如果树为空，直接将新节点设为根节点，并染成黑色
            if (_root == nullptr)
            {
                _root = new Node(kv);
                _root->_colour = BLACK; // 根节点是黑色的
                return true;
            }

            // 遍历树找到插入位置
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_kv.first > kv.first)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (cur->_kv.first < kv.first)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    return false; // 待插入的节点已经存在
                }
            }

            // 找到位置 插入新节点
            cur = new Node(kv);
            if (parent->_kv.first > kv.first)
            {
                parent->_left = cur;
                cur->_parent = parent;
            }
            else
            {
                parent->_right = cur;
                cur->_parent = parent;
            }

            // 插入调整
            InsertFixUp(parent, cur);

            return true;
        }

        void InsertFixUp(Node *parent, Node *cur)
        {
            // 调整结点颜色
            // 新结点给红的还是黑的?	红色
            // 1. 空树。插入结点做根, 把他变黑。
            // 2. 插入红色节点, 他的父亲是黑色的, 结束。
            // 3. 插入红色节点, 他的父亲是红色的, 可以推断他的祖父存在且一定为黑色。关键看叔叔
            //	a. 如果叔叔存在且为红, 把父亲和叔叔变黑, 祖父变红, 继续往上处理。
            //	b. 如果叔叔存在且为黑, 或者不存在。旋转（单旋 or 双旋）+ 变色
            while (parent && parent->_colour == RED)
            {
                // 关键看叔叔
                Node *grandfather = parent->_parent;
                if (grandfather->_left == parent)
                {
                    Node *uncle = grandfather->_right;

                    // 情况1: uncle 存在, 且为红
                    if (uncle && uncle->_colour == RED)
                    {
                        parent->_colour = uncle->_colour = BLACK;
                        grandfather->_colour = RED;

                        // 继续向上调整
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    // 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑
                    else
                    {
                        // 情况 3: 双旋 -> 变成单旋
                        if (cur == parent->_right)
                        {
                            RotateL(parent);
                            std::swap(parent, cur);
                        }

                        // 第二种情况 (ps: 有可能是第三种情况变过来的)
                        RotateR(grandfather);
                        grandfather->_colour = RED;
                        parent->_colour = BLACK;

                        break;
                    }
                }
                else
                {
                    Node *uncle = grandfather->_left;

                    // 情况1: uncle 存在, 且为红
                    if (uncle && uncle->_colour == RED)
                    {
                        parent->_colour = BLACK;
                        uncle->_colour = BLACK;
                        grandfather->_colour = RED;

                        // 继续向上调整
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    // 情况2 or 情况3: uncle 不存在 or uncle 存在且为黑
                    else
                    {
                        // 情况3: 双旋 -> 变为单旋
                        if (cur == parent->_left)
                        {
                            RotateR(parent);
                            std::swap(parent, cur);
                        }

                        // 第二种情况 (ps: 有可能是第三种情况变来的)
                        RotateL(grandfather);
                        grandfather->_colour = RED;
                        parent->_colour = BLACK;

                        break;
                    }
                }
            }

            // 保证根节点为黑色
            _root->_colour = BLACK;
        }

        // 删除操作
        bool Erase(const K &key)
        {
            // 查找节点
            Node *nodeToDelete = _root;
            while (nodeToDelete)
            {
                if (nodeToDelete->_kv.first > key)
                {
                    nodeToDelete = nodeToDelete->_left;
                }
                else if (nodeToDelete->_kv.first < key)
                {
                    nodeToDelete = nodeToDelete->_right;
                }
                else
                {
                    break; // 找到待删除的节点
                }
            }

            // 如果未找到节点
            if (nodeToDelete == nullptr)
            {
                return false;
            }

            // 执行删除操作
            Node *parent, *child;
            Colour originalColour = nodeToDelete->_colour;

            if (nodeToDelete->_left == nullptr)
            {
                child = nodeToDelete->_right;
                parent = nodeToDelete->_parent;
                Transplant(nodeToDelete, nodeToDelete->_right);
            }
            else if (nodeToDelete->_right == nullptr)
            {
                child = nodeToDelete->_left;
                parent = nodeToDelete->_parent;
                Transplant(nodeToDelete, nodeToDelete->_left);
            }
            else
            {
                Node *successor = Minimum(nodeToDelete->_right);
                originalColour = successor->_colour;
                child = successor->_right;
                if (successor->_parent == nodeToDelete)
                {
                    parent = successor;
                }
                else
                {
                    Transplant(successor, successor->_right);
                    successor->_right = nodeToDelete->_right;
                    successor->_right->_parent = successor;
                    parent = successor->_parent;
                }
                Transplant(nodeToDelete, successor);
                successor->_left = nodeToDelete->_left;
                successor->_left->_parent = successor;
                successor->_colour = nodeToDelete->_colour;
            }

            delete nodeToDelete;

            // 如果删除的节点是黑色，需要进行调整
            if (originalColour == BLACK)
            {
                EraseFixUp(child, parent);
            }

            return true;
        }

        void EraseFixUp(Node *x, Node *parent)
        {
            while (x != _root && (x == nullptr || x->_colour == BLACK))
            {
                if (x == parent->_left)
                {
                    Node *w = parent->_right;
                    // 情况1: x的兄弟节点w是红色的
                    if (w->_colour == RED)
                    {
                        w->_colour = BLACK;
                        parent->_colour = RED;
                        RotateL(parent);
                        w = parent->_right;
                    }
                    // 情况2: x的兄弟节点w是黑色的，且w的两个子节点都是黑色的
                    if ((w->_left == nullptr || w->_left->_colour == BLACK) &&
                        (w->_right == nullptr || w->_right->_colour == BLACK))
                    {
                        w->_colour = RED;
                        x = parent;
                        parent = x->_parent;
                    }
                    else
                    {
                        // 情况3: w是黑色的，并且w的左子节点是红色，右子节点是黑色
                        if (w->_right == nullptr || w->_right->_colour == BLACK)
                        {
                            if (w->_left)
                                w->_left->_colour = BLACK;
                            w->_colour = RED;
                            RotateR(w);
                            w = parent->_right;
                        }
                        // 情况4: w是黑色的，并且w的右子节点是红色
                        if (w)
                        {
                            w->_colour = parent->_colour;
                            parent->_colour = BLACK;
                            if (w->_right)
                                w->_right->_colour = BLACK;
                            RotateL(parent);
                        }
                        x = _root;
                        break;
                    }
                }
                else
                {
                    Node *w = parent->_left;
                    // 情况1: x的兄弟节点w是红色的
                    if (w->_colour == RED)
                    {
                        w->_colour = BLACK;
                        parent->_colour = RED;
                        RotateR(parent);
                        w = parent->_left;
                    }
                    // 情况2: x的兄弟节点w是黑色的，且w的两个子节点都是黑色的
                    if ((w->_left == nullptr || w->_left->_colour == BLACK) &&
                        (w->_right == nullptr || w->_right->_colour == BLACK))
                    {
                        w->_colour = RED;
                        x = parent;
                        parent = x->_parent;
                    }
                    else
                    {
                        // 情况3: w是黑色的，并且w的右子节点是红色，左子节点是黑色
                        if (w->_left == nullptr || w->_left->_colour == BLACK)
                        {
                            if (w->_right)
                            {
                                w->_right->_colour = BLACK;
                            }
                            w->_colour = RED;
                            RotateL(w);
                            w = parent->_left;
                        }
                        // 情况4: w是黑色的，并且w的左子节点是红色
                        if (w)
                        {
                            w->_colour = parent->_colour;
                            parent->_colour = BLACK;
                            if (w->_left)
                            {
                                w->_left->_colour = BLACK;
                            }
                            RotateR(parent);
                        }
                        x = _root;
                        break;
                    }
                }
            }

            if (x)
            {
                x->_colour = BLACK;
            }
        }

        Node *Minimum(Node *node)
        {
            while (node->_left != nullptr)
            {
                node = node->_left;
            }
            return node;
        }

        void Transplant(Node *u, Node *v)
        {
            if (u->_parent == nullptr)
            {
                _root = v;
            }
            else if (u == u->_parent->_left)
            {
                u->_parent->_left = v;
            }
            else
            {
                u->_parent->_right = v;
            }

            if (v != nullptr)
            {
                v->_parent = u->_parent;
            }
        }

        // 查找节点
        Node *Find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_kv.first > key)
                {
                    cur = cur->_left;
                }
                else if (cur->_kv.first < key)
                {
                    cur = cur->_right;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }

        // 前序遍历的递归实现
        // 辅助函数
        // void _PreOrder(Node *root)
        // {
        //     if (root == nullptr)
        //     {
        //         return;
        //     }

        //     // 访问根节点
        //     std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
        //     _PreOrder(root->_left);  // 访问左子树
        //     _PreOrder(root->_right); // 访问右子树
        // }

        // void PreOrder()
        // {
        //     std::cout << "前序遍历: ";
        //     _PreOrder(_root);
        //     std::cout << std::endl;
        // }

        // 前序遍历的非递归实现
        void PreOrder()
        {
            if (_root == nullptr)
            {
                return;
            }

            std::stack<Node *> stack;
            stack.push(_root);

            std::cout << "前序遍历: ";
            while (!stack.empty())
            {
                Node *cur = stack.top();
                stack.pop();
                // 访问根节点
                std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";

                // 先压入右子树再压入左子树（确保左子树先处理）
                if (cur->_right != nullptr)
                {
                    stack.push(cur->_right);
                }
                if (cur->_left != nullptr)
                {
                    stack.push(cur->_left);
                }
            }
            std::cout << std::endl;
        }

        // 中序遍历
        // void _InOrder(Node *root)
        // {
        //     if (root == nullptr)
        //     {
        //         return;
        //     }

        //     _InOrder(root->_left);
        //     // 访问根节点
        //     std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
        //     _InOrder(root->_right);
        // }

        // void InOrder()
        // {
        //     std::cout << "中序遍历: ";
        //     _InOrder(_root);
        //     std::cout << std::endl;
        // }

        // 中序遍历 非递归
        void InOrder()
        {
            std::stack<Node *> stack;
            Node *cur = _root;

            std::cout << "中序遍历: ";
            while (cur != nullptr || !stack.empty())
            {
                // 找到最左边的节点
                while (cur != nullptr)
                {
                    stack.push(cur);
                    cur = cur->_left;
                }

                // 处理当前节点
                cur = stack.top();
                stack.pop();
                // 访问根节点
                std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";

                // 转向右子树
                cur = cur->_right;
            }
            std::cout << std::endl;
        }

        // 后序遍历的递归实现
        // 辅助函数
        // void _PostOrder(Node *root)
        // {
        //     if (root == nullptr)
        //     {
        //         return;
        //     }

        //     _PostOrder(root->_left);  // 访问左子树
        //     _PostOrder(root->_right); // 访问右子树
        //     // 访问根节点
        //     std::cout << root->_kv.first << " (" << (root->_colour == RED ? "RED" : "BLACK") << ") ";
        // }

        // void PostOrder()
        // {
        //     std::cout << "后序遍历: ";
        //     _PostOrder(_root);
        //     std::cout << std::endl;
        // }

        // 后序遍历的非递归实现
        void PostOrder()
        {
            if (_root == nullptr)
            {
                return;
            }

            std::stack<Node *> st;
            Node *cur = _root;
            Node *lastNode = nullptr; // 最近访问的节点
            std::cout << "后序遍历: ";
            while (cur || !st.empty())
            {
                while (cur)
                {
                    st.push(cur);
                    cur = cur->_left;
                }

                Node *top = st.top();
                if ((top->_right == nullptr) || (lastNode == top->_right))
                {
                    // 访问当前节点
                    std::cout << top->_kv.first << " (" << (top->_colour == RED ? "RED" : "BLACK") << ") ";
                    lastNode = top;
                    st.pop();
                }
                else
                {
                    cur = top->_right;
                }
            }
            std::cout << std::endl;
        }

        // 层序遍历
        void LevelOrder()
        {
            if (_root == nullptr)
            {
                return;
            }

            std::queue<Node *> queue;
            queue.push(_root);

            std::cout << "层序遍历: " << std::endl;
            while (!queue.empty())
            {
                int size = queue.size();
                while (size--)
                {
                    Node *cur = queue.front();
                    queue.pop();
                    // 访问当前节点
                    std::cout << cur->_kv.first << " (" << (cur->_colour == RED ? "RED" : "BLACK") << ") ";

                    if (cur->_left != nullptr)
                    {
                        queue.push(cur->_left); // 将左子树压入队列
                    }
                    if (cur->_right != nullptr)
                    {
                        queue.push(cur->_right); // 将右子树压入队列
                    }
                }
                std::cout << std::endl;
            }
            std::cout << std::endl;
        }

        // 查找后继节点
        Node *findMin(Node *node)
        {
            while (node->_left != nullptr)
            {
                node = node->_left;
            }
            return node;
        }

        Node *FindSuccessor(Node *node)
        {
            if (node->_right != nullptr)
            {
                return findMin(node->_right);
            }

            Node *cur = _root;
            Node *successor = nullptr;
            while (cur != nullptr)
            {
                if (node->_kv.first < cur->_kv.first)
                {
                    successor = cur;
                    cur = cur->_left;
                }
                else if (node->_kv.first > cur->_kv.first)
                {
                    cur = cur->_right;
                }
                else
                {
                    break;
                }
            }
            return successor;
        }

        // 查找前驱节点
        Node *findMax(Node *node)
        {
            while (node->_right != nullptr)
            {
                node = node->_right;
            }
            return node;
        }

        Node *FindPredecessor(Node *node)
        {
            if (node->_left != nullptr)
            {
                return findMax(node->_left);
            }

            Node *cur = _root;
            Node *predecessor = nullptr;
            while (cur != nullptr)
            {
                if (node->_kv.first < cur->_kv.first)
                {
                    cur = cur->_left;
                }
                else if (node->_kv.first > cur->_kv.first)
                {
                    predecessor = cur;
                    cur = cur->_right;
                }
                else
                {
                    break;
                }
            }
            return predecessor;
        }

        // 判断是否是红黑树
        bool IsRBTree()
        {
            // 空树也是红黑树
            if (_root == nullptr)
            {
                return true;
            }

            // 1. 根是黑色
            if (_root->_colour != BLACK)
            {
                std::cout << "根节点不是黑色" << std::endl;
                return false;
            }

            // 获取任意一条路径上黑色节点的数量
            size_t blackCount = 0;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_colour == BLACK)
                {
                    blackCount++;
                }
                cur = cur->_left;
            }

            // 判断是否满足红黑树的性质, k 用来记录路径中黑色节点的个数
            size_t k = 0;
            return _IsRBTree(_root, k, blackCount);
        }

        bool _IsRBTree(Node *root, size_t k, size_t blackCount)
        {
            // 走到 nullptr 之后, 判断 k 和 blackCount 是否相等
            if (root == nullptr)
            {
                // 最终黑色节点个数
                if (blackCount != k)
                {
                    std::cout << "违反性质四: 每条路径中黑色节点的个数必须相等" << std::endl;
                    return false;
                }
                return true;
            }

            // 统计黑色节点个数
            if (root->_colour == BLACK)
            {
                k++;
            }

            // 检测当前节点与其父亲节点是否都为红色
            Node *parent = root->_parent;
            if (parent && parent->_colour == RED && root->_colour == RED)
            {
                std::cout << "违反了性质三: 红色节点的孩子必须是黑色" << std::endl;
                return false;
            }

            return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
        }

    private:
        Node *_root;
    };
}

5.2、RBTree.cc

#include "RBTree.hpp"
#include "AVLTree.hpp"

using namespace Lenyiin;

void test_RBTree()
{
    // int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    RBTree<int, int> t;
    for (const auto &e : a)
    {
        t.Insert(std::make_pair(e, e));
    }

    t.PreOrder();
    t.InOrder();
    t.PostOrder();
    t.LevelOrder();

    std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;

    auto node = t.Find(5);
    if (node != nullptr)
    {
        std::cout << node->_kv.first << std::endl;
    }
    else
    {
        std::cout << "没找到" << std::endl;
    }

    auto pre = t.FindPredecessor(node);
    if (pre != nullptr)
    {
        std::cout << node->_kv.first << " 的前驱节点是: " << pre->_kv.first << std::endl;
    }
    else
    {
        std::cout << "前驱节点为空" << std::endl;
    }

    auto suc = t.FindSuccessor(node);
    if (suc != nullptr)
    {
        std::cout << node->_kv.first << " 的后继节点是: " << suc->_kv.first << std::endl;
    }
    else
    {
        std::cout << "后继节点为空" << std::endl;
    }

    t.Erase(7);
    t.LevelOrder();
    std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;

    t.Erase(15);
    t.LevelOrder();
    std::cout << "IsRBTree ? " << t.IsRBTree() << std::endl;
}

void testRB_AVLTree()
{
    const int n = 100000;
    vector<int> v;
    v.reserve(n);
    srand(time(0));
    for (size_t i = 0; i < n; i++)
    {
        v.push_back(rand());
    }

    RBTree<int, int> rbtree;
    AVLTree<int, int> avltree;

    size_t begin1 = clock();
    for (const auto &e : v)
    {
        rbtree.Insert(make_pair(e, e));
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    for (const auto &e : v)
    {
        avltree.Insert(make_pair(e, e));
    }
    size_t end2 = clock();

    std::cout << "红黑树测试时间：" << end1 - begin1 << std::endl;
    std::cout << "AVL 测试时间：\t" << end2 - begin2 << std::endl;
}

int main()
{
    test_RBTree();
    testRB_AVLTree();

    return 0;
}

5.3、测试结果

这里使用的 AVL 树的源码使用的是我的这篇博客所讲解的源代码：《 C++ 修炼全景指南：十七》自平衡的艺术：深入了解 AVL 树的核心原理与实现

6、红黑树的高级拓展

6.1、红黑树的实际应用

红黑树作为一种高效的自平衡二叉搜索树，在计算机科学和实际工程中有广泛的应用。它的高效性和稳定性使其成为许多系统和算法的首选数据结构。下面，我们将探讨红黑树在实际应用中的一些典型案例，并分析其在这些场景中的优势和作用。

6.1.1、红黑树在标准库中的应用

1、C++ STL 中的 std::map 和 std::set

std::map：在 C++ 标准模板库(STL)中，std::map 是一个关联容器，用于存储键值对，并按照键的顺序进行排序。底层实现通常使用红黑树。这是因为红黑树能够保证在最坏情况下，插入、删除和查找操作的时间复杂度都是 O(log⁡n) ，这是非常理想的性能表现。
std::set：类似于 std::map，std::set 是一个集合容器，它存储唯一的元素，并按照顺序排列。红黑树作为底层数据结构，使得 std::set 在插入、删除和查找操作时，能够高效地保持元素的有序性。

在这些容器中，红黑树的自平衡特性确保了在大量元素插入或删除操作后，树的高度始终保持在 O(log⁡n) ，从而保证了操作的高效性。

2、Java 中的 TreeMap 和 TreeSet

在 Java 的集合框架中，TreeMap 和 TreeSet 的底层实现也采用了红黑树。TreeMap 用于存储键值对，并保证键的顺序；TreeSet 则用于存储唯一的元素，并按照元素的顺序进行排序。
红黑树在这些容器中的应用与 C++ STL 中类似，通过自平衡特性，保证了操作的时间复杂度稳定在 O(log⁡n) 。

6.1.2、操作系统中的红黑树

1、虚拟内存管理

Linux 内核的虚拟内存管理：红黑树在 Linux 内核中被用于虚拟内存区域(VMA，Virtual Memory Area)的管理。每个进程的虚拟地址空间被划分为多个区域，每个区域代表一个连续的虚拟地址范围。为了高效地查找、分配和回收虚拟内存区域，Linux 内核使用红黑树来组织这些区域。
红黑树在这里的主要作用是通过快速查找操作，来定位某个地址属于哪个虚拟内存区域，以及在分配新区域时，快速找到合适的位置。这一操作的时间复杂度为 O(log⁡n) ，非常适合操作系统的实时性需求。

2、进程调度

在某些操作系统中，红黑树也被用于进程调度队列的管理。调度器需要频繁地插入、删除和查找进程，以确定下一个要执行的进程。红黑树的平衡特性可以保证这些操作在最坏情况下的时间复杂度是 O(log⁡n) ，从而提高调度的效率。

6.1.3、数据库中的红黑树

1、索引结构

内存数据库中的索引：在一些内存数据库中，如 Redis，红黑树被用作数据的索引结构。红黑树能够提供快速的键值查找、插入和删除操作，使得数据在内存中的存取效率得以提高。
二级索引：在一些数据库系统中，红黑树被用于实现二级索引。二级索引用于加速对非主键列的查询操作，而红黑树的有序性可以使得范围查询更加高效。

2、日志结构化存储

在一些日志结构化存储系统中，数据的插入和检索操作非常频繁。红黑树通过其自平衡特性，能够有效地组织和管理这些数据，从而提供高效的插入和检索性能。

6.1.4、网络应用中的红黑树

1、路由表

在计算机网络中，路由器需要维护一个庞大的路由表，用于决定数据包的转发路径。为了在大量的路由条目中快速查找目的地，红黑树被用于组织和管理这些路由条目。红黑树的平衡特性使得路由表的查找、插入和删除操作都能在 O(log⁡n) 的时间内完成。

2、HTTP 服务器

在一些高性能 HTTP 服务器中，如 Nginx，红黑树被用于管理服务器中的各类资源，如连接、定时器等。通过红黑树，可以高效地组织和管理这些资源，从而提高服务器的性能和响应速度。

6.1.5、实际案例中的性能分析

红黑树在这些实际应用中的性能表现主要体现在以下几个方面：

高效性：在各种应用场景中，红黑树能够保证操作的时间复杂度为 O(log⁡n) ，这在大量数据的插入、删除和查找操作中，表现出高效的性能。
稳定性：红黑树的自平衡特性使得它在最坏情况下的性能也能得到保证，避免了普通二叉搜索树退化为链表的情况。
灵活性：红黑树可以被灵活地应用于各种场景，如内存管理、索引结构、路由表等，充分发挥其自平衡和有序性的优势。

6.1.6、实现中的关键点

在实际应用中，红黑树的实现需要注意以下几个关键点：

平衡性维护：红黑树的核心在于通过旋转和重新着色来保持树的平衡，这直接关系到其性能。因此，在实现中，需要精心设计插入和删除操作，以保证树的平衡性。
空间优化：在实际工程中，红黑树的空间消耗也是一个需要考虑的问题。为了降低空间开销，可以使用对象池或内存池来管理节点的分配和释放。
并发控制：在多线程环境下，需要考虑红黑树的线程安全性。可以采用读写锁、分段锁定等技术来提高并发性能。

6.2、性能优化

6.2.1、预取和缓存优化

缓存局部性：由于红黑树的节点存储在堆上，节点的访问在内存中可能是非连续的。这会导致缓存未命中，从而影响性能。为了优化缓存局部性，可以考虑在节点较少的情况下，使用数组而非指针进行存储，这样可以使节点存储在一块连续的内存区域中，提高缓存命中率。
预取优化：在插入、删除和查找操作中，可以预先访问下一个节点。这可以利用现代处理器的预取机制，从而减少内存访问延迟。

6.2.2、减少旋转和重新着色

旋转操作优化：旋转操作在红黑树中是相对较重的操作，因为它涉及到节点指针的多次修改。通过优化插入和删除算法，尽量减少旋转的次数，可以提高性能。例如，在某些情况下，可以通过重新着色来代替旋转，以保持红黑树的平衡。
路径压缩：在删除操作中，通过路径压缩技术可以在调整过程中减少访问节点的次数，从而提高性能。

6.2.3、并行化和并发优化

读写分离：在多线程环境下，如果红黑树的读操作远远多于写操作，可以采用读写分离策略，将读操作分离出来，避免写操作锁住整棵树，从而提高并发性能。
分段锁定：在插入和删除操作中，可以采用分段锁定策略，只对局部的子树进行锁定，而不是锁定整棵树。这种方式可以提高多线程环境下的性能。

6.2.4、改进红黑树的变体

红黑树的调整：虽然红黑树的基本性质保证了操作的平衡性，但在某些特殊场景中，红黑树的性能可能不如其他平衡树，例如 AVL 树。在这些情况下，可以考虑使用红黑树的变体，例如结合自适应算法，根据实际数据分布情况动态调整红黑树的结构，以获得更优的性能。

6.2.5、实际应用场景中的优化

在实际应用中，红黑树通常用作关联容器的底层数据结构，如 C++ 标准库中的 std::map 和 std::set。在这些应用中，红黑树的性能优化主要体现在以下几个方面：

内存分配优化：由于红黑树频繁进行插入和删除操作，因此需要频繁地进行内存分配和释放。为了提高性能，可以使用自定义的内存池或对象池来减少内存分配的开销。
大数据优化：在处理大数据集时，可以将红黑树的节点分配到多台机器上，并通过分布式算法对红黑树进行操作。这种方式可以显著提高红黑树在大规模数据处理中的性能。

6.2.6、实现代码示例

在实际的红黑树实现中，我们可以通过以下方式优化性能：

template <class K, class V>
class RBTree {
public:
    // 查找、插入、删除等操作略

    // 自定义内存池，用于优化内存分配
    void* operator new(size_t size) {
        // 内存池分配逻辑
    }

    void operator delete(void* ptr) {
        // 内存池释放逻辑
    }

private:
    Node<K, V>* _root;

    // 旋转、插入调整、删除调整等操作略
};

通过使用自定义的内存分配器，我们可以减少频繁的内存分配和释放操作对性能的影响。在多线程环境中，我们还可以使用线程安全的内存池，以进一步提高性能。

6.3、进阶拓展

红黑树作为一种经典的平衡二叉搜索树，已经在各种实际应用中展现出了其高效性和稳定性。然而，在一些特定场景和高级应用中，红黑树还可以进行拓展和优化，以适应更复杂的需求。下面将讨论一些红黑树的高级主题，包括多线程环境下的红黑树、持久化红黑树、结合哈希表的红黑树等。

6.3.1、多线程环境下的红黑树

1、多线程并发访问问题

在多线程环境中，红黑树需要解决并发访问的问题。由于红黑树的插入和删除操作涉及到旋转和重新着色，这些操作都可能破坏树的平衡性，因此需要进行同步控制以保证树结构的完整性。
一种简单的方法是使用全局锁，在对红黑树进行插入、删除等操作时，锁定整个树。然而，这种方法在高并发情况下会导致严重的性能瓶颈。

2、细粒度锁定策略

为了提高并发性能，可以采用细粒度锁定策略。具体而言，可以对红黑树中的节点或子树进行锁定，从而允许多个线程同时进行操作。以下是几种常用的细粒度锁定策略：
- 读写锁：对树的读操作和写操作分别使用不同的锁，从而允许多个线程同时读取树，而写操作则需要独占锁。
- 分段锁定：将红黑树分为多个独立的区域（段），每个区域维护一个独立的锁，从而允许多个线程在不同区域内同时进行操作。
- 手动锁定节点：在插入和删除操作中，仅对受影响的节点进行锁定，以最小化锁的粒度。

3、乐观并发控制

除了锁定策略，还可以使用乐观并发控制技术，例如版本号或时间戳。当线程尝试对节点进行修改时，首先检查节点的版本号是否发生变化，如果没有变化则进行修改，否则重新尝试。这种策略适用于读多写少的场景，能够在一定程度上提高并发性能。

6.3.2、持久化红黑树

1、持久化数据结构的概念

持久化数据结构是一种在对数据结构进行修改时，保留原始版本的技术。持久化红黑树在插入或删除节点时，不会直接修改原来的树，而是创建一个新的版本。这样，所有的历史版本都可以被访问，提供了对数据结构的时态回溯能力。

2、实现方法

持久化红黑树的实现可以采用 “路径复制” 策略。在插入或删除节点时，只对受影响的节点进行复制，而其他部分共享原始树中的节点。这样，可以有效地利用内存空间，同时保留树的历史版本。

例如，在插入一个节点时，只需要复制插入路径上的节点，并将新节点链接到新路径上。其他不受影响的部分则与原树共享。如下图所示：

原始树:       5                新版本树:       5'
           /   \                           /   \
          3     8                         3     8
         / \                             / \   
        2   4                           2   4
                                         \
                                          7

3、优势和应用

持久化红黑树在一些需要保存数据历史记录的应用中非常有用。例如，版本控制系统、数据库的时间旅行查询 (Time-Travel Queries) 等。它允许在 O(log⁡n) 的时间复杂度下进行版本切换和数据查询，并且具有很好的空间效率。

6.3.3、结合哈希表的红黑树

1、红黑树与哈希表的融合

红黑树与哈希表可以结合，形成一种更高效的数据结构。哈希表可以在 O(1) 时间复杂度下进行插入、删除和查找操作，但在处理大量冲突时性能会退化。而红黑树的性能稳定，但在某些情况下无法达到哈希表的常数级别效率。
通过结合哈希表和红黑树，可以在绝大多数情况下获得 O(1) 的性能，而在发生哈希冲突时使用红黑树来维持性能稳定。例如，Java 的 HashMap 在处理大量冲突时，将链表转换为红黑树，以保证查找操作的效率。

2、实现细节

在哈希表中，每个桶（bucket）通常使用链表来存储冲突的元素。当链表中的元素数量超过一定阈值时，将链表转换为红黑树。这样可以在冲突严重的情况下，保证查找操作的性能不至于退化到线性级别。
在实现上，需要在哈希表的插入、删除和查找操作中增加红黑树的逻辑。当桶中的元素数量减少到一定阈值以下时，可以将红黑树重新转换为链表。

3、应用场景

这种结合的数据结构广泛应用于实际工程中。例如，Java 的 HashMap 和 ConcurrentHashMap 在 JDK 1.8 之后都引入了红黑树的逻辑，以优化哈希冲突的性能。
在分布式系统中，结合哈希表和红黑树的数据结构可以用来实现高效的分布式缓存、负载均衡等功能。

6.3.4、红黑树与其他平衡树的比较

1、红黑树 vs. AVL 树

插入和删除操作：AVL 树的平衡性更严格，因此插入和删除操作往往需要更多的旋转次数，性能可能略低于红黑树。红黑树由于平衡性较弱，插入和删除操作相对更高效。
查找操作：由于 AVL 树的平衡性更好，树的高度更低，因此在查找操作中，AVL 树可能稍微快于红黑树。但这个差距通常可以忽略不计。

2、红黑树 vs. B 树

用途：红黑树适用于内存中数据的组织，而 B 树主要用于外存数据的管理，例如数据库索引和文件系统。
节点结构：B 树的每个节点可以包含多个元素，因此更适合磁盘存储。红黑树的每个节点只包含一个元素，更适合在内存中使用。

6.3.5、小结

红黑树作为一种自平衡二叉搜索树，不仅在基本操作上具有优秀的性能，而且在实际应用中可以通过拓展和优化来满足更复杂的需求。无论是在多线程环境中的并发访问控制，还是在持久化数据结构和哈希表优化中，红黑树都展现出了强大的灵活性和适应性。通过深入理解红黑树的高级主题，我们可以更好地将其应用到实际工程中，从而提升系统的整体性能和效率。

7、总结

红黑树作为一种自平衡二叉搜索树，在结构设计和操作维护方面都体现了深刻的算法思想和技术细节。在前面的各个部分中，我们深入探讨了红黑树的结构与性质、操作与维护、性能分析与优化、实际应用以及拓展主题。现在，我们将这些内容进行全面的概括，强调红黑树的核心特性以及其在实际开发中的重要性。

7.1、红黑树的结构与性质

红黑树通过严格的五个性质（节点的红黑性、根节点必须为黑色、红色节点的子节点为黑色、从任一节点到叶子的每条路径上黑色节点数相同、每个叶子节点都是黑色的空节点）来保持树的近似平衡。这种近似平衡的特点使得红黑树在最坏情况下的高度仅为 2log⁡(n+1) ，从而确保了查找、插入、删除操作的时间复杂度都维持在 O(log⁡n) 。

7.2、红黑树的插入与删除操作

红黑树的插入与删除操作是其最具挑战性的部分，需要在保持二叉搜索树性质的同时维持树的平衡。插入操作中，我们首先将新节点插入为红色，然后通过颜色调整和必要的旋转来修复因插入导致的红黑性质破坏。通过引入 “叔叔节点” 概念，我们对不同的插入情况进行了细致的分类和处理，确保了树的自平衡。

删除操作更为复杂，涉及到删除节点的颜色和结构调整，特别是处理 “双黑” 节点的情况。为了恢复树的平衡，我们引入了 “兄弟节点” 的概念，通过一系列颜色调整和旋转操作，确保删除后的红黑树仍然满足红黑性质。

7.3、红黑树的旋转操作

旋转操作是红黑树自平衡的核心。红黑树的两种旋转操作（左旋和右旋）通过调整节点之间的连接关系，重新分配子树的高度，从而在插入和删除过程中恢复树的平衡。左旋和右旋操作的实现需要细致地调整节点指针，同时保持二叉搜索树的有序性，这在插入和删除修复过程中起到了关键作用。

7.4、红黑树的查找操作

红黑树的查找操作利用了二叉搜索树的特性，从根节点开始，根据比较结果逐层深入。由于红黑树的高度在 O(log⁡n) 范围内，查找操作的效率得到了有效保证。通过查找操作，我们可以快速定位红黑树中的某个节点，为插入、删除等其他操作提供支持。

7.5、实际应用与拓展

红黑树在理论上保证了 O(log⁡n) 的操作性能，这在处理大规模数据时表现尤为突出。通过性能分析，我们了解到红黑树在不同操作场景下的时间复杂度和空间复杂度，这为我们优化红黑树提供了依据。在实际应用中，我们可以根据具体需求对红黑树进行调整，如优化旋转次数、减少颜色调整等，以提升整体性能。

红黑树在实际应用中非常广泛，如在 STL 中用于实现 std::map 和 std::set 等有序容器，在数据库系统中用作索引结构，以及在操作系统中用于管理内存分配等。通过这些实际应用，我们看到了红黑树在各种复杂系统中的高效性和可靠性。拓展主题中，我们探讨了红黑树在多线程环境、持久化数据结构等高级场景中的应用，进一步挖掘了红黑树的潜力。

7.6、总结

红黑树通过巧妙的结构设计和精确的操作维护，成功地解决了二叉搜索树在插入和删除操作时可能出现的失衡问题。它在不牺牲查找效率的前提下，保持了树的平衡，使得插入、删除、查找操作都能在 O(log⁡n) 的时间内完成。通过对红黑树的深入研究，我们不仅掌握了其实现细节，更理解了其在不同应用场景中的优势和局限性。

在实际开发中，红黑树为我们提供了一个可靠的平衡搜索树解决方案。无论是用于实现高效的有序数据容器，还是在复杂系统中充当关键的性能保障组件，红黑树都展现出了其独特的价值。通过对红黑树的学习和实践，我们不仅能够提升算法设计和数据结构的水平，更能在软件开发中应用这一强大的工具，构建出性能卓越的系统。

希望这篇博客对您有所帮助，也欢迎您在此基础上进行更多的探索和改进。如果您有任何问题或建议，欢迎在评论区留言，我们可以共同探讨和学习。更多知识分享可以访问 我的个人博客网站。本博客所涉及的代码也可以从 CSDN 下载区下载

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

开放原子开发者工作坊

所有评论(0)

查看更多评论

Lenyiin

@mmlhbjk

已为社区贡献7条内容

《 C++ 修炼全景指南：十八 》穿越数据的红与黑：掌握数据平衡的极致艺术

Lenyiin

摘要

1、引言

1.1、红黑树的背景和意义

1.2、红黑树的研究目的

1.3、内容结构

2、红黑树的理论基础

2.1、二叉搜索树的局限性

2.2、平衡树的概念

2.3、红黑树的起源

2.4、红黑树的结构与性质

2.4.1、红黑树的节点结构

2.4.2、红黑树的五大性质

2.4.3、红黑树的颜色调整与树旋转

2.5、红黑树的平衡性分析

2.6、红黑树在实际应用中的优势

3、红黑树的实现

3.1、红黑树节点结构

3.2、旋转操作

3.2.1、左旋

3.2.2、右旋

3.2.3、旋转操作的技术细节

3.2.4、旋转操作在插入和删除中的作用

3.3、插入操作

3.3.1、常规BST插入

3.3.2、调整树以恢复红黑树的性质

3.3.3、插入操作的复杂度

3.4、删除操作

3.4.1、常规BST删除

3.4.2、维护红黑树的性质

3.4.3、辅助函数

3.5、查找操作

3.5.1、查找操作的基本步骤

3.5.2、查找操作的实现

3.5.3、查找操作的技术细节

3.6、删除整颗红黑树操作

3.6.1、删除整个红黑树的步骤

3.6.2、删除整个红黑树的实现：

4、红黑树的拓展

4.1、红黑树的遍历

4.1.1、前序遍历（Pre-order Traversal）

4.1.2、中序遍历（In-order Traversal）

4.1.3、后序遍历（Post-order Traversal）

4.1.4、层序遍历（Level-order Traversal）

4.1.5、遍历的复杂度分析

4.1.6、总结

4.2、查找后继节点

4.3、查找前驱节点

4.4、判断是否是红黑树

5、完整实现代码和测试

5.1、RBTree.hpp

5.2、RBTree.cc

5.3、测试结果

6、红黑树的高级拓展

6.1、红黑树的实际应用

6.1.1、红黑树在标准库中的应用

1、C++ STL 中的 std::map 和 std::set

2、Java 中的 TreeMap 和 TreeSet

6.1.2、操作系统中的红黑树

1、虚拟内存管理

2、进程调度

6.1.3、数据库中的红黑树

1、索引结构

2、日志结构化存储

6.1.4、网络应用中的红黑树

1、路由表

2、HTTP 服务器

6.1.5、实际案例中的性能分析

6.1.6、实现中的关键点

6.2、性能优化

6.2.1、预取和缓存优化

6.2.2、减少旋转和重新着色

6.2.3、并行化和并发优化

6.2.4、改进红黑树的变体

6.2.5、实际应用场景中的优化

6.2.6、实现代码示例

6.3、进阶拓展

6.3.1、多线程环境下的红黑树

1、多线程并发访问问题

《 C++ 修炼全景指南：十八》穿越数据的红与黑：掌握数据平衡的极致艺术