Red-black-tree

红黑树

红黑树概念

红黑树是一种自平衡的二叉查找树，是一种高效的查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是由 Rudolf Bayer 于1972年发明，在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。

红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找效率。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map和set 均是基于红黑树结构实现的。

红黑树的性质

学过二叉查找树的同学都知道，普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。为了避免这种情况，就出现了一些自平衡的查找树，比如 AVL，红黑树等。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。

红黑树子概念

在讲解红黑树性质之前，先简单了解一下几个概念：

• parent：父节点
• sibling：兄弟节点
• uncle：叔父节点（ parent 的兄弟节点）
• grand：祖父节点（ parent 的父节点）

红黑树的平衡条件

• 性质1：每个节点非黑即红
• 性质2：根节点是黑色
• 性质3：叶子结点是黑色
• 性质4：如果一个结点是红色，则它的两个子节点都是黑色
• 性质5：从根节点出发到所有叶子结点路径上，黑色节点数目相同

有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。

但是，仅仅避免这种情况还不够，这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长，那么，在对这些路径上的及诶单进行增删查操作时，效率也会大大降低。这个时候性质4和性质5用途就凸显了，有了这两个性质作为约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。原因如下：

当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。
此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。举例说明一下，请看下图：

上图画出了从根节点 M 出发的到其叶子节点的最长和最短路径。这里偷懒只画出了两条最长路径，实际上最长路径有4条，分别为
M -> Q -> O -> N
M -> Q -> O -> p
M -> Q -> Y -> X
M -> Q -> Y -> Z
长度为4，最短路径为 M -> E，长度为2。最长路径的长度正好为最短路径长度的2倍。

有了上面的介绍，我们就可以继续讨论红黑树的相关操作了。

红黑树操作

红黑树的基本操作和其他树形结构一样，一般都包括查找、插入、删除等操作。前面说到，红黑树是一种自平衡的二叉查找树，既然是二叉查找树的一种，那么查找过程和二叉查找树一样，比较简单。相对于查找操作，红黑树的插入和删除操作就要复杂的多。

查找操作

查找操作较为简单，主要分为以下几个步骤：

1. 走到根节点。
2. 比较当前所在节点的键值和需要查找的键值
3. 如果当前节点的键值和需要查找的键值相同，则所在节点即为目标。
4. 如果需要找的键比当前节点的键小，则前往当前节点的左孩子，然后回到第2步。
5. 如果需要找的键比当前节点的键大，则前往当前节点的右孩子，然后回到第2步。

注意：如果某刻，当前所在的节点为空，则查找失败，需要查找的键不在树里。

旋转操作

树的旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子，具体见下图：

上图包含了左旋和右旋的示意图，这里以右旋为例进行说明，右旋节点 M 的步骤如下：

1. 将节点 M 的左孩子引用指向节点 E 的右孩子
2. 将节点 E 的右孩子引用指向节点 M，完成旋转

上面分析了右旋操作，左旋操作与此类似，这里不再赘述了。

插入操作

红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。

性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。

接下来，将分析插入红色节点后红黑树的情况。这里假设要插入的节点为 N，N 的父节点为 P，祖父节点为 G，叔叔节点为 U。插入红色节点后，会出现5种情况，分别如下：

情况一：

插入的新节点 N 是红黑树的根节点，这种情况下，我们把节点 N 的颜色由红色变为黑色，性质2（根是黑色）被满足。同时 N 被染成黑色后，红黑树所有路径上的黑色节点数量增加一个，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍然被满足。

情况二：

N 的父节点是黑色，这种情况下，性质4（每个红色节点必须有两个黑色的子节点）和性质5没有受到影响，不需要调整。

情况三：

N 的父节点是红色（节点 P 为红色，其父节点必然为黑色），叔叔节点 U 也是红色。由于 P 和 N 均为红色，所有性质4被打破，此时需要进行调整。

这种情况下，先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色。此时经过 G 的路径上的黑色节点数量不变，性质5仍然满足。但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。

情况四：

N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋，调整 N 与 P 的位置。接下来按照情况五进行处理，以恢复性质4。

这里需要特别说明一下，上图中的节点 N 并非是新插入的节点。当 P 为红色时，P 有两个孩子节点，且孩子节点均为黑色，这样从 G 出发到各叶子节点路径上的黑色节点数量才能保持一致。既然 P 已经有两个孩子了，所以 N 不是新插入的节点。

情况四是由以 N 为根节点的子树中插入了新节点，经过调整后，导致 N 被变为红色，进而导致了情况四的出现。考虑下面这种情况（PR 节点就是上图的 N 节点）：

如上图，插入节点 N 并按情况三处理。此时 PR 被染成了红色，与 P 节点形成了连续的红色节点，这个时候就需按情况四再次进行调整。

情况五：

N 的父节点为红色，叔叔节点为黑色。N 是 P 的左孩子，且节点 P 是 G 的左孩子。此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。

插入总结

