当前位置：首页 > news >正文

【数据结构】AVL树和红黑树的Insert(插入)(实现map.insert)

news 2025/6/29 6:05:51

以AVL树作为底层

节点

Insert

更新平衡因子

旋转

左单旋：

左单旋代码示例：

右单旋：

右单旋代码示例：

双旋：

右左双旋：

右左双旋代码示例：

左右双旋：

左右双旋代码示例：

erase(了解)

验证AVL树是否正确

以红黑树作为底层

节点

Insert

第一种情况

第二种情况

第三种情况

Insert代码示例：

erase(了解)

验证红黑树是否正确

AVL树和红黑树的效率比较

上一篇文章对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的。

【数据结构】map_set前传：二叉搜索树(C++)-CSDN博客文章浏览阅读1k次，点赞30次，收藏25次。二叉搜索树（BST）是一种特殊的二叉树，其左子树所有节点的值小于根节点，右子树所有节点的值大于根节点，且不允许有重复值。BST的常见操作包括插入、查找、删除和中序遍历。插入操作通过比较节点值确定位置，查找操作通过递归或迭代实现，删除操作则需处理多种情况，如删除叶子节点、单子节点或双子节点。中序遍历BST会按升序输出节点值。BST的K模型仅存储键值，适用于查找是否存在；K/V模型存储键值对，适用于字典等场景。BST的局限性在于当数据有序时，树可能退化为链表，导致查找效率降低，此时需使用平衡二叉搜索树来优化。https://blog.csdn.net/suimingtao/article/details/147849074

【语法】C++的map/set_c++ set map模版-CSDN博客文章浏览阅读809次，点赞9次，收藏9次。本文介绍了C++ STL中的关联式容器map和set，以及它们的底层实现——平衡二叉搜索树。map和set通过键值对存储数据，支持高效的查找操作，元素按排序规则组织。set是K模型，map是K/V模型，两者都使用insert添加数据，不允许重复键值。map的节点存储pair类型，支持通过[]操作符访问和修改值。此外，还介绍了multiset和multimap，它们允许键值重复，但不支持[]操作符。文章还详细讲解了insert、find、erase等常用操作的使用方法和注意事项，并通过代码示例展示了如何利用m_c++ set map模版https://blog.csdn.net/suimingtao/article/details/148106387但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

这里所说的平衡树就是AVL树：当向二叉树搜索树中插入新节点后，如果能保证每个节点的左右子树高度差不超过1(需要对树中的节点做调整)，即可降低树的高度从而减少平均搜索长度

保持平衡的方法有很多，这里用的是平衡因子。

每个节点都有一个平衡因子，是右子树的高度-左子树的高度得到的，只要平衡因子在[-1,1]区间，就代表着是一个平衡树，当平衡因子的值是2或-2时，就代表此时以当前节点为根节点的树不平衡，需要旋转。

这样可以让搜索树的效率保持在O(logN)

因为map是K/V模型，set是K模型，只要实现了map，set自然就实现了，所以本篇以实现map为主

以AVL树作为底层

节点

由于map的底层是平衡二叉搜索树，所以底层就是AVL树，这里也以AVL树实现

二叉搜索树的节点有左子树，右子树，键值对(pair类型)。

template<class K,class V>
struct AVTreeNode
{AVTreeNode* _left;//左子树AVTreeNode* _right;//右子树pair<K,V> _kv;//键值对
};

但上面说过，需要给每个节点都引入一个平衡因子，但光加一个平衡因子不行，这样到后面插入时也不能找到当前节点的祖先，就无法更新祖先们的平衡因子，所以这里要构建一个三叉链，也就是还要加一个父亲节点

