第十六讲：AVL树和红黑树

目录

1、底层结构

2、AVL树

2.1、概念

2.2、AVL树的插入

2.2.1、右单旋

2.2.2、左单旋

2.2.3、左右单旋

2.2.4、右左单旋

2.3、AVL树的删除

2.4、AVL树的性能

2.5、模拟实现

3、红黑树

3.1、概念

3.2、红黑树的插入

3.2.1、情况一

3.2.2、情况二

3.2.3、情况三

3.3、红黑树的删除

3.4、红黑树的性能

3.5、模拟实现

4、模拟实现map和set

1、底层结构

前面对map、multimap、set以及multiset进行了简单的介绍，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用红黑树来实现。

2、AVL树

2.1、概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1、它的左右子树都是AVL树。

2、左右子树高度之差(简称平衡因子)的绝对值不超过1。

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，搜索时间复杂度O(logN)。

2.2、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。AVL树的插入过程可以分为两步：

1、按照二叉搜索树的方式插入新节点。

2、调整节点的平衡因子。

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构， 使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种以下四种：分别为右单旋、左单旋、左右单旋、右左单旋。

2.2.1、右单旋

新节点插入较高左子树的左侧（左左）：右单旋

如图所示：

其中，a、b、c分别为高度为h的AVL树，h大于等于0。

即：对60进行右单旋，旋转完成后再考虑平衡因子的更新。

2.2.2、左单旋

新节点插入较高右子树的右侧（右右）：左单旋

如图所示：

其中，a、b、c分别为高度为h的AVL树，h大于等于0。

即：对30进行左单旋，旋转完成后再考虑平衡因子的更新。

2.2.3、左右单旋

新节点插入较高左子树的右侧（左右）：先左单旋再右单旋

如图所示：

其中，a、d分别为高度为h的AVL树，b、c分别为高度为h-1的AVL树，h大于等于0。如果h=0，60这个结点即是新增的结点。

即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。

2.2.4、右左单旋

新节点插入较高右子树的左侧（右左）：先右单旋再左单旋

如图所示：

其中，a、d分别为高度为h的AVL树，b、c分别为高度为h-1的AVL树，h大于等于0。如果h=0，60这个结点即是新增的结点。

即：先对90进行右单旋，再对30进行左单旋，旋转完成后再考虑平衡因子的更新。

2.3、AVL树的删除

删除比插入还要复杂，具体实现可参考《算法导论》或《数据结构（用面向对象方法与C++描述）》殷人昆版。

2.4、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即O（log (N)）。

2.5、模拟实现

template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}

AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;

pair<K, V> _kv;
int _bf; // 平衡因子
};

template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv) // 插入
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}

Node* parent = nullptr;
Node* cur = _root;

while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}

cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}

/*
* 新结点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性。
*
* cur插入之前，parent的平衡因子分为以下三种情况：-1，0，1。
*
* 1、如果cur插入到parent的左侧，只需要给parent的平衡因子-1即可。
* 2、如果cur插入到parent的右侧，只需要给parent的平衡因子+1即可。
*/

while (parent)
{
// 修改平衡因子
if (cur == parent->_left)
{
parent->_bf–;
}
else
{
parent->_bf++;
}

/*
* 此时，parent的平衡因子可能有三种情况：0、正负1、正负2
*
* 1、如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功。
* 因为新插入的结点填上了低的那一边，不用再继续向上更新。
*
* 2、如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树
* 的高度增加，需要继续向上更新。
*
* 3、如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。
*/

if (parent->_bf == 0) // 平衡因子为0，不用再向上更新平衡因子。
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 平衡因子为正负1，向上调整。
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 平衡因子为正负2，因此需要做旋转处理
{
// 旋转，目的是保持树的平衡
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent); // 左旋
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent); // 右旋
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent); // 右左旋
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent); // 左右旋
}

//旋转完成后，树已经平衡了。
break;
}
else
{
assert(false);
}
}
return true;
}

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

parent->_right = subRL;
subR->_left = parent;

Node* parentParent = parent->_parent;

parent->_parent = subR;
if(subRL)
subRL->_parent = parent;

if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_bf = subR->_bf = 0;
}

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