上面五种情况中，情况一和情况二比较简单，情况三、四、五稍复杂。但如果细心观察，会发现这三种情况的区别在于叔叔节点的颜色，如果叔叔节点为红色，直接变色即可。如果叔叔节点为黑色，则需要选选择，再交换颜色。当把这三种情况的图画在一起就区别就比较容易观察了，如下图：

删除操作

相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。

由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点，只要节点里的值最终被删除就行了，至于树结构如何变化，这个并不重要。

红黑树删除操作的复杂度在于删除节点的颜色，当删除的节点是红色时，直接拿其孩子节点补空位即可。因为删除红色节点，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍能够被满足。

当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5。但如果孩子节点为黑色，处理起来就要复杂的多。分为6种情况，下面会展开说明。

在展开说明之前，我们先做一些假设，方便说明。这里假设最终被删除的节点为X（至多只有一个孩子节点），其孩子节点为N，X的兄弟节点为S，S的左节点为 SL，右节点为 SR。接下来讨论是建立在节点 X 被删除，节点 N 替换X的基础上进行的。

在上面的基础上，接下来就可以展开讨论了。红黑树删除有6种情况，分别是：

情况一：

N 是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。要删除的节点 X 是根节点，且左右孩子节点均为空节点，此时将节点 X 用空节点替换完成删除操作。

情况二：

S 为红色，其他节点为黑色。这种情况下可以对 N 的父节点进行左旋操作，然后互换 P 与 S 颜色。但这并未结束，经过节点 P 和 N 的路径删除前有3个黑色节点（P -> X -> N），现在只剩两个了（P -> N）。比未经过 N 的路径少一个黑色节点，性质5仍不满足，还需要继续调整。不过此时可以按照情况四、五、六进行调整。

情况三：

N 的父节点，兄弟节点 S 和 S 的孩子节点均为黑色。这种情况下可以简单的把 S 染成红色，所有经过 S 的路径比之前少了一个黑色节点，这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点，此时需要从情况一开始对 P 进行平衡处理。

情况四：

N 的父节点是红色，S 和 S 孩子为黑色。这种情况比较简单，我们只需交换 P 和 S 颜色即可。这样所有通过 N 的路径上增加了一个黑色节点，所有通过 S 的节点的路径必然也通过 P 节点，由于 P 与 S 只是互换颜色，并不影响这些路径。

这里需要特别说明一下，上图中的节点 N 并非是新插入的节点。当 P 为红色时，P 有两个孩子节点，且孩子节点均为黑色，这样从 G 出发到各叶子节点路径上的黑色节点数量才能保持一致。既然 P 已经有两个孩子了，所以 N 不是新插入的节点。

情况四是由以 N 为根节点的子树中插入了新节点，经过调整后，导致 N 被变为红色，进而导致了情况四的出现。考虑下面这种情况（PR 节点就是上图的 N 节点）：

情况五：

S 为黑色，S 的左孩子为红色，右孩子为黑色。N 的父节点颜色可红可黑，且 N 是 P 左孩子。这种情况下对 S 进行右旋操作，并互换 S 和 SL 的颜色。此时，所有路径上的黑色数量仍然相等，N 兄弟节点的由 S 变为了 SL，而 SL 的右孩子变为红色。接下来我们到情况六继续分析。

情况六：

S 为黑色，S 的右孩子为红色。N 的父节点颜色可红可黑，且 N 是其父节点左孩子。这种情况下，我们对 P 进行左旋操作，并互换 P 和 S 的颜色，并将 SR 变为黑色。因为 P 变为黑色，所以经过 N 的路径多了一个黑色节点，经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径，则有以下两种情况：

1. 该路径经过 N 新的兄弟节点 SL ，那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色，对于经过 SL 的路径不影响。
2. 该路径经过 N 新的叔叔节点 SR，那它之前必然经过 P、 S 和 SR，而现在它只经过 S 和 SR。在对 P 进行左旋，并与 S 换色后，经过 SR 的路径少了一个黑色节点，性质5被打破。另外，由于 S 的颜色可红可黑，如果 S 是红色的话，会与 SR 形成连续的红色节点，打破性质4（每个红色节点必须有两个黑色的子节点）。此时仅需将 SR 由红色变为黑色即可同时恢复性质4和性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。）。

删除总结

红黑树删除的情况比较多，它们之间的联系和区别如图：

红黑树总结

推荐一个数据结构可视化的网站，里面包含常见数据结构可视化过程，地址为:Data Structure Visualization (usfca.edu)

红黑树和AVL树的比较

• AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异

• 红黑树的插入删除比AVL树更便于控制操作

• 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）

红黑树效率

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。

查找操作时，它和普通的相对平衡的二叉搜索树的效率相同，都是通过相同的方式来查找的，没有用到红黑树特有的特性。但如果插入的时候是有序数据，那么红黑树的查询效率就比二叉搜索树要高了，因为此时二叉搜索树不是平衡树，它的时间复杂度O(N)。

