红黑树进阶：正向与反向迭代器的实现及map、set的封装实践

文章目录

一、引言
二、红黑树迭代器设计
- 1、迭代器的基本概念和分类
- 2、正向迭代器设计
- - a.迭代器结构定义
  - b.迭代器的 ++与 --
- 3、反向迭代器设计
- - a.反向迭代器的必要性
  - b.反向迭代器的实现要点
- 4、红黑树封装迭代器
三、使用红黑树实现Map
四、红黑树实现Set
五、细节理解
- 1、 typname的使用
- 2、map和set中仿函数与红黑树中 KeyOfT 的关系
RBTree.h（红黑树源码）

一、引言

map和set是两种常见的数据结构，它们分别用于存储键值对和无序集合。红黑树作为一种高效的平衡搜索树，非常适合用于封装这两种数据结构。通过红黑树的特性，我们可以保证map和set在插入、删除和查找操作时的性能稳定且高效。此外，红黑树的有序性也使得map和set在遍历元素时能够按照特定的顺序进行，满足了更多实际应用的需求。

迭代器是一种设计模式，它允许我们顺序访问容器中的元素。对于红黑树来说，设计高效的迭代器是实现其封装Map和Set的关键之一。通过迭代器，我们可以方便地遍历红黑树中的节点，从而实现Map和Set的遍历操作。

在本文中，我们将首先探讨红黑树的正向和反向迭代器设计。正向迭代器允许我们按照中序遍历的顺序访问红黑树的节点，而反向迭代器则允许我们按照逆中序遍历的顺序访问节点。这些迭代器的设计将为我们后续封装Map和Set提供便利。

红黑树基础回顾 -> 深入解析红黑树（RB-Tree）：原理、操作及应用

二、红黑树迭代器设计

1、迭代器的基本概念和分类

迭代器的主要目的是简化对容器的遍历操作，使得无论底层数据结构是顺序表、链表还是树，都可以使用相同的方式来遍历。

在C++中，迭代器通常被实现为类的内部类型，它封装了对容器中元素的指针或引用，并提供了一组操作符重载（如*、->、++、--等）以便对容器进行遍历操作。通过迭代器，可以访问容器中的元素，检查迭代器的有效性（即是否指向一个有效的元素），以及比较两个迭代器是否相等或一个迭代器是否在另一个迭代器之前。

2、正向迭代器设计

a.迭代器结构定义

其中 typedef RBTreeNode<T> Node;是红黑树节点的定义，我们可以在文末的红黑树代码中观察。

template<class T,class Ptr,class Ref>
struct RBTreeIterator {typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;Node* _node;RBTreeIterator(Node* node = nullptr):_node(node){}Ref operator*() { return _node->_data; }Ptr operator->() { return &_node->_data; }bool operator!=(const Self& s)const { return _node != s._node; }bool operator==(const Self& s) const { return _node == s._node; }
private:void increment();void decrement();
};

Ref operator*() const:
这个函数重载了解引用运算符*。它返回当前迭代器所指向的节点的数据成员的引用（_node->_data）。这使得你可以通过解引用迭代器来访问它指向的元素，就像访问指针所指向的对象一样。例如，如果你有一个迭代器it指向红黑树中的一个元素，你可以通过*it来访问这个元素的值。
Ptr operator->() const:
这个函数重载了成员访问运算符->。它返回一个指向当前迭代器所指向的节点的数据成员的指针（&_node->_data）。这使得你可以通过迭代器来直接访问它所指向元素的成员，就像通过指针访问对象的成员一样。例如，如果元素是一个具有成员member的对象，你可以通过it->member来访问它。
bool operator!=(const Self& s) const:
这个函数重载了不等于运算符!=。它比较当前迭代器和另一个迭代器s是否指向不同的节点（_node != s._node）。如果它们指向的节点不同，则返回true，否则返回false。这使得你可以使用标准循环结构，如while或for循环，来遍历迭代器范围，直到迭代器不等于另一个迭代器（通常是容器的end()迭代器）。
bool operator==(const Self& s) const:
这个函数重载了等于运算符==。它比较当前迭代器和另一个迭代器s是否指向相同的节点（_node == s._node）。如果它们指向同一个节点，则返回true，否则返回false。这允许你检查两个迭代器是否指向相同的位置。