parent->_left = subLR;
if (subLR) // subLR可能是空的。
subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (_root == parent) // parent可能是根结点。
{
_root = subL;
subL->_parent = nullptr;
}
else // parent不是根结点，是子树。
{
if (parentParent->_left == parent) // 是左子树
{
parentParent->_left = subL;
}
else // 是右子树
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
subL->_bf = parent->_bf = 0;
}

void RotateRL(Node* parent) // 右左旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;

RotateR(parent->_right);
RotateL(parent);

if (bf == 0) // subRL自己就是新增
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1) // subRL的左子树新增
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1) // subRL的右子树新增
{
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}

void RotateLR(Node* parent) // 左右旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(parent->_left);
RotateR(parent);

if (bf == 0)
{
subL->_bf = subLR->_bf = parent->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if(bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}

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

bool IsBalance() // 是否是平衡树
{
return _IsBalance(_root);
}

int Height() // 树的高度
{
return _Height(_root);
}

size_t Size() // 返回元素个数
{
return _Size(_root);
}

Node* 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;
}
else
{
return cur;
}
}
return NULL;
}

private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ':' << root->_kv.second << endl;;
_InOrder(root->_right);
}

bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}

int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);

if (rightHeight – leftHeight != root->_bf)
{
cout << root->_kv.first << ':' << root->_kv.second << " 平衡因子异常" << endl;
return false;
}

return abs(rightHeight – leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}

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;
}

size_t _Size(Node* root)
{
if (root == nullptr)
return 0;

return _Size(root->_left) + _Size(root->_right) + 1;
}

private:
Node* _root = nullptr;
};

3、红黑树

3.1、概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是黑色或者是红色。 通过对任意一条从根到叶子结点的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。如下图所示：

红黑树的性质：

1、每个结点不是红色就是黑色。

2、根节点是黑色的 。

3、如果一个节点是红色的，则它的两个孩子结点是黑色的。（也就是说树中不能出现连续的红色结点。父子结点的颜色只能是：黑+黑、黑+红、红+黑三种情况）。

4、对于每个结点，从该结点到其所有叶子结点的路径上，均包含相同数目的黑色结点 。

5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点）。

从上面红黑树的性质我们可以知道，从根节点开始，如果存在最长路径的话，红黑树中的最长路径是一黑一红间隔的路径，如果存在最短路径的话，最短的路径是全黑结点的路径。

从根节点开始，假设红黑树的每条路径都有N个黑色结点，则每条路径的结点数量的范围为[N，2N]。

3.2、红黑树的插入

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

1、按照二叉搜索的树规则插入新节点。

2、检测新节点插入后，红黑树的性质是否造到破坏。

因为新节点的默认颜色是红色，因此如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

注意：之所以新结点的默认颜色给红色，原因是破坏红黑树的第三条性质比破坏红黑树的第四条所付出的代价小。

3.2.1、情况一

情况一：cur为红，p为红，g为黑，u存在且为红，例如

其中a、b、c、d、e分别是红黑树。

解决方式：将p和u改为黑，g改为红，然后把g当成cur，继续向上调整。

3.2.2、情况二

情况二：cur为红，p为红，g为黑，u不存在或者u存在且为黑，例如

其中a、b、c、d、e分别是红黑树。

解决方式：

1、若p为g的左孩子，cur为p的左孩子，则针对p进行右旋转，然后p变黑，g变红。

2、若p为g的右孩子，cur为p的右孩子，则针对p进行左旋转，然后p变黑，g变红。

3.2.3、情况三

情况三：cur为红，p为红，g为黑，u不存在或者u存在且为黑，例如

其中a、b、c、d、e分别是红黑树。

解决方式：

1、若p为g的左孩子，cur为p的右孩子，则针对p做左旋转，转换为了情况二。

2、若p为g的右孩子，cur为p的左孩子，则针对p做右旋转，转换成了情况二。

3.3、红黑树的删除

红黑树的删除比插入还要复杂，有兴趣可参考：《算法导论》或者《STL源码剖析》。

3.4、红黑树的性能

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log(N))，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，所以红黑树的性能往往比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用：

1、C++ STL库中的map和set以及mutil_map和mutil_set。

2、Java库。

3、linux内核。

4、其他一些库。

3.5、模拟实现

enum Colour
{
RED,
BLACK
};

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

Colour _col;

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

template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}

Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}

// 新增结点
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}