插入和删除操作时，由于红黑树的每次操作平均要旋转一次和变换颜色，所以它比普通的二叉搜索树效率要低一点，不过时间复杂度仍然是O(logN)。总之，红黑树的优点就是对有序数据的查询操作不会慢到O(logN)的时间复杂度。

具体实现

最后结尾放上红黑树模拟实现的具体代码：

Red-black-tree

//RedBlackTree.h
#pragma once

template <typename KeyType, typename DataType>
class RedBlackTree {

public:
	/** 树的生命相关操作。 */
	RedBlackTree();
	~RedBlackTree();

	/**
	 * 清空树中所有元素。
	 */
	void clear();

public:
	/** 树的基本查询操作。 */

	/**
	 * 判断键是否在树里。
	 * 
	 * @param queryKey 待判断的键。
	 * @return 是否在树上找到了对应键。
	 */
	bool hasKey(const KeyType& queryKey);

	/**
	 * 根据键获取数据。
	 * 
	 * @param key 键。
	 * @return 键对应的数据。
	 * @exception runtime_error 如果无法找到键，会抛出异常。
	 */
	DataType& getData(const KeyType& key);

	/**
	 * 设置数据。如果键已经存在，会更新原有数据。
	 * 
	 * @param key 键。
	 * @param data 数据。
	 */
	RedBlackTree<KeyType, DataType>& setData(const KeyType& key, const DataType& data);

	/**
	 * 删除键。
	 * 
	 * @param key 键。
	 * @return 红黑树对象自身。
	 */
	RedBlackTree<KeyType, DataType>& removeKey(const KeyType& key);

private:
	enum class NodeColor {
		RED, BLACK
	};
	enum class ChildSide {
		LEFT, RIGHT
	};
	struct Node {
		KeyType key;
		DataType data;
		NodeColor color = NodeColor::RED;
		Node* father = nullptr;
		Node* leftChild = nullptr;
		Node* rightChild = nullptr;
	};

private:
	/**
	 * 释放该节点及其所有子节点。
	 * 
	 * @param node 递归释放的第一个节点。
	 */
	void cleanup(Node* node);

	/**
	 * 左旋。
	 * 
	 * @param node 支点。
	 * @exception 若支点的右子树不存在，会引发未定义的行为（undefined behaviour).
	 */
	void rotateLeft(Node* node);

	/**
	 * 右旋。
	 * 
	 * @param node 支点。
	 * @exception 若支点的左子树不存在，会引发未定义的行为（undefined behaviour).
	 */
	void rotateRight(Node* node);

	/**
	 * 修复“连续红色节点”问题。当出现当前节点和父节点同为红色时，需要进行修复。
	 * 
	 * @param node “连续红色节点”中的子节点。
	 * @exception 若node是nullptr，会产生未定义的行为。
	 */
	void fixContinuousRedNodeProblem(Node* node);

	/**
	 * 修复“左右孩子不平衡”问题。当某边删除黑色节点后，可能产生此问题。
	 * 
	 * @param node 失衡问题所在的较轻的节点。
	 * @exception 若参数不正确，会产生未定义的行为。
	 */
	void fixUnbalancedChildrenProblem(Node* node);

private:
	/**
	 * 根节点。
	 */
	Node* root = nullptr;

};
//RedBlackTree.cpp
#include <stdexcept>

#include "RedBlackTree.h"

template<typename KeyType, typename DataType>
RedBlackTree<KeyType, DataType>::RedBlackTree()
{
}

template<typename KeyType, typename DataType>
RedBlackTree<KeyType, DataType>::~RedBlackTree()
{
	if (this->root != nullptr) {
		this->cleanup(this->root);
		this->root = nullptr;
	}
}

template<typename KeyType, typename DataType>
void RedBlackTree<KeyType, DataType>::clear()
{
	if (this->root != nullptr) {
		this->cleanup(this->root);
		this->root = nullptr;
	}
}

template<typename KeyType, typename DataType>
bool RedBlackTree<KeyType, DataType>::hasKey(const KeyType& queryKey)
{
	Node* currentNode = this->root;
	
	while (currentNode != nullptr) {
		if (queryKey == currentNode->key) {
			return true; // 找到对应键。
		}
		else if (queryKey < currentNode->key) {
			currentNode = currentNode->leftChild; // 目标键小于当前键，向左查找。
		}
		else { // queryKey > currentNode->key
			currentNode = currentNode->rightChild; // 目标键大于当前键，向右查找。
		}
	}

	return false; // 找不到键。
}

template<typename KeyType, typename DataType>
DataType& RedBlackTree<KeyType, DataType>::getData(const KeyType& key)
{
	Node* currentNode = root;
	while (currentNode != nullptr) {
		if (key == currentNode->key) {
			return currentNode->data; // 找到对应键。
		}
		else if (key < currentNode->key) {
			currentNode = currentNode->leftChild; // 目标键小于当前键，向左查找。
		}
		else { // key > currentNode->key
			currentNode = currentNode->rightChild; // 目标键大于当前键，向右查找。
		}
	}

	throw std::runtime_error("could not find your key in the object."); // 找不到对应键。抛出异常。
}

