C++ 红黑树
目录
0.前言
1.红黑树概念
2.红黑树性质
3.红黑树节点定义
节点属性详解
4.红黑树结构
4.1带头节点的红黑树结构
4.2不带头节点的红黑树结构
5.红黑树插入节点操作
5.1 按照二叉搜索树的规则插入新节点
5.2 检测新节点插入后,红黑树的性质是否遭到破坏
5.2.1 情况一: cur为红,p为红,g为黑,u存在且为红
5.2.2 情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑(需要单旋)
5.2.3 情况三: cur为红,p为红,g为黑,u不存在/u存在且为黑(需要双旋)
6.红黑树删除节点操作
6.1 按照二叉搜索树的规则删除节点
6.2. 检测删除节点后,红黑树的性质是否遭到破坏,并进行修复
7.红黑树的性能
7.1红黑树的复杂度分析
7.2与 AVL 树的比较
8.红黑树的迭代器设计
8.1迭代器结构
8.2前向迭代(operator++)
8.3后向迭代(operator--)
9.红黑树的模拟实现代码
10.基于红黑树的map模拟实现
11.结语
(图像由AI生成)
0.前言
在之前的文章中,我们介绍了 C++ 标准库中的 map
和 set
容器的使用,以及 AVL 树的实现。尽管 AVL 树在平衡性方面表现优异,但在插入和删除操作频繁的应用中,红黑树(Red-Black Tree)由于其较少的旋转操作次数,往往能提供更优的性能。本篇博客将详细介绍红黑树的概念、性质、节点定义、结构、插入与删除操作、性能、迭代器设计,并展示基于红黑树的模拟实现代码及其在 map
容器中的应用。
1.红黑树概念
红黑树(Red-Black Tree)是一种自平衡二叉搜索树,在每个节点上增加一个存储位表示节点的颜色,可以是红色(Red)或黑色(Black)。红黑树通过对从根到叶子的路径上各个节点的着色方式进行限制,确保没有任何一条路径比其他路径长出两倍,从而实现近似的平衡。
红黑树最早由 Rudolf Bayer 于 1972 年提出,最初被称为对称二叉 B 树(Symmetric Binary B-trees)。后来,Leonidas J. Guibas 和 Robert Sedgewick 对其进行了改进和推广,正式提出了红黑树的概念。红黑树的设计思想是通过简单的规则和操作,确保树在插入和删除操作后保持平衡,从而提供高效的查找性能。
红黑树广泛应用于各种实际场景中,其性质使得它在实现高效数据结构时具有很大优势。例如:
-
STL 容器:C++ 标准模板库(STL)中的
map
和set
容器通常基于红黑树实现,以保证快速的插入、删除和查找操作。 -
数据库索引:许多数据库系统使用红黑树来实现索引结构,以提高数据检索的效率。
-
内核调度:一些操作系统内核使用红黑树来管理进程调度,以确保系统能够高效地处理任务。
2.红黑树性质
(图片来源:知乎@王大帅 特此鸣谢)
红黑树具有以下五个重要性质,这些性质保证了红黑树的平衡性和高效性:
-
每个节点不是红色就是黑色:
- 红黑树的每个节点都有一个颜色属性,这个颜色要么是红色,要么是黑色。通过颜色属性的限制,红黑树能够在结构上保持平衡。
-
根节点是黑色的:
- 红黑树的根节点始终是黑色的。这一性质确保了树的平衡性从根节点开始,并且为树的其他平衡规则提供了基础。
-
如果一个节点是红色的,则它的两个孩子节点是黑色的:
- 这一性质避免了两个连续的红色节点出现在从根到叶子的路径上。通过限制红色节点的排列方式,红黑树能够防止路径长度的不平衡增长。
-
对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点:
- 这一性质也称为黑色平衡性(black-height)。它保证了从任一节点到其叶节点的路径长度相似,从而使红黑树接近平衡。这意味着在插入或删除节点时,红黑树可以通过重新着色和旋转操作来恢复平衡,而不需要像 AVL 树那样频繁调整。
-
每个叶子节点都是黑色的(此处的叶子节点指的是空节点):
- 红黑树中的叶子节点实际上是树中的空节点(NIL 节点),这些节点也被视为黑色。即使树中没有显式存储这些 NIL 节点,理解它们的存在对于分析红黑树的平衡性是至关重要的。
3.红黑树节点定义
在红黑树中,每个节点不仅存储数据,还包含指向其子节点和父节点的指针,以及节点的颜色属性。下面是红黑树节点的定义代码:
enum Color { RED, BLACK };template<class T>
struct RBTreeNode
{T _data; // 存储的数据RBTreeNode<T>* _left; // 指向左子节点的指针RBTreeNode<T>* _right; // 指向右子节点的指针RBTreeNode<T>* _parent; // 指向父节点的指针Color _color; // 节点的颜色// 构造函数,初始化节点的数据和指针,默认颜色为红色RBTreeNode(const T& data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED){}
};
节点属性详解
-
_data:
- 存储节点的数据。这个数据可以是任何类型,由模板参数
T
决定。
- 存储节点的数据。这个数据可以是任何类型,由模板参数
-
_left:
- 指向左子节点的指针。如果左子节点不存在,则该指针为
nullptr
。
- 指向左子节点的指针。如果左子节点不存在,则该指针为
-
_right:
- 指向右子节点的指针。如果右子节点不存在,则该指针为
nullptr
。
- 指向右子节点的指针。如果右子节点不存在,则该指针为
-
_parent:
- 指向父节点的指针。这在红黑树的插入和删除操作中非常重要,因为这些操作需要通过父节点来进行旋转和重新着色。
-
_color:
- 节点的颜色属性,可以是红色(RED)或黑色(BLACK)。颜色属性在保持红黑树的平衡性中起到关键作用。
- 在构造函数中,节点的颜色被默认设置为红色(RED)。这是因为插入新节点时,默认情况下设置为红色更易于保持树的平衡,并通过后续的旋转和重新着色操作来调整树的结构。
4.红黑树结构
红黑树可以带有头节点(header)或者不带头节点。在带头节点的红黑树结构中,头节点提供了便利的指针,可以快速访问树的最小节点、最大节点以及根节点。这种设计在实现中有助于简化边界情况的处理。
4.1带头节点的红黑树结构
带头节点的红黑树使用一个特殊的头节点(header),它的颜色通常设为红色,并且其指针指向树中的特殊节点。具体来说,头节点的指针结构如下:
- header->parent 指向树的根节点。
- header->left 指向树中最小的节点(leftmost)。
- header->right 指向树中最大的节点(rightmost)。
4.2不带头节点的红黑树结构
不带头节点的红黑树则不使用额外的头节点,直接通过根节点进行操作。在这种结构中,树的边界处理和遍历操作相对复杂一些,因为没有头节点来存储额外的指针信息。
为定义方便起见,后文中红黑树结构采用无头结点方式。
5.红黑树插入节点操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入操作可以分为两个步骤:
- 按照二叉搜索树的规则插入新节点
- 检测新节点插入后,红黑树的性质是否遭到破坏,并进行修复
5.1 按照二叉搜索树的规则插入新节点
首先,我们按照二叉搜索树的规则找到新节点的插入位置,并将其插入到树中。插入的新节点默认颜色为红色。以下是具体的实现代码:
pair<Iterator, bool> Insert(const T& data) {if (_root == nullptr) {_root = new Node(data);_root->_color = BLACK; // 根节点必须是黑色return make_pair(Iterator(_root, _root), true);}KeyOfT kot; // 获取键值Node* parent = nullptr;Node* cur = _root;while (cur) {if (kot(cur->_data) == kot(data)) {return make_pair(Iterator(cur, _root), false); // 如果数据已经存在,直接返回}parent = cur;if (kot(cur->_data) > kot(data)) {cur = cur->_left;} else {cur = cur->_right;}}cur = new Node(data);Node* newNode = cur;if (KeyOfT()(data) < KeyOfT()(parent->_data)) {parent->_left = cur;} else {parent->_right = cur;}cur->_parent = parent;// 检测并修复红黑树性质,伪代码FixInsert(cur);return make_pair(Iterator(newNode, _root), true);
}
5.2 检测新节点插入后,红黑树的性质是否遭到破坏
在插入节点后,可能会破坏红黑树的性质,需要进行修复。红黑树的性质有五条:
- 每个节点不是红色就是黑色。
- 根节点是黑色的。
- 如果一个节点是红色的,则它的两个孩子节点是黑色的。
- 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
- 每个叶子节点都是黑色的(此处的叶子节点指的是空节点)。
为了修复红黑树的性质,我们需要考虑以下几种情况:
-
情况 1:新节点的父节点是黑色的。这种情况下,插入操作不会破坏红黑树的任何性质,因此不需要进行任何操作。
-
情况 2:新节点的父节点是红色的。由于红黑树的性质 3 被破坏(两个连续的红色节点),我们需要进行修复操作。具体分为以下几种子情况:
-
情况 2.1:新节点的叔叔节点(父节点的兄弟节点)是红色的。这种情况下,父节点和叔叔节点都变为黑色,祖父节点变为红色,然后将当前节点指向祖父节点,继续检测祖父节点。
-
情况 2.2:新节点的叔叔节点是黑色的,且新节点是父节点的右孩子。此时,我们需要进行左旋操作,将新节点变成父节点,然后进行情况 2.3 的处理。
-
情况 2.3:新节点的叔叔节点是黑色的,且新节点是父节点的左孩子。这种情况下,我们进行右旋操作,将父节点变成新节点,调整颜色后结束修复。
-
我们不妨约定cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点。
5.2.1 情况一: cur为红,p为红,g为黑,u存在且为红
在这种情况下,当前节点cur
的父节点p
和叔叔节点u
都是红色,祖父节点g
是黑色。这种情况破坏了红黑树性质3(红节点的子节点必须是黑色)。解决方式如下:
- 将
p
和u
改为黑色。 - 将
g
改为红色。 - 将当前节点
cur
移动到g
,继续向上调整。
void FixInsert(Node* node) {Node* parent = nullptr;Node* grandFather = nullptr;// 当前节点不在根节点且其父节点为红色时,需要调整while (node != _root && node->_parent->_color == RED) {parent = node->_parent;grandFather = parent->_parent;if (parent == grandFather->_left) {Node* uncle = grandFather->_right;if (uncle && uncle->_color == RED) {// 情况 1: 叔叔是红色parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;node = grandFather; // 将当前节点上移到祖父节点继续调整} else {// 处理情况 2 和 3}} else {Node* uncle = grandFather->_left;if (uncle && uncle->_color == RED) {// 情况 1: 叔叔是红色parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;node = grandFather; // 将当前节点上移到祖父节点继续调整} else {// 处理情况 2 和 3}}}_root->_color = BLACK; // 根节点始终是黑色
}
5.2.2 情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑(需要单旋)
在这种情况下,当前节点cur
的父节点p
是红色,叔叔节点u
是黑色或不存在。根据cur
和p
的相对位置,需要进行单旋操作。
- 如果
cur
是p
的右子节点,p
是g
的左子节点,需要进行左旋。 - 如果
cur
是p
的左子节点,p
是g
的右子节点,需要进行右旋。
void FixInsert(Node* node) {Node* parent = nullptr;Node* grandFather = nullptr;// 当前节点不在根节点且其父节点为红色时,需要调整while (node != _root && node->_parent->_color == RED) {parent = node->_parent;grandFather = parent->_parent;if (parent == grandFather->_left) {Node* uncle = grandFather->_right;if (uncle && uncle->_color == RED) {parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;node = grandFather; // 将当前节点上移到祖父节点继续调整} else {if (node == parent->_right) {// 情况 2: 叔叔是黑色且当前节点是右子节点,需要左旋RotateL(parent);node = parent;parent = node->_parent;}// 单旋后调整颜色RotateR(grandFather);swap(parent->_color, grandFather->_color);node = parent;}} else {Node* uncle = grandFather->_left;if (uncle && uncle->_color == RED) {parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;node = grandFather; // 将当前节点上移到祖父节点继续调整} else {if (node == parent->_left) {// 情况 2: 叔叔是黑色且当前节点是左子节点,需要右旋RotateR(parent);node = parent;parent = node->_parent;}// 单旋后调整颜色RotateL(grandFather);swap(parent->_color, grandFather->_color);node = parent;}}}_root->_color = BLACK; // 根节点始终是黑色
}
5.2.3 情况三: cur为红,p为红,g为黑,u不存在/u存在且为黑(需要双旋)
在这种情况下,当前节点cur
的父节点p
是红色,叔叔节点u
是黑色或不存在。根据cur
和p
的相对位置,需要进行双旋操作。
- 如果
cur
是p
的左子节点,p
是g
的左子节点,且cur
是p
的右子节点(需要右旋后左旋)。 - 如果
cur
是p
的右子节点,p
是g
的右子节点,且cur
是p
的左子节点(需要左旋后右旋)。
void FixInsert(Node* node) {Node* parent = nullptr;Node* grandFather = nullptr;// 当前节点不在根节点且其父节点为红色时,需要调整while (node != _root && node->_parent->_color == RED) {parent = node->_parent;grandFather = parent->_parent;if (parent == grandFather->_left) {Node* uncle = grandFather->_right;if (uncle && uncle->_color == RED) {parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;node = grandFather; // 将当前节点上移到祖父节点继续调整} else {if (node == parent->_right) {// 情况 3: 叔叔是黑色且当前节点是右子节点,需要左旋后右旋RotateL(parent);node = parent;parent = node->_parent;}// 双旋后调整颜色RotateR(grandFather);swap(parent->_color, grandFather->_color);node = parent;}} else {Node* uncle = grandFather->_left;if (uncle && uncle->_color == RED) {parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;node = grandFather; // 将当前节点上移到祖父节点继续调整} else {if (node == parent->_left) {// 情况 3: 叔叔是黑色且当前节点是左子节点,需要右旋后左旋RotateR(parent);node = parent;parent = node->_parent;}// 双旋后调整颜色RotateL(grandFather);swap(parent->_color, grandFather->_color);node = parent;}}}_root->_color = BLACK; // 根节点始终是黑色
}
6.红黑树删除节点操作
在红黑树中,删除节点操作分为两个部分:首先按照二叉搜索树的规则删除节点,然后通过调整(旋转和重新着色)来修复可能破坏的红黑树性质。
6.1 按照二叉搜索树的规则删除节点
删除节点时,首先找到要删除的节点,并进行删除操作。如果节点有两个子节点,需要找到后继节点替换被删除节点,并删除后继节点。
Node* Delete(Node* root, const T& data) {// 查找并删除节点,返回新根节点Node* z = FindNode(root, data); // 找到要删除的节点if (!z) return root; // 节点不存在,直接返回Node* y = z;Node* x;Color y_original_color = y->_color;if (z->_left == nullptr) {x = z->_right;Transplant(root, z, z->_right);} else if (z->_right == nullptr) {x = z->_left;Transplant(root, z, z->_left);} else {y = Minimum(z->_right); // 找到后继节点y_original_color = y->_color;x = y->_right;if (y->_parent == z) {if (x) x->_parent = y;} else {Transplant(root, y, y->_right);y->_right = z->_right;y->_right->_parent = y;}Transplant(root, z, y);y->_left = z->_left;y->_left->_parent = y;y->_color = z->_color;}delete z;if (y_original_color == BLACK) {FixDelete(root, x);}return root;
}
6.2. 检测删除节点后,红黑树的性质是否遭到破坏,并进行修复
删除节点后,可能会破坏红黑树的性质,需要进行修复。常见的调整情况如下:
情况一:当前节点x是红色或其父节点是红色
- 不需要做任何调整,因为删除一个红色节点不会破坏红黑树的性质。
情况二:当前节点x是黑色,其兄弟节点是红色
- 将父节点变为红色,兄弟节点变为黑色,然后进行旋转,转为情况三或四进行处理。
情况三:当前节点x是黑色,其兄弟节点是黑色,兄弟节点的子节点都是黑色
- 将兄弟节点变为红色,继续向上调整,直到根节点或调整完毕。
情况四:当前节点x是黑色,其兄弟节点是黑色,兄弟节点的一个子节点是红色
- 根据兄弟节点子节点的位置,进行旋转和重新着色。
7.红黑树的性能
7.1红黑树的复杂度分析
红黑树是一种自平衡二叉搜索树,能够确保在最坏情况下的操作复杂度为O(logn),其中 n 是树中节点的数量。这种性能保证源于红黑树的平衡性质,使得树的高度始终保持在 O(logn) 范围内。以下是对红黑树主要操作的复杂度分析:
-
查找:
- 红黑树的查找操作与二叉搜索树类似,通过比较节点值从根节点逐层向下查找。由于红黑树的高度最多为 O(logn),因此查找操作的复杂度为O(logn)。
-
插入:
- 插入操作首先按照二叉搜索树的规则找到插入位置,复杂度为O(logn)。然后,通过重新着色和旋转来保持红黑树的平衡。每次插入操作最多需要进行两次旋转,因此插入操作的复杂度为 O(logn)。
-
删除:
- 删除操作也首先按照二叉搜索树的规则找到要删除的节点,复杂度为 O(logn)。删除后,通过重新着色和旋转来保持红黑树的平衡。每次删除操作最多需要进行三次旋转,因此删除操作的复杂度为O(logn)。
7.2与 AVL 树的比较
红黑树与 AVL 树都是自平衡二叉搜索树,但它们在具体实现和性能特性上有所不同。以下是两者的比较:
-
平衡性:
- AVL 树:高度平衡,确保每个节点的左右子树高度差最多为 1。这意味着 AVL 树通常比红黑树更加平衡。
- 红黑树:通过颜色和旋转规则保持平衡,但允许更松散的平衡条件。这使得红黑树的高度可能稍高于 AVL 树,但仍然在 O(logn) 范围内。
-
插入和删除操作:
- AVL 树:由于严格的平衡条件,插入和删除操作可能需要进行较多的旋转。插入操作的平均旋转次数为 1.44 次,删除操作的平均旋转次数为 2.44 次。
- 红黑树:由于较为宽松的平衡条件,插入和删除操作所需的旋转次数通常较少。插入操作最多需要进行两次旋转,删除操作最多需要进行三次旋转。
-
查找性能:
- AVL 树:由于更严格的平衡条件,AVL 树的查找性能在理论上优于红黑树。然而,在实际应用中,这种性能差异通常并不明显,尤其是在数据规模较大时。
-
适用场景:
- AVL 树:适用于查找操作较为频繁、插入和删除操作较少的场景,如数据库索引和只读数据结构。
- 红黑树:适用于插入和删除操作较为频繁的场景,如操作系统的任务调度和动态集合操作。红黑树在这些场景中由于旋转次数较少,能够提供更好的整体性能。
8.红黑树的迭代器设计
红黑树的迭代器设计需要支持遍历树中的所有节点,并能够执行前向和后向遍历操作。迭代器在红黑树中的作用类似于指针,能够指向树中的节点,并提供便捷的节点访问和遍历功能。
8.1迭代器结构
红黑树的迭代器通过模板参数支持泛型,并包含当前节点和树根节点的指针。下面是迭代器的定义:
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node; // 当前节点Node* _root; // 树根节点RBTreeIterator(Node* node, Node* root): _node(node), _root(root){}Self& operator++();//待实现Self& operator--();//待实现Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}bool operator== (const Self& s){return _node == s._node;}
};
8.2前向迭代(operator++
)
前向迭代操作用于遍历树的下一个节点。根据当前节点的位置,前向迭代的实现分为两种情况:
-
当前节点有右子树:如果当前节点有右子树,则下一个节点是右子树的最左节点。
-
当前节点没有右子树:如果当前节点没有右子树,则沿着父节点向上移动,直到找到一个节点,该节点是其父节点的左子节点。这个父节点就是下一个节点。
Self& operator++()
{if (_node->_right){// 当前节点有右子树,找到右子树的最左节点Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{// 当前节点没有右子树,向上找第一个是左子节点的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}
8.3后向迭代(operator--
)
后向迭代操作用于遍历树的前一个节点。根据当前节点的位置,后向迭代的实现分为三种情况:
-
当前节点是
end()
:如果当前节点是end()
(空节点),则下一个节点是整棵树的最右节点。 -
当前节点有左子树:如果当前节点有左子树,则下一个节点是左子树的最右节点。
-
当前节点没有左子树:如果当前节点没有左子树,则沿着父节点向上移动,直到找到一个节点,该节点是其父节点的右子节点。这个父节点就是下一个节点。
Self& operator--()
{if (_node == nullptr) // end(){// 当前节点是end(),找到最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 当前节点有左子树,找到左子树的最右节点Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 当前节点没有左子树,向上找第一个是右子节点的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}
9.红黑树的模拟实现代码
#pragma once
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
using namespace std;enum Color { RED, BLACK };template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _color;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}Self& operator++(){if (_node->_right){// 右不为空,右子树最左节点就是中序第一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{// 孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr) // end(){// --end(),特殊处理,走到中序最后一个节点,整棵树的最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 左子树不为空,中序左子树最后一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}bool operator== (const Self& s){return _node == s._node;}
};template<class K, class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
private:Node* _root = nullptr;
public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}RBTree() = default;RBTree(const RBTree& t){_root = _Copy(t._root);}RBTree& operator=(RBTree t){swap(_root, t._root);//交换根节点return *this;}~RBTree(){_Destroy(_root);_root = nullptr;}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_color = BLACK;return make_pair(Iterator(_root, _root), true);}KeyOfT kot;//获取键值Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) == kot(data)){return make_pair(Iterator(cur, _root), false);}parent = cur;if (kot(cur->_data) > kot(data)){cur = cur->_left;}else //kot(cur->_data) > kot(data){cur = cur->_right;}}cur = new Node(data);Node* newNode = cur;if (KeyOfT()(data) < KeyOfT()(parent->_data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_color == RED){Node* grandFather = parent->_parent;// g// / \// p u if (parent == grandFather->_left){Node* uncle = grandFather->_right;if (uncle && uncle->_color == RED){// 叔叔是红色,变色再继续向上调整parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;cur = grandFather;parent = cur->_parent;}else{// 叔叔是黑色/叔叔为空,旋转+变色if (cur == parent->_left){// g// / \// p u// ///cRotateR(grandFather);parent->_color = BLACK;grandFather->_color = RED;}else{// g// / \// p u// \// cRotateL(parent);RotateR(grandFather);cur->_color = BLACK;grandFather->_color = RED;}break;}}else{// g// / \// u pNode* uncle = grandFather->_left;// 叔叔是红色,变色再继续向上调整if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;cur = grandFather;parent = cur->_parent;}else // 叔叔是黑色/叔叔为空,旋转+变色{// g// / \// u p// \// cif (cur == parent->_right){RotateL(grandFather);parent->_color = BLACK;grandFather->_color = RED;}else{// g// / \// u p// /// cRotateR(parent);// g// / \// u c// \// pRotateL(grandFather);cur->_color = BLACK;grandFather->_color = RED;}break;}}}_root->_color = BLACK;return make_pair(Iterator(newNode, _root), true);}void InOrder(){_InOrder(_root);cout << endl;}int Size(){return _Size(_root);}int Height(){return _Height(_root);}
private:Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_color = root->_color;newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);if (newRoot->_left)newRoot->_left->_parent = newRoot;if (newRoot->_right)newRoot->_right->_parent = newRoot;return newRoot;}void _Destroy(Node* root){if (root == nullptr)return;_Destroy(root->_left);_Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);//cout << root->_kv.first << " " << root->_kv.second << endl;cout<<root->_data<<" ";_InOrder(root->_right);}int _Size(Node* root){if (root == nullptr)return 0;return 1 + _Size(root->_left) + _Size(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;return 1 + max(_Height(root->_left), _Height(root->_right));}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}
};
10.基于红黑树的map模拟实现
以下是基于红黑树实现的 map
类的代码,其中复用了红黑树的实现。这里的 map
类使用红黑树来存储键值对,并提供插入、删除和查找操作。
template <class Key, class Value>
struct KeyValuePair {Key first;Value second;KeyValuePair(const Key& k = Key(), const Value& v = Value()): first(k), second(v) {}bool operator<(const KeyValuePair& kv) const {return first < kv.first;}bool operator>(const KeyValuePair& kv) const {return first > kv.first;}bool operator==(const KeyValuePair& kv) const {return first == kv.first;}
};template<class Key, class Value, class KeyOfT = KeyValuePair<Key, Value>>
class Map {
private:RBTree<KeyValuePair<Key, Value>, KeyValuePair<Key, Value>&, KeyValuePair<Key, Value>*> _tree;public:typedef typename RBTree<KeyValuePair<Key, Value>, KeyValuePair<Key, Value>&, KeyValuePair<Key, Value>*>::Iterator Iterator;Map() {}pair<Iterator, bool> Insert(const Key& key, const Value& value) {return _tree.Insert(KeyValuePair<Key, Value>(key, value));}bool Erase(const Key& key) {return _tree.Delete(KeyValuePair<Key, Value>(key));}Iterator Find(const Key& key) {return _tree.Find(KeyValuePair<Key, Value>(key));}Value& operator[](const Key& key) {Iterator it = Find(key);if (it != _tree.End()) {return it->second;} else {auto result = Insert(key, Value());return result.first->second;}}Iterator Begin() {return _tree.Begin();}Iterator End() {return _tree.End();}
};
11.结语
红黑树作为一种高效的自平衡二叉查找树,在实际应用中得到了广泛使用。它通过重新着色和旋转操作保持树的平衡,保证了插入、删除和查找操作的时间复杂度为 O(log n)。与 AVL 树相比,红黑树在插入和删除操作中具有更高的效率,非常适合频繁更新的场景。希望通过本文的介绍,大家能更好地理解和应用红黑树。