// 调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) // p在g的左边
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) // u存在且为红
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else // u不存在，或者u存在且为黑
{
if (cur == parent->_left) // cur在p的左边
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else // cur在p的右边
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // p在g的右边
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) // u存在且为红
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

cur = grandfather;
parent = cur->_parent;
}
else // u不存在，或者u存在且为黑
{
if (cur == parent->_right) // cur在p的右边
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else // cur在p的左边
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}

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

parent->_right = subRL;
subR->_left = parent;

Node* parentParent = parent->_parent;

parent->_parent = subR;
if (subRL)
subRL->_parent = parent;

if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
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 (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}

void InOrder()
{
_InOrder(_root);
cout << endl;
}

bool IsBalance()
{
if (_root == nullptr)
return true;

if (_root->_col == RED)
return false;

int refVal = 0; // 参考值
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refVal;
}
cur = cur->_left;
}

int blacknum = 0;
return Check(_root, blacknum, refVal);
}

int Height()
{
return _Height(_root);
}

size_t Size()
{
return _Size(_root);
}

Node* 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;
}
else
{
return cur;
}
}
return NULL;
}

private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;

_InOrder(root->_left);
cout << root->_kv.first << ':' << root->_kv.second << endl;
_InOrder(root->_right);
}

bool Check(Node* root, int blacknum, const int refVal)
{
if (root == nullptr)
{
if (blacknum != refVal)
{
cout << "存在黑色结点数量不相等的路径" << endl;
return false;
}
return true;
}

if (root->_col == RED && root->_parent->_col == RED)
{
cout << "有连续的红色结点" << endl;
return false;
}

if (root->_col == BLACK)
{
++blacknum;
}

return Check(root->_left, blacknum, refVal)
&& Check(root->_right, blacknum, refVal);
}

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;
}

size_t _Size(Node* root)
{
if (root == nullptr)
return 0;

return _Size(root->_left) + _Size(root->_right) + 1;
}

private:
Node* _root = nullptr;
};

4、模拟实现map和set

set和map的底层都是红黑树，因此只需在set和map内部封装一棵红黑树，然后将其接口包装下即可。

RBTree.h：

enum Colour
{
RED,
BLACK
};

template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;

Colour _col;

RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node* _node;

__TreeIterator(Node* node)
:_node(node)
{}

Ref operator*()
{
return _node->_data;
}

Ptr operator->()
{
return &_node->_data;
}

Self& operator–()
{
// 自己实现
}

Self& operator++()
{
if (_node->_right) // 右不为空
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else // 右为空
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}

bool operator!=(const Self& s)
{
return _node != s._node;
}

bool operator==(const Self& s)
{
return _node == s._node;
}
};

//set->RBTree<K, K, SetKeyOfT> _t;
//map->RBTree<K, pair<const K, T>, MapKeyOfT> _t;
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T&, T*> iterator;
typedef __TreeIterator<T, const T&, const T*> const_iterator;

iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}

return iterator(cur);
}

iterator end()
{
return iterator(nullptr);
}

const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}

return const_iterator(cur);
}

const_iterator end() const
{
return const_iterator(nullptr);
}

//pair<iterator, bool> Insert(const T& data)
pair<Node*, bool> Insert(const T& data) // 如果用上面的会有迭代器类型转换的问题。
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);
}

Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;

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 make_pair(cur, false);
}
}

// 新增结点 //
cur = new Node(data);
Node* newnode = cur;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}

//
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(newnode, true);
}

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

parent->_right = subRL;
subR->_left = parent;

Node* parentParent = parent->_parent;

parent->_parent = subR;
if (subRL)
subRL->_parent = parent;

if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
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 (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
private:

Node* _root = nullptr;
};

MyMap.h：

#include "RBTree.h"

namespace bit
{
template<class K, class V>
class map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;//仅key不可改
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; // key以及value都不可改

iterator begin()
{
return _t.begin();
}

iterator end()
{
return _t.end();
}

V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}

pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

MySet.h：

#include "RBTree.h"

namespace bit
{
template<class K>
class set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};

// 对类模板取内嵌类型，加typename告诉编译器这里是类型
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

iterator begin() const
{
return _t.begin();
}

iterator end() const
{
return _t.end();
}

pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}

private:
RBTree<K, K, SetKeyOfT> _t;
};
}