template<typename KeyType, typename DataType>
RedBlackTree<KeyType, DataType>& RedBlackTree<KeyType, DataType>::setData(
	const KeyType& key, 
	const DataType& data
)
{
	Node* currentNode = root;
	Node* currentFather = nullptr;

	while (currentNode != nullptr) {
		if (key == currentNode->key) { // 找到对应键。
			currentNode->data = data;
			return *this; // 更新完成。结束。
		}
		else {
			currentFather = currentNode;
			currentNode = (key < currentNode->key ? currentNode->leftChild : currentNode->rightChild);
		}
	}

	// 如果是更新现有键值，则在上面的循环里会触发 return.
	// 下面部分负责创建新的节点，完成新数据的存储。

	/*
		此时，currentNode 指向 nullptr, currentFather 指向最后遍历到的节点，也可能是 nullptr.
		插入时，新节点设为红色，根据键值插入到最后一个节点的左或右。
	*/

	// 创建新节点。
	currentNode = new Node;
	currentNode->father = currentFather;
	currentNode->leftChild = nullptr;
	currentNode->rightChild = nullptr;
	currentNode->key = key;
	currentNode->data = data;

	// 如果树是空的，插入节点设为根即可。
	if (currentFather == nullptr) {
		currentNode->color = NodeColor::BLACK;
		this->root = currentNode;
		return *this;
	}

	// 下面处理树是非空时的情况。
	// 先将节点设为红色。
	currentNode->color = NodeColor::RED;
	// 将新节点绑定到父节点。
	if (key < currentFather->key) {
		currentFather->leftChild = currentNode;
	}
	else {
		currentFather->rightChild = currentNode;
	}

	// 对可能出现的“连续红色节点”问题进行修复。
	this->fixContinuousRedNodeProblem(currentNode);
	return *this;
}