template<class K,class V>
struct AVTreeNode
{AVTreeNode* _left;//左子树AVTreeNode* _right;//右子树AVTreeNode* _parent;//父节点int _bf;//平衡因子pair<K,V> _kv;//键值对AVTreeNode(const pair<K,V>& kv)//构造函数:_left(nullptr),right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};

(构造函数是为了在后面AVLTree的实现中为节点初始化)

Insert

map的insert只是在二叉搜索树的insert的基础上可以判断是否平衡，若不平衡则旋转

所以还是要先写出来二叉搜索树的insert

bool Insert(const pair<K,V>& kv){if(_root==nullptr)//如果该树目前为空，就把当前值给根{_root = new Node(kv);return true;}//找到要插入的位置Node* cur = _root;Node* parent = nullptr;while(cur){parent = cur;if(kv.first > cur->_kv.first)//如果要插入的值比当前节点大，就往右边找cur = cur->_right;else if(kv.first < cur->_kv.first)//入股要插入的值比当前节点小，就往左边找cur = cur->_left;else//如果相等，插入失败，就返回falsereturn false;}cur = new Node(kv);//为插入的值开辟一个新节点cur->_parent = parent;if(kv.first > parent->_kv.first)//如果新节点在父亲的右边，就插入到右子树中parent->_right = cur;else//如果新节点在父亲的左边，就插入到左子树中parent->_left = cur;return true;}

更新平衡因子

现在再来思考怎么更新平衡因子

如果是像下图这样插入，就只需要更改插入节点的父亲的平衡因子(新插入的节点的平衡因子必然是0)，因为8这棵树的高度并没有改变，还是1，所以不需要让祖先们的平衡因子改变

但如果是像下图这样插入，插入节点的父亲从本来的0个高度变成了1个高度，那父亲的父亲也就需要跟着变，但当高度更新为2时，就要发生旋转，不能再往上更新了

旋转后：

由上可以总结出下面规律：

当新增节点在它父亲的左边，父亲的平衡因子-1；当新增节点在它父亲的右边，父亲的平衡因子+1
若更新后父亲的平衡因子为0，就代表之前为1或-1，只是给短的那一边新增了节点，所以就不需要继续向上更新
若更新后父亲的平衡因子为1或-1，就代表之前为0(为2时就旋转了，所以不可能为2)，即新增了高度，需要向上更新
若更新后父亲的平衡因子为2或-2，不平衡，此时发生旋转，也不需要向上更新

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 (kv.first > cur->_kv.first)//如果要插入节点比当前节点大{//就去右树parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first)//如果要插入节点比当前节点小{//就去左树parent = cur;cur = cur->_left;}else//如果相等，就插入失败{return false;}}cur = new Node(kv);//为要插入节点开辟空间if (_kv.first > parent->_kv.first)//如果当前节点比父亲大，就代表在右树parent->_right = cur;else//否则就在左树parent->_left = cur;cur->_parent = parent;//更新平衡因子while (parent){if (parent->_left == cur)//如果当前节点在父亲的左边parent->_bf--;//平衡因子就-1else//如果当前节点在父亲的右边parent->_bf++;//平衡因子就+1if (parent->_bf == 0)//如果平衡因子更新后是0，就代表两边相等，没有新增高度{break;//就不需要再往上更新了，即跳出}else if (abs(parent->_bf) == 1)//如果平衡因子更新后是1，就代表高度+1，要继续往上更新{//cur和parent往上走一步cur = cur->_parent;parent = cur->_parent;}else//如果平衡因子更新后是2，就不平衡了，那此时就要旋转了{//旋转	}}return true;
}

旋转

旋转分为左单旋、右单旋、右左双旋、左右双旋四种情况

左单旋：

在进行如下图的节点插入后(红色数字为平衡因子)，parent的平衡因子更新为了2，此时就要进行旋转

而因为这是右边高，左边低，所以要进行的是左单旋

只需要把最高的那部分压下来，放到subR的左边即可，如图所示

可以看到，这是将subR原来的左树放到了parent的右树，再将subR的左树置成parent

需要注意的是，不要忘记维护他们的三叉链关系，即旋转完后，subLR->_parent为parent，parent->_parent为subL

此时要旋转的树就是整棵树的根，所以subL->_parent要置成nullptr；但如果要旋转的树也只是一颗子树，要让subL的parent指向原来的parent的父亲，并让原来的parent的父亲的左/右子树指向subL

并且旋转完后parent和subL的平衡因子都变成了0

左单旋代码示例：

void RotateL(Node* parent)//左单旋
{Node* subR = parent->_right;//右子树Node* subRL = subR->_left;//右子树的左子树Node* ppNode = parent->_parent;//当前根节点的父亲//将当前根节点和左树压到subR的左树，并把原来subR的左树变成当前根节点的右树subR->_left = parent;parent->_parent = subR;//维护三叉链关系parent->_right = subRL;if(subRL)subRL->_parent = parent;//维护三叉链关系//如果当前根节点就是整棵树的根，要把_root也重新指向subRif (_root == parent){_root = subR;subR->_parent = nullptr;}else//当前根节点也只是个子树，就不需要重新指向_root{if (ppNode->_left == parent)//如果本来的根节点在它父亲的左边ppNode->_left = subR;//就让subR到左边else//如果本来的根节点在它父亲的右边ppNode->_right = subR;//就让subR到右边subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;//旋转后即平衡，这两个节点的平衡因子都变成0了
}

右单旋：

在进行如下插入节点后，parent的平衡因子变为2，此时就要进行旋转。

和左单旋时的思路差不多，就是把subL的右树放到parent的做左树，并把parent放到subL的右树

同样也别忘了维护三叉链关系

右单旋代码示例：

void RotateR(Node* parent)//右单旋
{Node* subL = parent->_left;//当前根节点的左子树Node* subLR = subL->_right;//当前根节点的左子树的右子树Node* ppNode = parent->_parent;//当前根节点的父亲//将当前根节点和右树压到subL的右子树，并将原来subL的左树变成当前根节点的左树subL->_right = parent;parent->_parent = subL;//维护三叉链关系parent->_left = subLR;if (subLR)subLR->_parent = parent;//维护三叉链关系//如果当前根节点就是整个树的根，就需要把_root重新置成subLif (_root == parent){_root = subL;subL->_parent = nullptr;}else//如果当前根节点也只是一个子树，就不用改_root{if (ppNode->_left == parent)//如果原来的根节点在父亲的左边ppNode->_left = subL;//就让subL去左边else//如果原来的根节点在父亲的右边ppNode->_right = subL;//就让subL去右边subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;//旋转完后即平衡，这两个节点的平衡因子都为0
}

双旋：

当右边或左边单独高时，是左单旋和右单旋两种情况，但除此之外还有其他情况

右左双旋：

上图是需要左单旋的两种情况，但如果新增节点不在subR->_right上，而在subRL上呢？

此时，就不是单一的右边高了。而是整体右边高，但对于subR来说是左边高

此时，需要先对subR这棵树进行右单旋，再对parent这棵树进行左单旋

不管新增节点在subRL的左还是右，都是一样的逻辑：subRL作子树的根，parent作subRL的左树，subR作subRL的右树

判断是否是要进行双旋，就可以看它的旋转曲线是直线还是折线

唯一不同的是双旋后的平衡因子

在单旋中，旋转结束后parent和subR的bf都会变成0。而在双旋中，要取决于新增节点在subRL的哪一边

如上图所示，若新增节点在c中， b的高度就是h-1，那parent的bf就会为-1；若新增节点在b中，c的高度就是h-1，那subR的bf就会为1

那怎么判断新增节点在c还是b中呢？可以看subRL的平衡因子，当subRL的平衡因子为1时，就代表新增节点在右边，为-1时，就代表新增节点在左边

双旋除了上面两种情况，其实还有第三种情况

也就是a,b,c,d都为空树的情况，此时也需要右左双旋，步骤和之前一样

可以看到，在双旋完成后，三个节点的平衡因子都变为了0，而这是在subRL的平衡因子为0的条件下

也就是说，在双旋中，subRL的平衡因子有-1,0,1三种情况，分别对应subR的bf为1，三者bf都为0，parent的bf为-1的情况

右左双旋代码示例：

void RotateRL(Node* parent)//右左双旋
{Node* subR = parent->_right;//当前根节点的右子树Node* subRL = subR->_left;//当前根节点的右子树的左子树int bf = subRL->_bf;//用来判断哪个节点的bf需要修改为1或-1RotateR(subR);//先右单旋，在左单旋RotateL(parent);if (bf == -1)//如果subRL的bf为-1，那短的一边就在subRL的右边，双旋完后就会在subR的左边{parent->_bf = 0;subR->_bf = 1;}else if (bf == 1)//如果subRL的bf为1，那短的一边就在subRL的左边，双旋完后就会在parent的右边{parent->_bf = -1;subR->_bf = 0;}else//还有subRL->_bf == 0的情况，即只有三个节点，因此平衡因子都为0{parent->_bf = subR->_bf = 0;}subRL->_bf = 0;//不管bf是多少，subRL最后会变为当前树的根，平衡因子为0
}

左右双旋：

右单旋是不管对于parent还是subL，都是左边高的情况

既然右左双旋是整体右边高，但对于左边来说左边高的情况，那左右双旋就是整体左边高，但对于右边来说右边高的情况

可以看到，当subLR的bf为1时，旋转完后subL的bf变为了-1；当subLR的bf为-1时，旋转完后的parent的bf变为了1。subLR作了子树的根，subL作了左子树，parent作了右子树

和右左双旋时一样，旋转曲线也是折线

对于左右双旋，更通用的旋转模板如下：

根据旋转的结果，可以总结出规律：左右双旋后，subLR作子树的根，subL作左子树，parent作右子树；b作subL的右子树，c作parent的左子树。

所以，如果新增节点在b上，c的高度就是h-1，parent的bf就是1；如果新增节点在c上，b的高度就是h-1，subL的bf就是-1。

和右左双旋一样，左右双旋也有第三种情况

如上图所示，当a,b,c,d均为空树时，也需要右左双旋，且旋转完后的平衡因子都为0

左右双旋代码示例：

void RotateLR(Node* parent)//左右双旋
{Node* subL = parent->_left;//当前根节点的左子树Node* subLR = subL->_right;//当前根节点的左子树的右子树int bf = subLR->_bf;//用来判断双旋后哪个节点的平衡因子是1或-1RotateL(subL);//先左单旋，再右单旋RotateR(parent);if (bf == -1)//如果bf为-1，就代表短的那边在subLR的右边，旋转完后到了parent的左边{parent->_bf = 1;subL->_bf = 0;}else if (bf == 1)//如果bf为1，就代表短的那边在subLR的左边，旋转完后到了subL的右边{parent->_bf = 0;subL->_bf = -1;}else//当bf为0时，就代表只有三个节点，所以平衡因子都为0{parent->_bf = subL->_bf = 0;}subLR->_bf = 0;//不管subLR->_bf为多少，subLR旋转后变为了子树的根，平衡因子为0
}

erase(了解)

AVL树的删除除了需要写单纯的二叉搜索树的删除之外，还需要考虑平衡因子的更新

二叉搜索树的删除分为四种情况：(设删除节点为cur,父亲为parent)

当cur的左树为空，右树不为空时，parent->_right/_left = cur->_right
当cur的左树不为空，右树为空时，parent->_right/_left = cur->_left
当cur的左右树都不为空时，可以选用cur右树的最左节点或cur左树的最右节点，来和cur替换，演变成删除左/右子树的最右/左节点
当cur的左右树都为空时，直接将parent置空即可(该情况可以被划分到1或2)

而AVL树除了要进行上面的操作，还需要更新平衡因子

若要删除的节点在parent的右边，parent的bf需要--;若要删除的节点在parent的左边，parent的bf需要++。(和插入节点时相反)

拿上图的情况举例，7的bf被更新为了0，代表7之前是±1，变为了0，即高度发生了改变，因此需要向上调整

5的bf被改为了-1，代表5之前是0，变为了-1，那代表一边高一边低，整体高度还是高的那边，因此高度没有发生变化，停止更新

但若bf变为了±2，和插入节点时一样，需要旋转了。不过旋转完后仍需向上调整，因为旋转完后该子树的根的bf变为了0，代表高度发生了改变。

通过上述规律，可以总结出：

当bf被改为了0，代表高度发生了改变，需要向上调整；
当bf被改为了±1，代表高度没用发生改变，无需向上调整；
当bf被改为了±2，代表此时不平衡，需旋转，旋转完后继续向上调整

Erase函数仅作为了解即可，这里就不放示例代码了

验证AVL树是否正确

这里给读者提供一下用来验证AVL树是否正确的函数

void InOrder()//中序遍历
{_InOrder(_root);
}void _InOrder(Node* root)//中序遍历的子函数(否则调用不到_root)
{if (root == nullptr)return;_InOrder(root->_left);cout << "key:" << root->_kv.first << '\t' << "value:" << root->_kv.second << '\n';_InOrder(root->_right);
}bool IsBalance()//判断二叉树是否平衡
{return _IsBalance(_root);
}bool _IsBalance(Node* root)//判断二叉树是否平衡的子函数(否则调用不到_root)
{if (root == nullptr)//如果是空树，那必然平衡return true;int leftHeight = _Height(root->_left);//求出左右子树的高度int rightHeight = _Height(root->_right);return abs(leftHeight - rightHeight) < 2//只要左右子树高度差小于2，并且左子树和右子树也平衡，那树就平衡&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}int _Height(Node* cur)//求二叉树的高度
{if (cur == nullptr)return 0;int leftHeight = _Height(cur->_left);int rightHeight = _Height(cur->_right);return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

以红黑树作为底层

先来复习一下红黑树

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

红黑树是怎么样实现其最长路径中节点个数不会超过最短路径节点个数的两倍的呢？

它会遵循下面的规则：

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

简化一点，即

根节点是黑色的
没有连续的红色节点
每条路径都有相同数量的黑色节点

那么最短的路径就是全黑的路径，最长的路径就是一黑一红(黑红各一半)的路径，因此两条路径的高度差最多是2倍，不可能超过2倍

因此，

当增删查改的节点在最短路径上时。时间复杂度为O(logN)

当增删查改的节点在最长路径上时，时间复杂度为2*O(logN)

所以总体的增删查改的时间复杂度为O(logN)

因此理论上而言，红黑树的效率比AVL树略差一点，但由于当今的硬件速度，它们之间已经基本没有差异了(logN和2*logN的速度对于CPU来说都差不多)

但在插入增删同样的节点的情况下，红黑树比AVL树旋转更少，因为AVL树更严格的平衡其实是通过多旋转达到的，所以实际上红黑树的应用比AVL更广泛

节点

在AVL树中，控制平衡是用的平衡因子(这只是其中一种方法)，而在红黑树中，近乎实现平衡用到了颜色，所以红黑树的节点和AVL树节点唯一的差异点就在平衡因子和颜色上，这里颜色可以用枚举(STL库中用的布尔值)

enum Color//红黑树的颜色
{RED,BLACK
};template<class K,class V>
struct RBTreeNode//红黑树的节点
{//三叉链RBTreeNode<K,V>* _left;RBTreeNode<K,V>* _right;RBTreeNode<K,V>* _parent;Color _col;//节点的颜色pair<K, V> _kv;//KV模型RBTreeNode(const pair<K,V>& kv)//默认构造函数:_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}
};

Insert

先来思考一个问题，对于新增的节点，颜色应该为黑色还是红色呢？

如果为黑色，就代表要破坏“每条路径都有相同数量的黑色节点“这条规则，因为在每条路径的黑色节点数量都相同的情况下，不管在哪条路径插入一个黑色节点，都会导致该路径的黑色节点+1

如果为红色，就代表要破坏“没有连续的红色节点”这条规则，因为可能它的父亲节点也是红色

而事实上，“没有连续的红色节点”这个规则更好调整。如果要调整“每条路径都有相同数量的黑色节点“这条规则，可能需要把每条路径都处理一遍

因此，这里选择节点的默认颜色为红色

违反“没有连续的红色节点”这条规则时，一共有三种情况，依情况来不同处理

第一种情况

cur，parent，uncle为红色，grandfather为黑色

此时，cur和parent都为红色节点，需要调整

将parent和uncle置黑，并将grandfather置红

这样可以保证每条路径在旋转完后还有相同的黑色节点数

此时，又有两条分支

如果grandfather就是这棵树的根，则需要将grandfather再置回黑，还是可以保证每条路径的黑节点个数相同

如果grandfather上面也有父亲(即这棵树只是整棵树的一棵子树)，就需要继续向上调整

将cur变成grandfather，再更新parent和grandfather

这种情况正好也是第一种情况，因此就还是重复操作(也有可能是第二种第三种情况)(如果grandfather上面还有，就需要继续向上调整)

顺便说一下，不管在左在右都是一样的

第二种情况

cur，parent为红，grandfather为黑，uncle不存在或为黑

为什么uncle为黑时，cur肯定不是新增节点呢？

若cur是新增节点，那就代表在未新增前是符合红黑树规则的，但从上图可以很明显看出不同路径中的黑色节点数量不同，因此uncle存在且为黑时cur不可能为新增节点

因此若uncle存在且为黑，那cur是由于子树的颜色改变而变为红色的

此时要想将parent置黑，那grandfather就必须置红，但grandfather可能是根节点，因此不能套用第一种方法

此时需要左单旋/右单旋，以上图的uncle不存在或uncle为黑的情况来说就是右单旋

单旋完后，再把grandfather置为红色，parent置为黑色

旋转完后就不需要再向上调整了

第三种情况

cur，parent为红，grandfather为黑，uncle不存在或存在且为黑

第三种情况的颜色和第二种完全一样，只不过第二种情况是单旋，而第三种情况是双旋

按上图的例子来看，就是左右双旋

双旋完后，将cur置黑，grandfather置红，和单旋时的情况一样，旋转完后也无需向上调整

Insert代码示例：

bool Insert(const pair<K, V>& kv)//红黑树的插入
{if (_root == nullptr)//如果当前是空树，就插入到根节点中{_root = new Node(kv);}else{Node* cur = _root;Node* parent = nullptr;while (cur)//找到要在哪里插入{if (kv.first > cur->_kv.first)//要插入的节点比当前节点大，就去右边{parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first)//要插入的节点比当前节点小，就去左边{parent = cur;cur = cur->_left;}else//如果相等，插入失败{return false;}}cur = new Node(kv);//为该kv开辟空间if (cur->_kv.first > parent->_kv.first)//在parent的右边{parent->_right = cur;cur->_parent = parent;}else//在parent的左边{parent->_left = cur;cur->_parent = parent;}//cur->_col = RED;//默认颜色为红色Node* grandfather = nullptr;Node* uncle = nullptr;while (parent && parent->_col == RED)//若父亲也是红色，此时需要调整{grandfather = parent->_parent;if (grandfather->_left == parent)//若父亲在祖父的左边{uncle = grandfather->_right;//那叔叔就在祖父的右边if (uncle && uncle->_col == RED)//如果叔叔为红色，就将parent和uncle置黑，grandfather置红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else//走到这里说明叔叔为黑色或不存在，就要旋转，要么左右双旋//要么右单旋，但就算是左右双旋，也是要执行一次左单旋一次右单旋，// 所以可以先判断是否需要左右双旋，如果需要，就先左单旋一次，// 这样即使是左右双旋的情况也可以转换成需要右单旋的情况{if (parent->_right == cur)//此时就要左右双旋(对于左边来说要左旋){RotateL(parent);//因为双旋的第一次单旋会让cur和parent调换//位置，所以先让parent和cur再换过来，之后再单旋就不会因为//之前单旋过一次而出问题了std::swap(cur, parent);}RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}else//若父亲在祖父的右边{uncle = grandfather->_left;//那叔叔就在祖父的左边if (uncle && uncle->_col == RED)//如果叔叔为红色，就将parent和uncle置黑，grandfather置红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else//走到这里说明叔叔为黑色或不存在，就要旋转，要么右左双旋//要么左单旋，但就算是右左双旋，也是要执行一次右单旋一次左单旋，//所以可以先判断是否需要右左双旋，如果需要，就先右单旋一次，//这样即使是右左双旋也可以转换成需要左单旋的情况{if (parent->_left == cur)//此时需要右左双旋(对于右边来说右边高){RotateR(parent);//因为双旋的第一次单旋会让cur和parent调换//位置，所以先让parent和cur再换过来，之后再单旋就不会因为//之前单旋过一次而出问题了std::swap(cur, parent);}RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}}}_root->_col = BLACK;//确保最后调整完根节点是黑色return true;
}

在处理第二、三种情况时，我把它们归为了一类处理，即使是双旋，只要先单旋一次，也会变成只需单旋一次的情况

但如果是双旋，绝对不能就这样结束

因此，如果是双旋，在第一次单旋后，需要交换一下parent和cur中所存的指针，即std::swap(parent,cur)

erase(了解)

红黑树的删除首先也和搜索树一样，如果要删除的节点左右子树都存在，则需替换节点，因此无论什么情况，最后要删除的那个节点左右至少有一个为空

如果删除的是红色节点，则没有任何影响

若该红色节点有左右子树，就先替换，再删那个左右至少有一个为空的节点

但如果删除的是黑色节点，再左右子树都有节点的情况下，如果没有黑色节点来代替它，就需要旋转

但如果有黑色节点来代替就无需旋转

想更具体的了解可以参考这篇文章

红黑树 - _Never_ - 博客园https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

验证红黑树是否正确

下面代码可以用于判断手搓的红黑树是否符合规则

bool IsValidRBTree()//判断红黑树是否正确
{Node* root = _root;// 空树也是红黑树if (root == nullptr)return true;// 检测根节点是否满足情况if (root->_col != BLACK){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;Node* cur = root;while (cur){if (BLACK == cur->_col)blackCount++;cur = cur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(root, k, blackCount);
}
bool _IsValidRBTree(Node* root, size_t k, const size_t blackCount)
{//走到null之后，判断k和black是否相等if (root == nullptr){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == root->_col)k++;// 检测当前节点与其双亲是否都为红色Node* parent = root->_parent;if (parent && RED == parent->_col && RED == root->_col){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(root->_left, k, blackCount) &&_IsValidRBTree(root->_right, k, blackCount);
}

AVL树和红黑树的效率比较

在平衡性上，AVL树比红黑树更严格，但AVL严格的平衡机制也导致了更多次的旋转，红黑树的平衡性没那么严格，因此旋转的次数更少

不过因为红黑树的平衡机制没那么严格，最短路径和最长路径可能分别为O(logN)和O(2*logN)，因此理论而言红黑树在增删查改的效率上会比AVL略逊一筹，但实际上呢？

void TestRB_AVLTree()//测试红黑树和AVL树的效率
{const int n = 1000000;//一百万个数据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;//红黑树插入一百万数据所需的毫秒int begin1 = clock();for (auto e : v)rbtree.Insert(make_pair(e,e));int end1 = clock();//AVL树插入一百万数据所需的毫秒int begin2 = clock();for (auto e : v)avltree.Insert(make_pair(e, e));int end2 = clock();cout << "RBTree:" << end1 - begin1 << endl;cout << "AVLTree:" << end2 - begin2 << endl;
}

输出结果：