这些操作符重载使得迭代器可以像内置指针一样使用，提供了一种更加自然和直观的方式来遍历容器中的元素。同时，由于迭代器内部封装了对节点的引用或指针，它们也提供了更好的封装和抽象，隐藏了底层数据结构的复杂性。

b.迭代器的 ++与 –

递增和递减操作是迭代器设计的关键部分。对于红黑树的迭代器来说，递增操作需要找到当前节点的后继节点，而递减操作需要找到当前节点的前驱节点。

递增操作 increment()
- 如果当前节点有右子树，则后继节点是右子树中的最左节点。
- 如果当前节点没有右子树，则后继节点是当前节点沿父节点链向上移动时遇到的第一个不是从父节点的右子树下来的节点。

void increment() {if (_node->_right != nullptr) {// 如果当前节点有右子树，找到右子树中的最左节点  Node* subLeft = _node->_right;while (subLeft->_left) {subLeft = subLeft->_left;}_node = subLeft;}else {// 如果当前节点没有右子树，沿父节点链向上移动  Node* cur = _node;Node* parent = cur->_parent;while (parent != nullptr && cur == parent->_right) {cur = parent;parent = parent->_parent;}_node = parent;}
}

递减操作 decrement()
- 如果当前节点有左子树，则前驱节点是左子树中的最右节点。
- 如果当前节点没有左子树，则前驱节点是当前节点沿父节点链向上移动时遇到的第一个不是从父节点的左子树下来的节点。

void decrement() {if (_node->_left != nullptr) {// 如果当前节点有左子树，找到左子树中的最右节点  Node* subRight = _node->_left;while (subRight->_right != nullptr) {subRight = subRight->_right;}_node = subRight;}else {// 如果当前节点没有左子树，沿父节点链向上移动  Node* cur = _node;Node* parent = cur->_parent;while (parent != nullptr && cur == parent->_left) {cur = parent;parent = parent->_parent;}_node = parent;}
}

前置递增和递减运算符 operator++() 和 operator--()

这两个函数是前置递增和递减运算符的重载。它们分别调用上文的 increment() 和 decrement() 函数来改变迭代器指向的当前节点，并返回迭代器的引用（*this）。

Self& operator++() {increment();return *this;
}Self& operator--() {decrement();return *this;
}

在调用这些函数时，运算符前面的迭代器对象会首先被更新（递增或递减），然后返回更新后的迭代器对象的引用。

后置递增和递减运算符 operator++(int) 和 operator--(int)

这两个函数是后置递增和递减运算符的重载。它们用于创建迭代器的一个临时副本，更新原始迭代器，然后返回这个临时副本。这种形式的递增和递减操作会先返回迭代器当前指向的元素的引用，然后再移动迭代器。

Self operator++(int) {Self tmp(*this);increment();return tmp;
}Self operator--(int) {Self tmp(*this);decrement();return tmp;
}

注意，这两个函数的参数是一个未命名的整型参数。这个参数的存在纯粹是为了区分前置和后置版本的运算符。在实际调用中，这个参数不会被传递任何值，它仅仅是一个占位符，用于区分前置和后置版本。由于后置版本的运算符实际上先返回当前值再递增或递减，所以需要先创建一个当前迭代器的副本（tmp），然后递增或递减迭代器，最后返回这个副本。

这样的设计使得用户可以用如下两种方式使用迭代器：

// 前置版本
++it;  // 先移动迭代器，再返回新的迭代器
--it;  // 先移动迭代器，再返回新的迭代器// 后置版本
it++;  // 先返回当前迭代器，再移动迭代器
it--;  // 先返回当前迭代器，再移动迭代器

后置版本的迭代器主要用于那些需要在表达式中先返回当前值再改变迭代器位置的场景，比如在循环中：

for (iterator it = container.begin(); it != container.end(); ++it) {// ...
}

在这里，++it 使用了后置递增运算符，它首先返回 it 当前指向的元素的迭代器，然后递增 it 以指向下一个元素。在循环的每次迭代中，这允许我们安全地使用 it 来访问当前元素，同时准备移动到下一个元素。

3、反向迭代器设计

a.反向迭代器的必要性

反向迭代器的必要性主要体现在需要逆序遍历容器或集合元素时。在C++ STL中，很多容器如vector、list、deque等，都提供了正向迭代器来遍历元素，但有时我们可能需要从后往前遍历元素，这时候就需要反向迭代器。例如，在需要查找一个序列中最后一个满足特定条件的元素时，使用反向迭代器可以显著提高效率。

b.反向迭代器的实现要点

正向与反向迭代器应该提供统一的接口，使得用户可以通过相同的方式来操作它们。

封装正向迭代器：反向迭代器内部封装了一个正向迭代器，通过操作这个正向迭代器来实现反向迭代。
反向操作：反向迭代器的++、--、*、->等操作需要与正向迭代器的相应操作相反。例如，反向迭代器的++实际上是调用正向迭代器的--，而反向迭代器的--则是调用正向迭代器的++。
类型别名：反向迭代器需要定义一些类型别名，如Ref和Ptr，来指代结点数据的引用和指针。这些类型别名通常是从正向迭代器中继承的。
比较操作：反向迭代器还需要定义比较操作，如operator!=和operator==，以便能够比较两个反向迭代器是否相等或不等。这些操作也是通过调用正向迭代器的相应操作来实现的。
解引用操作：无论是正向迭代器还是反向迭代器，都应该提供*和->操作来访问结点数据。
递增和递减操作：正向迭代器提供++和--来移动迭代器，反向迭代器也应该提供相同的操作，但它们的语义应该是相反的。
比较操作：正向和反向迭代器都应该提供比较操作，如!=和==，以便判断两个迭代器是否指向同一位置。

//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator{typedef ReverseIterator<Iterator> Self; //反向迭代器的类型typedef typename Iterator::Ref Ref; //结点指针的引用typedef typename Iterator::Ptr Ptr; //结点指针Iterator _it; //反向迭代器所封装的正向迭代器ReverseIterator(Iterator it):_it(it) //根据所给正向迭代器构造一个反向迭代器{}Ref operator*() { return *_it; }Ptr operator->() { return _it.operator->(); }Self& operator++() {--_it; return *this;}Self& operator--() {++_it; return *this;}bool operator!=(const Self& s) const { return _it != s._it;	}bool operator==(const Self& s) const { return _it == s._it; }
};

4、红黑树封装迭代器

有了上面的两个模板类后，我们仅需在红黑树所在类中添加：

typedef RBTreeIterator<T, T*, T&> iterator;
typedef ReverseIterator<iterator> reverse_iterator;

RBTreeIterator 是一个代表红黑树（Red-Black Tree）迭代器的模板类，用于遍历红黑树容器中的元素。

iterator 类型别名被定义为 RBTreeIterator<T, T*, T&>，简化了对红黑树迭代器的引用，使得我们使用红黑树时能够更简单地引用迭代器类型。

reverse_iterator 类型别名被定义为 ReverseIterator<iterator>，它表示反向迭代器，用于以相反的顺序遍历红黑树中的元素。这个反向迭代器封装了正向迭代器（即 iterator 类型），并提供了反向迭代所需的方法。

这种设计让用户可以透明地选择使用正向迭代器还是反向迭代器来遍历红黑树，而不需要关心底层实现细节。

以下是如何使用这些迭代器类型别名的简单示例：

// 假设 RBTree 是一个红黑树容器模板类
template<class K,class T,class KeyOfT>
class RBTree {
public:// ... 其他成员和方法 ...// 迭代器类型别名typedef RBTreeIterator<T, T*, T&> iterator;typedef ReverseIterator<iterator> reverse_iterator;// 获取指向容器中第一个元素的迭代器iterator begin() {Node* subL = _root;while (subL && subL->_left) {subL = subL->_left;}return iterator(subL);}// 获取指向容器末尾之后位置的迭代器iterator end() { return nullptr; }reverse_iterator rbegin(){Node* right = _root;while (right && right->_right){right = right->_right;}return reverse_iterator(iterator(right));}reverse_iterator rend(){return reverse_iterator(iterator(nullptr));}//end()  rbegin()在使用时存在缺陷。// ... 其他成员和方法 ...
};int main() {RBTree<int> tree;// ... 向tree中添加元素 ...// 使用正向迭代器遍历树for (RBTree<int>::iterator it = tree.begin(); it != tree.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用反向迭代器逆序遍历树for (RBTree<int>::reverse_iterator rit = tree.rbegin(); rit != tree.rend(); ++rit) {std::cout << *rit << " ";}std::cout << std::endl;return 0;
}

在这个示例中，RBTree 类提供了正向迭代器 iterator 和反向迭代器 reverse_iterator。用户可以通过这些迭代器类型别名方便地遍历红黑树中的元素，无论是正向还是反向。

三、使用红黑树实现Map

map模板类中，我们使用了红黑树RBTree来存储键值对。为了适配红黑树，我们定义了一个内部结构体MapKeyOfT，它用于从键值对pair<K, V>中提取键K。这样，红黑树就能根据键来排序和查找键值对了。

在map的公开接口中，我们定义了正向和反向迭代器类型别名iterator和reverse_iterator，它们分别对应于红黑树的正向和反向迭代器。我们也提供了begin()、end()、rbegin()和rend()方法来获取对应的迭代器。

template<class K,class V>
class map {struct MapKeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;reverse_iterator rbegin() { return _t.rbegin(); }reverse_iterator rend() { return _t.rend(); }iterator begin() { return _t.begin(); }iterator end() { return _t.end(); }iterator find(const K& key) { return _t.Find(key); }pair<iterator, bool> insert(const pair<K, V>& kv) {return _t.Insert(kv);}V& operator[](const K& key) {pair<iterator, bool>ret = insert({ key,V() });return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT>_t;
};

find()方法用于在map中查找具有指定键的元素，调用了红黑树的Find()方法来实现查找功能。

insert()方法用于向map中插入一个键值对。它返回一个包含迭代器和一个布尔值的pair，迭代器指向新插入的元素（如果已存在则指向已存在的元素），布尔值表示是否成功插入了新元素，通过调用红黑树的Insert()方法实现。

operator[]方法用于通过键来访问或插入对应的值。如果键不存在于map中，则插入一个新的键值对，其中键为传入的键，值为类型的默认值（通过V()调用构造函数创建）。然后返回值的引用，这样用户就可以直接修改它。注意，由于这种方式可能在键不存在时改变map的内容，因此在使用时需要小心。

在类的私有部分，我们定义了一个红黑树对象_t来实际存储键值对。红黑树的键类型为K，值类型为pair<const K, V>，这样每个节点就存储了一个键值对。键的提取函数是MapKeyOfT，它确保红黑树能够正确地对键值对进行排序和查找。

四、红黑树实现Set

set模板类使用红黑树来存储唯一的键，并且提供了常见的集合操作。与map类似，这里也定义了一个内部结构体SetKeyOfT，用于从键K中提取键本身（在这个情况下，提取操作实际上只是返回传入的键）。

与map类似，在公开接口中，我们仍然定义了正向和反向迭代器类型别名iterator和reverse_iterator，用于遍历集合中的元素。同时，提供了begin()、end()、rbegin()和rend()方法来获取相应的迭代器。

template<class K>
class set {struct SetKeyOfT {const K& operator()(const K& key) {return key;}};
public:typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;reverse_iterator rbegin() { return _t.rbegin(); }reverse_iterator rend() { return _t.rend(); }iterator begin() { return _t.begin(); }iterator end() { return _t.end(); }pair<iterator, bool> insert(const K& key) { return _t.Insert(key); }private:RBTree<K, const K, SetKeyOfT> _t;
};

insert()方法用于向集合中插入一个键。如果键已经存在于集合中，则不会插入重复键。该方法返回一个包含迭代器和布尔值的pair，迭代器指向新插入的键（或已存在的键），布尔值表示是否成功插入了新键。

在类的私有部分，我们定义了一个红黑树对象_t来存储键。由于集合中的元素是唯一的，因此红黑树的键类型为K，值类型为const K。这样，每个节点存储了一个不可变的键。键的提取函数是SetKeyOfT，它确保红黑树能够正确地对键进行排序和查找。

注意，这个set实现是基于红黑树的，因此它提供了对数时间复杂度的查找、插入和删除操作。同时，由于红黑树的自平衡特性，它能够在数据动态变化时保持较快的查找速度。

五、细节理解

1、 typname的使用

我们以set为例：

typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;

在这里RBTree<K, const K, SetKeyOfT> 创建了一个红黑树模板实例，其中：

K 是键的类型。
const K 是值的类型，表示集合中的元素是不可变的。
SetKeyOfT 是一个结构体，它用于从键中提取键（实际上在这里并没有进行转换，因为键已经是所需的形式）。

接着，通过作用域解析运算符 ::，你从这个红黑树模板实例中获取了 iterator 和 reverse_iterator 类型的定义，并将它们分别重命名为 iterator 和 reverse_iterator，以便在 set 类内部和外部都可以方便地引用它们。

这样的做法在设计模板类时是非常常见的，主要有以下几个用意：

抽象和封装：通过定义类型别名，我们隐藏了底层数据结构的实现细节。用户不需要知道底层是红黑树还是其他数据结构，只需要通过set类提供的接口进行操作即可。这增加了代码的抽象性和封装性，使得代码更加易于理解和维护。
简化接口：类型别名使得set类的接口更加简洁和一致。用户可以直接使用iterator和reverse_iterator来遍历集合，而不需要记住底层数据结构的迭代器类型。这提高了代码的易用性和可读性。
提供统一访问方式：无论是正向遍历还是反向遍历，用户都可以通过统一的接口进行访问。这降低了用户的学习成本，提高了代码的可重用性。
灵活性：通过类型别名，我们可以轻松地更改底层数据结构而不需要修改使用该数据结构的代码。例如，如果将来决定使用另一种数据结构来实现set，只需要更改类型别名的定义即可，而不需要修改所有使用迭代器的代码。
遵循STL风格：在C++标准模板库（STL）中，这种使用类型别名的做法是非常普遍的。遵循STL风格可以使得自定义的容器类与STL中的容器类在接口和使用方式上保持一致，从而提高了代码的兼容性和可移植性。

综上所述，通过定义类型别名来抽象和封装底层数据结构的细节，我们可以创建一个更加简洁、易用、灵活和兼容的set类。这样的做法在设计和实现模板类时是非常有益的。

2、map和set中仿函数与红黑树中 KeyOfT 的关系

⚠️理解map和set中仿函数的用意：

在这里插入图片描述

在我实现的map和set中，MapKeyOfT和SetKeyOfT（或类似的键提取器）与红黑树中的KeyOfT都扮演着从容器中存储的元素中提取键的角色。

首先，让我们明确每个键提取器的用途：

MapKeyOfT：在map容器中，每个元素都是一个键值对（pair<const Key, T>）。MapKeyOfT的作用是从这个键值对中提取出键（Key）部分，以便在红黑树中进行搜索、排序和平衡操作。
SetKeyOfT：在set容器中，每个元素就是一个单独的键（Key）。SetKeyOfT的作用相对简单，它直接从元素中提取出键，因为元素本身就是键。
KeyOfT：在红黑树的上下文中，KeyOfT是一个更通用的概念，用于从某个类型的元素中提取出键。这个键用于在红黑树中进行比较和排序，以确保树的平衡和高效的搜索性能。

现在，让我们讨论它们之间的关系：

在STL或其他类似的关联容器实现中，map和set通常是基于红黑树实现的。这意味着MapKeyOfT和SetKeyOfT实际上是特定于map和set的键提取器，它们根据容器的需求定制了从元素中提取键的方式。这些键提取器在内部被用于与红黑树进行交互，以确保正确的搜索和排序行为。

从某种程度上说，MapKeyOfT和SetKeyOfT可以看作是KeyOfT在map和set容器中的特化版本。它们针对键值对和单个键的不同情况进行了定制，但背后的原理是相同的：都是从某种类型的元素中提取出用于比较和排序的键。

总结来说，MapKeyOfT、SetKeyOfT和KeyOfT都是为了从元素中提取键而存在的。

RBTree.h（红黑树源码）

#pragma once 
#include <iostream>
#include"ReverseIterator.h"
using namespace std;enum Color { RED, BLACK };
template<class T>
struct RBTreeNode {RBTreeNode(const T& data) :_data(data), _color(RED) {}RBTreeNode<T>* _left = nullptr;RBTreeNode<T>* _right = nullptr;RBTreeNode<T>* _parent = nullptr;T _data;Color _color;
};template<class K,class T,class KeyOfT>
class RBTree {typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T, T*, T&> iterator;typedef ReverseIterator<iterator> reverse_iterator;reverse_iterator rbegin(){Node* right = _root;while (right && right->_right){right = right->_right;}return reverse_iterator(iterator(right));}reverse_iterator rend(){return reverse_iterator(iterator(nullptr));}iterator begin() {Node* subL = _root;while (subL && subL->_left) {subL = subL->_left;}return iterator(subL);}iterator end() { return nullptr; }pair<iterator, bool> Insert(const T& data) {if (!_root) {_root = new Node(data);_root->_color = BLACK;return { iterator(_root),true };}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur) {if (kot(cur->_data) < kot(data)) {parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)) {parent = cur;cur = cur->_left;}else {return { iterator(cur), false };}}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_color == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else {if (cur == parent->_left) {RotateR(grandparent);grandparent->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandparent);grandparent->_color = RED;cur->_color = BLACK;}break;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_color == RED) {parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right) {RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}_root->_color = BLACK;return { iterator(newnode),true };}void _Inorder(Node* root) {if (root == nullptr) {return;}_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}void  Inorder() {_Inorder(_root);cout << endl;}bool Check(Node* cur, int blackNum, int refBlackNum) {if (cur == nullptr) {if (blackNum != refBlackNum){cout << "黑色节点数量不相等" << endl;return false;}//cout << "黑色节点数量：" << blackNum << endl;return true;}if (cur->_color == RED && cur->_parent->_color == RED) {cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}if (cur->_color == BLACK) {++blackNum;}return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);}bool IsBalance() {if (_root != nullptr && _root->_color == RED)return false;int refBlackNum = 0;Node* cur = _root;while (cur != nullptr) {if (cur->_color == BLACK)refBlackNum++;cur = cur->_left;}return Check(_root, 0, refBlackNum);}iterator Find(const K& key) {Node* cur = _root;while (cur) {if (cur->_kv.first < key)cur = cur->_right;else if (cur->_kv.first > key)cur = cur->_left;elsereturn cur;}return NULL;}size_t Size() { return _Size(_root); }size_t _Size(Node* root) {if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}int _Height(Node* root) {if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int Height() { return _Height(_root); }void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root) {_root = subR;subR->_parent = nullptr;}else {if (ppnode->_left == parent)ppnode->_left = subR;elseppnode->_right = subR;subR->_parent = ppnode;}}void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root) {_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = subL;elseppnode->_right = subL;subL->_parent = ppnode;}}
private:Node* _root = nullptr;
};

本文完整代码： map与set · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)