template<typename KeyType, typename DataType>
RedBlackTree<KeyType, DataType>& RedBlackTree<KeyType, DataType>::removeKey(
	const KeyType& key
)
{
	Node* currentNode = root;

	while (currentNode != nullptr) {
		if (key == currentNode->key) {
			break; // 键匹配，查询成功。
		}
		else {
			currentNode = (key < currentNode->key ? currentNode->leftChild : currentNode->rightChild);
		}
	}

	if (currentNode == nullptr) {
		throw std::runtime_error("could not find your key in the object."); // 找不到对应键。抛出异常。
	}

	// 否则，使用替代法，锁定替代的节点。
	// 只要有至少一个孩子，就要继续寻找替代节点。
	while (currentNode->leftChild != nullptr || currentNode->rightChild != nullptr) {
		if (currentNode->rightChild != nullptr) {
			// 当前节点有右孩子。
			// 使用后继节点代替原删除节点。
			// 注意：后继节点的左孩子一定是 nullptr.
			Node* replacementNode = currentNode->rightChild;
			while (replacementNode->leftChild != nullptr) {
				replacementNode = replacementNode->leftChild;
			}

			struct {
				Node* leftChild;
				Node* rightChild;
				NodeColor color;
				Node* father;
			} currentNodeInfo = {
					currentNode->leftChild, currentNode->rightChild,
					currentNode->color, currentNode->father
			}, replacementNodeInfo = {
					replacementNode->leftChild, replacementNode->rightChild,
					replacementNode->color, replacementNode->father
			};

			// 交换颜色。
			currentNode->color = replacementNodeInfo.color;
			replacementNode->color = currentNodeInfo.color;

			// 编辑父节点。
			if (currentNodeInfo.father != nullptr) {
				if (currentNodeInfo.father->leftChild == currentNode) {
					currentNodeInfo.father->leftChild = replacementNode;
				}
				else {
					currentNodeInfo.father->rightChild = replacementNode;
				}
			}
			else {
				this->root = replacementNode;
			}

			// 编辑 currentNode 左孩子的信息。
			if (currentNodeInfo.leftChild != nullptr) {
				currentNodeInfo.leftChild->father = replacementNode;
			}

			// 编辑 replacementNode 右孩子的信息（如果有）。
			if (replacementNodeInfo.rightChild != nullptr) {
				replacementNodeInfo.rightChild->father = currentNode;
			}
			
			currentNode->leftChild = nullptr; // 替换节点的左孩子一定是 nullptr.
			currentNode->rightChild = replacementNodeInfo.rightChild;
			if (replacementNodeInfo.father == currentNode) {
				currentNode->father = replacementNode;
			}
			else {
				currentNode->father = replacementNodeInfo.father;
			}

			replacementNode->leftChild = currentNodeInfo.leftChild;
			replacementNode->father = currentNodeInfo.father;
			if (currentNodeInfo.rightChild == replacementNode) {
				replacementNode->rightChild = currentNode;
			}
			else {
				replacementNode->rightChild = currentNodeInfo.rightChild;
			}

			if (currentNodeInfo.rightChild != replacementNode) {
				currentNodeInfo.rightChild->father = replacementNode;
				replacementNodeInfo.father->leftChild = currentNode;
			}
		} // if (当前节点有右孩子)
		else { // 当前节点有左孩子，但没有右孩子。
			// 使用前驱节点代替原删除节点。
			// 注意：前驱节点的右孩子一定是 nullptr.
			Node* replacementNode = currentNode->leftChild;
			while (replacementNode->rightChild != nullptr) {
				replacementNode = replacementNode->rightChild;
			}

			struct {
				Node* leftChild;
				Node* rightChild;
				NodeColor color;
				Node* father;
			} currentNodeInfo = {
					currentNode->leftChild, currentNode->rightChild,
					currentNode->color, currentNode->father
			}, replacementNodeInfo = {
					replacementNode->leftChild, replacementNode->rightChild,
					replacementNode->color, replacementNode->father
			};

			// 交换颜色。
			currentNode->color = replacementNodeInfo.color;
			replacementNode->color = currentNodeInfo.color;

			// 编辑父节点。
			if (currentNodeInfo.father != nullptr) {
				if (currentNodeInfo.father->leftChild == currentNode) {
					currentNodeInfo.father->leftChild = replacementNode;
				}
				else {
					currentNodeInfo.father->rightChild = replacementNode;
				}
			}
			else {
				this->root = replacementNode;
			}

			// 编辑 currentNode 右孩子的信息。
			if (currentNodeInfo.rightChild != nullptr) {
				currentNodeInfo.rightChild->father = replacementNode;
			}

			// 编辑 replacementNode 左孩子的信息（如果有）。
			if (replacementNodeInfo.leftChild != nullptr) {
				replacementNodeInfo.leftChild->father = currentNode;
			}

			currentNode->rightChild = nullptr; // 替换节点的右孩子一定是 nullptr.
			currentNode->leftChild = replacementNodeInfo.leftChild;
			if (replacementNodeInfo.father == currentNode) {
				currentNode->father = replacementNode;
			}
			else {
				currentNode->father = replacementNodeInfo.father;
			}

			replacementNode->rightChild = currentNodeInfo.rightChild;
			replacementNode->father = currentNodeInfo.father;
			if (currentNodeInfo.leftChild == replacementNode) {
				replacementNode->leftChild = currentNode;
			}
			else {
				replacementNode->leftChild = currentNodeInfo.leftChild;
			}

			if (currentNodeInfo.leftChild != replacementNode) {
				currentNodeInfo.leftChild->father = replacementNode;
				replacementNodeInfo.father->rightChild = currentNode;
			}
		} // 当前节点有左孩子，但没有右孩子。
	} // while (currentNode->leftChild != nullptr || currentNode->rightChild != nullptr)

	// 至此，删除目标没有子树。

	if (currentNode == this->root) { // 删除的是根。
		this->root = nullptr;
		delete currentNode;
	} // 删除的是根。
	else if (currentNode->color == NodeColor::RED) {
		if (currentNode == currentNode->father->leftChild) {
			currentNode->father->leftChild = nullptr;
		}
		else {
			currentNode->father->rightChild = nullptr;
		}
		delete currentNode;
	} // 要删除的是红色的叶节点。
	else { // 要删除的是黑色的叶节点。
		// 目标节点的父节点一定存在。因为目标节点是黑色的，所以兄弟一定存在。
		Node* sibling = (currentNode->father->leftChild != currentNode ?
			currentNode->father->leftChild : currentNode->father->rightChild);

		Node* currentFather = currentNode->father;

		ChildSide siblingSideToFather = 
			(sibling == currentFather->leftChild ? ChildSide::LEFT : ChildSide::RIGHT);

		// 前面已经找完了与删除目标相关的节点。现在可以删掉目标节点了。
		// 取消父节点对它的绑定。
		if (currentFather->leftChild == currentNode) {
			currentFather->leftChild = nullptr;
		}
		else {
			currentFather->rightChild = nullptr;
		}
		// 释放节点。
		delete currentNode;

		// 接下来开始分情况讨论。

		if (currentFather->color == NodeColor::RED) {
			// 父节点是红色时，兄弟节点一定是黑色的。

			if (sibling->leftChild != nullptr && sibling->rightChild != nullptr)
			{
				/*
					X: 被删除; R: Red; B: Black
					  R
					 / \
					X   B
					   / \
					  R   R   或其对称形态。
				*/
				// 兄弟的左右孩子都是红色。
				// 注意：如果这个黑色的叔叔有孩子，那么孩子一定是红色的。
				// 操作：对兄弟做旋转，再对父节点做旋转。父节点设为黑色，兄弟设为红色。
				sibling->color = NodeColor::RED;
				currentFather->color = NodeColor::BLACK;

				if (siblingSideToFather == ChildSide::RIGHT) {
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(currentFather);
				}
				else {
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(currentFather);
				}
			}
			else if (siblingSideToFather == ChildSide::RIGHT && sibling->leftChild != nullptr)
			{
				/*
					X: 被删除; R: Red; B: Black
					  R
					 / \
					X   B
					   /
					  R
				*/

				currentFather->color = NodeColor::BLACK;
				this->rotateRight(sibling);
				this->rotateLeft(currentFather);
			}
			else if (siblingSideToFather == ChildSide::LEFT && sibling->rightChild != nullptr)
			{
				/*
					X: 被删除; R: Red; B: Black
					  R
					 / \
					B   X
					 \
					  R
				*/

				currentFather->color = NodeColor::BLACK;
				this->rotateLeft(sibling);
				this->rotateRight(currentFather);
			}
			else if (siblingSideToFather == ChildSide::RIGHT && sibling->rightChild != nullptr) {
				/*
					X: 被删除; R: Red; B: Black
					  R
					 / \
					X   B
					     \
					      R
				*/
				currentFather->color = NodeColor::BLACK;
				sibling->color = NodeColor::RED;
				sibling->rightChild->color = NodeColor::BLACK;
				this->rotateLeft(currentFather);
			}
			else if (siblingSideToFather == ChildSide::LEFT && sibling->leftChild != nullptr)
			{
				/*
					X: 被删除; R: Red; B: Black
					    R
					   / \
					  B   X
					 /
					R
				*/
				currentFather->color = NodeColor::BLACK;
				sibling->color = NodeColor::RED;
				sibling->leftChild->color = NodeColor::BLACK;
				this->rotateRight(currentFather);
			}
			else { // sibling 没有孩子。
				sibling->color = NodeColor::RED;
				currentFather->color = NodeColor::BLACK;
			}

		} // currentFather->color == NodeColor::RED
		else { // currentFather->color == NodeColor::BLACK
			if (sibling->color == NodeColor::BLACK
				&& sibling->leftChild != nullptr && sibling->rightChild != nullptr)
			{
				// 兄弟是黑色的，且兄弟有两个孩子。那么这两个孩子一定是红色的。
				if (siblingSideToFather == ChildSide::RIGHT) {
					/*
						X: 被删除; R: Red; B: Black
							B
						   / \
						  X   B
						     / \
							R   R
					*/
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(sibling);
					this->rotateLeft(currentFather);
				}
				else {
					/*
						X: 被删除; R: Red; B: Black
							B
						   / \
						  B   X
						 / \
						R   R
					*/
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(sibling);
					this->rotateRight(currentFather);
				}
			} // 兄弟是黑色，且有两个孩子。
			else if (sibling->color == NodeColor::BLACK &&
				(sibling->leftChild != nullptr || sibling->rightChild != nullptr))
			{
				// 兄弟是黑色，且有一个孩子（一定是红色）。
				if (siblingSideToFather == ChildSide::RIGHT && sibling->rightChild != nullptr) {
					/*
						X: 被删除; R: Red; B: Black
							B
						   / \
						  X   B
						       \
						        R
					*/
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(currentFather);
				}
				else if (siblingSideToFather == ChildSide::RIGHT && sibling->leftChild != nullptr)
				{
					/*
						X: 被删除; R: Red; B: Black
							B
						   / \
						  X   B
							 /
							R
					*/
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(sibling);
					this->rotateLeft(currentFather);
				}
				else if (siblingSideToFather == ChildSide::LEFT && sibling->leftChild != nullptr)
				{
					/*
						X: 被删除; R: Red; B: Black
							B
						   / \
						  B   X
						 /
						R
					*/
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(currentFather);
				}
				else {
					/*
						X: 被删除; R: Red; B: Black
							B
						   / \
						  B   X
						   \
							R
					*/
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(sibling);
					this->rotateRight(currentFather);
				}
			} // 兄弟是黑色，且有一个孩子。
			else if (sibling->color == NodeColor::BLACK) {
				// 兄弟是黑色，但是没有孩子。
				/*
					   B          B
					  / \   ->   / \
					 X   B      X   R
				*/
				if (currentFather->leftChild == nullptr) {
					currentFather->rightChild->color = NodeColor::RED;
					this->fixUnbalancedChildrenProblem(currentFather);
				}
				else {
					currentFather->leftChild->color = NodeColor::RED;
					this->fixUnbalancedChildrenProblem(currentFather);
				}
			} // 兄弟是黑色的，且没有孩子。
			else {
				// 兄弟是红色的。那么兄弟一定有两个黑色的孩子。
				sibling->color = NodeColor::BLACK;
				currentFather->color = NodeColor::RED;
				if (siblingSideToFather == ChildSide::RIGHT) {
					/*
						   B
						  / \
						 X   R
						    / \
						   B   B
					*/
					this->rotateLeft(currentFather);
					this->rotateLeft(currentFather);
					if (currentFather->rightChild != nullptr) {
						this->fixContinuousRedNodeProblem(currentFather->rightChild);
					}
				}
				else {
					/*
						   B
						  / \
						 R   X
						/ \
					   B   B
					*/
					this->rotateRight(currentFather);
					this->rotateRight(currentFather);
					if (currentFather->leftChild != nullptr) {
						this->fixContinuousRedNodeProblem(currentFather->leftChild);
					}
				}
			}
		}
	}

	return *this; // 删除成功。
}

template<typename KeyType, typename DataType>
void RedBlackTree<KeyType, DataType>::cleanup(Node* node)
{
	if (node->leftChild != nullptr) {
		cleanup(node->leftChild);
	}
	if (node->rightChild != nullptr) {
		cleanup(node->rightChild);
	}
	delete node;
}

template<typename KeyType, typename DataType>
void RedBlackTree<KeyType, DataType>::rotateLeft(Node* node)
{
	Node* father = node->father;
	Node* targetRoot = node->rightChild;

	// 重新绑定子树的根。
	if (father == nullptr) {
		this->root = targetRoot;
	}
	else {
		if (node == father->leftChild) {
			father->leftChild = targetRoot;
		}
		else {
			father->rightChild = targetRoot;
		}
	}
	targetRoot->father = father;

	node->rightChild = targetRoot->leftChild; // 孩子有可能是 nullptr
	if (node->rightChild != nullptr) { // 只有当孩子不是空的时候，才可尝试重新绑定父节点。
		node->rightChild->father = node;
	}
	targetRoot->leftChild = node;
	node->father = targetRoot;
}

template<typename KeyType, typename DataType>
void RedBlackTree<KeyType, DataType>::rotateRight(Node* node)
{
	Node* father = node->father;
	Node* targetRoot = node->leftChild;

	// 重新绑定子树的根。
	if (father == nullptr) {
		this->root = targetRoot;
	}
	else {
		if (node == father->leftChild) {
			father->leftChild = targetRoot;
		}
		else {
			father->rightChild = targetRoot;
		}
	}
	targetRoot->father = father;

	node->leftChild = targetRoot->rightChild; // 孩子有可能是 nullptr
	if (node->leftChild != nullptr) { // 只有当孩子不是空的时候，才可尝试重新绑定父节点。
		node->leftChild->father = node;
	}
	targetRoot->rightChild = node;
	node->father = targetRoot;
}

template<typename KeyType, typename DataType>
void RedBlackTree<KeyType, DataType>::fixContinuousRedNodeProblem(Node* node)
{
	Node* currentNode = node;
	
	// 只有当当前节点是红色时，才可能在父节点为红色时违背红黑树规则，于是要进行修复操作。
	while (currentNode->color == NodeColor::RED) {
		Node* currentFather = currentNode->father;
		if (currentFather == nullptr) {
			// currentNode 是根节点。
			currentNode->color = NodeColor::BLACK;
			break;
		}
		else if (currentFather->color == NodeColor::BLACK) {
			// 父节点是黑色，不存在“连续红色节点”问题。
			break;
		}

		// 如果执行到了这里，说明父节点和目标节点都是红色的。

		// 如果父节点是红色的，那么它（父节点）一定不是根，所以祖父存在。
		Node* currentGrandpa = currentFather->father;

		// 寻找叔节点（可能为空）。
		Node* uncle =
			(currentGrandpa->leftChild != currentFather ?
				currentGrandpa->leftChild : currentGrandpa->rightChild);

		if (uncle != nullptr && uncle->color == NodeColor::RED) {
			// 叔叔存在并且是红色，进行反色操作。

			uncle->color = NodeColor::BLACK;
			currentFather->color = NodeColor::BLACK;
			currentGrandpa->color = NodeColor::RED;

			// 将当前节点设为爷爷节点。
			currentNode = currentGrandpa;
		}
		else {
			// 叔叔为黑色或不存在，进行旋转操作。
			// 旋转的每一种情况都可以保证树满足红黑树的要求。所以，进入本分支后将跳出修复函数。

			// 如果父节点是祖父的左孩子...
			if (currentFather == currentGrandpa->leftChild) {
				if (currentNode == currentFather->leftChild) {
					this->rotateRight(currentGrandpa);
					// 重新着色。
					currentFather->color = NodeColor::BLACK;
					currentGrandpa->color = NodeColor::RED;
				}
				else {
					this->rotateLeft(currentFather);
					this->rotateRight(currentGrandpa);
					// 重新着色。
					currentGrandpa->color = NodeColor::RED;
					currentNode->color = NodeColor::BLACK;
				}
			} // if (currentFather == currentGrandpa->leftChild)
			else {
				// 否则，则父节点是祖父的右孩子...

				if (currentNode == currentFather->rightChild) {
					this->rotateLeft(currentGrandpa);
					// 重新着色。
					currentFather->color = NodeColor::BLACK;
					currentGrandpa->color = NodeColor::RED;
				}
				else {
					this->rotateRight(currentFather);
					this->rotateLeft(currentGrandpa);
					// 重新着色。
					currentGrandpa->color = NodeColor::RED;
					currentNode->color = NodeColor::BLACK;
				}
			} // if (currentFather != currentGrandpa->leftChild)

			return;
		}
	}
}

template<typename KeyType, typename DataType>
void RedBlackTree<KeyType, DataType>::fixUnbalancedChildrenProblem(Node* node)
{
	Node* currentNode = node;

	while (currentNode != this->root) {
		Node* currentFather = currentNode->father;
		Node* sibling = (currentFather->leftChild != currentNode ?
			currentFather->leftChild : currentFather->rightChild);
		ChildSide siblingSideToFather = 
			(sibling == currentFather->leftChild ? ChildSide::LEFT : ChildSide::RIGHT);

		if (currentFather->color == NodeColor::RED) {
			// 父节点为红色。
			// 那么，兄弟一定是黑色的。
			// 此时，兄弟节点的左右孩子一定都存在。
			if (siblingSideToFather == ChildSide::RIGHT
				&& sibling->leftChild->color == NodeColor::BLACK)
			{
				/*
					   R
					  / \
					 X   B
					    / \
					   B   ?
				*/
				this->rotateLeft(currentFather);
				break; // 修复完成。
			}
			else if (siblingSideToFather == ChildSide::LEFT
				&& sibling->rightChild->color == NodeColor::BLACK)
			{
				/*
					    R
					   / \
					  B   X
					 / \
					?   B
				*/
				this->rotateRight(currentFather);
				break;
			}
			else if (siblingSideToFather == ChildSide::RIGHT
				&& sibling->rightChild->color == NodeColor::BLACK)
			{
				/*
					   R
					  / \
					 X   B
						/ \
					   R   B
				*/
				currentFather->color = NodeColor::BLACK;
				sibling->color = NodeColor::RED;
				this->fixContinuousRedNodeProblem(sibling->leftChild);
				break;
			}
			else if (siblingSideToFather == ChildSide::LEFT
				&& sibling->leftChild->color == NodeColor::BLACK)
			{
				/*
					    R
					   / \
					  B   X
					 / \
					B   R
				*/
				currentFather->color = NodeColor::BLACK;
				sibling->color = NodeColor::RED;
				this->fixContinuousRedNodeProblem(sibling->rightChild);
				break;
			}
			else { // 兄弟的左右孩子都是红色的。
				currentFather->color = NodeColor::BLACK;
				sibling->color = NodeColor::RED;
				if (siblingSideToFather == ChildSide::RIGHT) {
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(currentFather);
				}
				else {
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(currentFather);
				}
				break;
			}
		} // 父节点为红色。
		else { // 父节点为黑色。
			if (sibling->color == NodeColor::RED) { // 兄弟是红色的。
				/*
						B
					   / \
					  X   R
						 / \
						B   B

					及其对称形态。
				*/
				currentFather->color = NodeColor::RED;
				sibling->color = NodeColor::BLACK;
				if (siblingSideToFather == ChildSide::RIGHT) {
					
					this->rotateLeft(currentFather);
				}
				else {
					this->rotateRight(currentFather);
				}
			} // 兄弟是红色的。
			else { // 兄弟是黑色的。
				if (sibling->leftChild->color == NodeColor::BLACK 
					&& sibling->rightChild->color == NodeColor::BLACK)
				{
					/*
						  B
						 / \
						X   B
						   / \
						  B   B

						及其对称形态。
					*/
					sibling->color = NodeColor::RED;
					currentNode = currentFather;
				}
				else if (siblingSideToFather == ChildSide::RIGHT 
					&& sibling->rightChild->color == NodeColor::RED) 
				{
					/*
						  B
						 / \
						X   B
						   / \
						  ?   R

					*/
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(currentFather);
					break;
				}
				else if (siblingSideToFather == ChildSide::LEFT
					&& sibling->leftChild->color == NodeColor::RED)
				{
					/*
						    B
						   / \
						  B   X
						 / \
						R   ?

					*/
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(currentFather);
					break;
				}
				else if (siblingSideToFather == ChildSide::RIGHT) 
				{
					/*
						  B
						 / \
						X   B
						   / \
						  R   B

					*/
					sibling->leftChild->color = NodeColor::BLACK;
					this->rotateRight(sibling);
					this->rotateLeft(currentFather);
					break;
				}
				else 
				{
					/*
						    B
						   / \
						  B   X
						 / \
						B   R

					*/
					sibling->rightChild->color = NodeColor::BLACK;
					this->rotateLeft(sibling);
					this->rotateRight(currentFather);
					break;
				}
			} // 兄弟是黑色的。
		} // 父节点为黑色。
	}
}

参考文献

[1]. 一文带你彻底读懂红黑树（附详细图解） - 知乎 (zhihu.com)

[2].《算法》——清华大学出版社

[3].【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树_小七mod的博客-CSDN博客

[4].C++ 实现红黑树结构_枫铃树的博客-CSDN博客