创意产品设计及介绍,qq关键词排名优化,为什么淘宝店主不自己做电商网站,海外产品网站建设[本节目标] map和set底层结构 AVL树 红黑树 红黑树模拟实现STL中的map和set 1.底层结构
前面对map/multimap/set/multiset进行了简单的介绍#xff0c;在其文档介绍中发现#xff0c;这几个容器有个 共同点是#xff1a;其底层都是按照二叉搜索树来实现的#xff0c;但…[本节目标] map和set底层结构 AVL树 红黑树 红黑树模拟实现STL中的map和set 1.底层结构
前面对map/multimap/set/multiset进行了简单的介绍在其文档介绍中发现这几个容器有个 共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中 插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。
2.AVL树
2.1 AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年
发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均 搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树 左右子树高度之差(简称平衡因子(右子树高度-左子树高度))的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 $O(log_2 n)$搜索时间复杂度O($log_2 n$)。这里提一个问题为什么高度差要不超过1为什么不能是0这样树更平衡呀虽然这样的树更平衡但是条件太苛刻了如果我们插入的结点个数为2那么就做不到相等了最优就是高度差为1。
2.2 AVL树节点的定义
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;//balance factorpairK, V _kv;AVLTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv){}
};
2.3 AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步 1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子
我们先来看一下新插入的节点会影响那些节点的平衡因子呢新增节点的部分祖先节点 下面我们再来看一下平衡因子的更新规则。 现在我们就按照上面的规则写一下AVL树插入的代码先来画一下插入的三种情况的平衡因子图 直接上手代码
bool Insert(const pairK, V kv)
{//1. 先按照二叉搜索树的规则将节点插入到AVL树中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为空cur new Node(kv);if (parent-_kv.first kv.first)//要插入的值比当前值大{parent-_right cur;}else//要插入的值比当前值小{parent-_left cur;}cur-_parent parent;//2. 新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子并检测是否\破坏了AVL树的平衡性/*cur插入后parent的平衡因子一定需要调整在插入之前parent的平衡因子分为三种情况-10, 1, 分以下两种情况1. 如果cur插入到parent的左侧只需给parent的平衡因子-1即可2. 如果cur插入到parent的右侧只需给parent的平衡因子1即可此时parent的平衡因子可能有三种情况0正负1 正负21. 如果parent的平衡因子为0说明插入之前parent的平衡因子为正负1插入后被调整成0此时满足AVL树的性质插入成功2. 如果parent的平衡因子为正负1说明插入前parent的平衡因子一定为0插入后被更新成正负1此时以parent为根的树的高度增加需要继续向上更新3. 如果parent的平衡因子为正负2则parent的平衡因子违反平衡树的性质需要对其进行旋转处理*/while (parent){// 更新双亲的平衡因子if (parent-_left cur){parent-_bf--;}else{parent-_bf;}// 更新后检测双亲的平衡因子if (parent-_bf 0)//满足AVL树的性质{break;}else if(parent-_bf -1 || parent-_bf 1){// 插入前双亲的平衡因子是0插入后双亲的平衡因为为1 或者 -1 // 说明以双亲为根的二叉树的高度增加了一层因此需要继续向上调整cur cur-_parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2){//双亲的平衡因子为正负2违反了AVL树的平衡性// 需要对以pParent为根的树进行旋转处理}else{//插入之前AVL树就存在问题assert(false);}}return true;
}
2.4 AVL树的旋转
旋转的目的 1.保持搜索规则2、当前树从不平衡旋转为平衡3、降低当前树的高度 如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构 使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
1. 新节点插入较高右子树的右侧---右右左单旋 上面这个图是我们的抽象图a/b/c分别是高度为h的AVL子树我们来画一下具象图方便理解。 所以现在我们就理解上面的抽象图了我们可以发现一个规律经过旋转之后的的树的高度恢复到插入之前树的高度了所以此时我们不需要对上层的bf进行调整当进行旋转之后我们直接退出循环即可。 按照上面的图我们就可以直接开始写我们的代码了。
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;
}
我们来看看此时的代码是否存在问题上面的写法虽然将我们的树进行左旋了但是此时我们的树结构时三叉连还存储了parent所以我们这里需要更新一下每个节点parent。
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subRL-_parent parent;subR-_left parent;parent-_parent subR;
}
我们再来看看我们的代码有没有什么问题呢首先我们这里的parent和subR不可能为空因为此时的平衡因子是2才进入了这个函数但是这里的subRL为不为空我们就不清楚了所以我们就需要对subRL不为空才执行parent的更新。
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL ! nullptr)subRL-_parent parent;subR-_left parent;parent-_parent subR;
}
此时我们的代码还有问题嘛刚开始我们的根节点是parent但是此时我们的根节点是subR但是按照上面的程序此时的subR的_parent依然指向parent所以此时我们就要更新subR的_parent如果传入的praent就是根节点那么让subR变成我们的根节点如果传入的是子树那么还要与父节点进行链接所以一开始我们就要保存parent的父节点ppnode然后判断parent是ppnode的左还是右进行判断。 void RotateL(Node* parent)
{Node* ppnode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL ! nullptr)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}
}
此时我们的程序还有问题嘛有我们还没有更新我们的平衡因子。
void RotateL(Node* parent)
{Node* ppnode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL ! nullptr)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}//更新平衡因子parent-_bf 0;subR-_bf 0;
}
2.新节点插入较高左子树的左侧---左左右单旋
有了上面的左单旋我们这里的右单旋就很好写啦 //右单旋
void RotateR(Node* parent)
{Node* ppnode parent-_parent;Node* subL parent-_left;Node * subLR subL-_right;parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}//更新平衡因子parent-_bf 0;subL-_bf 0;
}
3. 新节点插入较高左子树的右侧---左右先左单旋再右单旋 基于上面的情况此时我们仅仅使用单旋是不能解决的此时需将b拆成60b子树c子树然后再先左单旋再右单旋解决。 此时我们再来画一下具象图理解一下。 通过上面的具象图我们就可以总结左右双旋的规则 //左右双旋
void RotateLR(Node* parent)
{RotateL(parent-_left);RotateL(parent);
}
其实对于这里的旋转其实比较简单但是对于平衡因子的更新比较麻烦。 观察上面的图我们发现可以分为三种情况区分这三种情况我们利用查看插入之前60的平衡因子进行判断.
//左右双旋
void RotateLR(Node* parent)
{//平衡因子调整 - 单旋会修改平衡因子//查看插入之后的平衡因子进行判断Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if(bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}
}
4. 新节点插入较高右子树的左侧---右左先右单旋再左单旋 有了上面的左右双旋这里的右左双旋就轻松多了我们直接来看平衡因子的调整 根据上面的平衡因子的调整关系我们就可以写我们的代码了。
//右左双旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){subRL-_bf 0;subR-_bf 0;parent-_bf -1;}else if (bf -1){subRL-_bf 0;subR-_bf 1;parent-_bf 0;}else if (bf 0){subRL-_bf 0;subR-_bf 0;parent-_bf 0;}else{assert(false);}
}
总结
假如以parent为根的子树不平衡即parent的平衡因子为2或者-2分以下情况考虑
1. parent的平衡因子为2说明parent的右子树高设parent的右子树的根为subR
当subR的平衡因子为1时执行左单旋当subR的平衡因子为-1时执行右左双旋
2. parent的平衡因子为-2说明parent的左子树高设parent的左子树的根为subL
当subL的平衡因子为-1是执行右单旋当subL的平衡因子为1时执行左右双旋
旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新。
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){//1. 先按照二叉搜索树的规则将节点插入到AVL树中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为空cur new Node(kv);if (parent-_kv.first kv.first)//要插入的值比当前值大{parent-_right cur;}else//要插入的值比当前值小{parent-_left cur;}cur-_parent parent;//2. 新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子并检测是否\破坏了AVL树的平衡性while (parent){// 更新双亲的平衡因子if (parent-_left cur){parent-_bf--;}else{parent-_bf;}// 更新后检测双亲的平衡因子if (parent-_bf 0)//满足AVL树的性质{break;}else if(parent-_bf -1 || parent-_bf 1){// 插入前双亲的平衡因子是0插入后双亲的平衡因为为1 或者 -1 // 说明以双亲为根的二叉树的高度增加了一层因此需要继续向上调整cur cur-_parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2){//双亲的平衡因子为正负2违反了AVL树的平衡性// 需要对以pParent为根的树进行旋转处理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)//左右双旋{RotateLR(parent);}else{RotateRL(parent);}break;}else{//插入之前AVL树就存在问题assert(false);}}return true;}
private: Node* _root nullptr;
};
2.5 AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
验证其为二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树
所以我们可以再写一个中序遍历的代码来验证是否有序。
void _InOder(Node* root)
{if (root nullptr)return;_InOder(root-_left);cout root-_kv.first ;_InOder(root-_right);
}void InOder()
{_InOder(_root);
}
再来写一个测试的代码
void TestAVLTree1()
{int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint,int t;for (auto e : a){t.Insert(make_pair(e,e));}t.InOder();
}
运行结果 从运行结果来看此时我们的程序是有序的说明此时的树是搜索二叉树但是此时的树不一定是AVL树因为有序只是AVL树的特点之一而且此时我们还不知道树的形状不能根据平衡因子判定是否是AVL树这里我们可以通过监视窗口先看根节点是谁然后再看左子树和右子树然后根据一层一层的看画出相应的树然后判断是不是AVL树但是比较麻烦我们这里能不能通过在中序遍历的时候同时打印出平衡因子去查看呢
这里其实是不能的因为这里的bf是靠我们自己的代码控制的有可能我们的代码写错了导致bf暂时没有出现问题从而导致我们对数进行错误判断成了AVL树。验证其为平衡树我们是求出左子树和右子树的高度如节点子树高度差的绝对值不超过1那么该树就是AVL树并且此时我们还能检查一下我们的平衡因子的正确性。
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;
}bool _IsBalance(Node* root)
{//root节点判断if(root nullptr)return true;int leftHeight Height(root-_left);//求左子树高度int rightHeight Height(root-_right);//求右子树高度if (abs(rightHeight - leftHeight 2)){//高度差异常return false;}if (rightHeight - leftHeight ! root-_bf){//平衡因子异常return false;}//root节点无异常//再判断root-_left和root-_right//如果左右子树都符合那么此时就是AVL树return _IsBalance(root-_left) _IsBalance(root-_right);
}bool IsBalance()
{return _IsBalance(_root);
}
然后我们再来测试一下
void TestAVLTree1()
{int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint,int t;for (auto e : a){t.Insert(make_pair(e,e));}t.InOder();if (t.IsBalance()){cout 当前树是AVL树 endl;}else{cout 当前树非AVL树 endl;}
}
我们上面的代码有没有优化的空间呢我们先来看一下上面的代码的缺陷我们上面在root验证AVL树的时候先是需要求出左树root-left和右树root-right的高度然后再判断当前节点root是否满足AVL树的特点由于我们求解高度是采用递归的写法在求解左树root-left高度之前我们还需要求解左树的root-left-left左子树和root-left-right右子树高度然后在我们判断root-left左树是否满足AVL树的特征时我们又要再去递归求出root-left-left左子树和root-left-right右子树高度这样就出现了大量的重复计算其实我们上面的写法是按照前序遍历的思路来写的这样写就会很亏。如果我们按照后序遍历的思路来写呢
bool _IsBalance(Node* root)
{if (root nullptr)return true;// 如果左右子树有一个不符合AVL就不是AVL树if (!_IsBalance(root-_left) || !_IsBalance(root-_right)){return false;}int leftHeight Height(root-_left);//求左子树高度int rightHeight Height(root-_right);//求右子树高度if (abs(rightHeight - leftHeight 2)){//高度差异常return false;}if (rightHeight - leftHeight ! root-_bf){//平衡因子异常return false;}return true;
}
但是其实效率并没有提高该重复计算的依然重复计算只不过和前序颠倒了一下顺序我们要清楚我们这里的出现的问题是在计算高度的时候出现了重复计算这源自于递归的写法所以我们可以不使用上面的递归的写法换另一种思路去解决我们依然使用后序遍历的思路然后本层判断完带回本层的树高度大的1给上一层上层就能直接求得本层的高度了。
bool _IsBalance(Node* root,int height)
{if (root nullptr){height 0;return true;}int leftHeight 0;int rightHeight 0;// 如果左右子树有一个不符合AVL就不是AVL树if (!_IsBalance(root-_left,leftHeight) || !_IsBalance(root-_right,rightHeight)){return false;}if (abs(rightHeight - leftHeight 2)){//高度差异常return false;}if (rightHeight - leftHeight ! root-_bf){//平衡因子异常return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;
}bool IsBalance()
{int height 0;return _IsBalance(_root,height);
}
我们来画一下递归图来理解一下 此时我们的来运行一下测试代码 如果未来我们不小心在写错了一个平衡因子的更新呢我们该怎么测试呢比如我们故意注释掉右左双旋的平衡因子更新看看程序此时会出现什么问题
void TestAVLTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint,int t;for (auto e : a){t.Insert(make_pair(e,e));}t.InOder();if (t.IsBalance()){cout 当前树是AVL树 endl;}else{cout 当前树非AVL树 endl;}
}
看看运行结果 此时这颗树就不是AVL树了但是我们不知道原因呀我们可以在出问题的地方加一些打印信息 此时我们再来看看输出结果。 此时上面显示的是6平衡因子异常那我们就能断定是插入6影响了当前AVL树的结构嘛这里是不能的因为有可能原本插入6都是满足的插入下一个值导致元素6左旋或者右旋不满足AVL树的结构了所以我们可以在每插入一个值后进行一次AVL判断。
void TestAVLTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint,int t;for (auto e : a){t.Insert(make_pair(e,e));cout e t.IsBalance() endl;} t.InOder();if (t.IsBalance()){cout 当前树是AVL树 endl;}else{cout 当前树非AVL树 endl;}
}
此时我们再来测试一下 此时我们可以看出是插入14的时候出现了问题此时教你们一招能让我们快速定位到问题点。 然后我们根据监视窗口画出插入14之前的AVL树。 总结 1、先看是插入谁导致出现的问题2、打条件断点r画出插入前的树3、单步跟踪对比图一 分析细节原因 不知道有没有仔细观看我们上面的测试的时候更换了一组测试用例原因是第一组的数据没有触发双旋的场景所以我们更换了一组测试数据所以建议用随机值来测试上面的程序。
void TestAVLTree2()
{const int N 1000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}if (t.IsBalance()){cout 当前树是AVL树 endl;}else{cout 当前树非AVL树 endl;}
}
我们再来测试一下AVL树的其他性能比如树的查找效率插入效率树的高度大小和节点个数
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);
}size_t Size()
{return _Size(_root);
}size_t _Size(Node* root)
{if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;
}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;
}然后我们来测试一下
void TestAVLTree3()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}size_t begin2 clock();AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}size_t end2 clock();cout Insert: end2 - begin2 endl;if (t.IsBalance()){cout 当前树是AVL树 endl;}else{cout 当前树非AVL树 endl;}cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl;
}
我们来测试一下结果 我们上面的代码不是产生了十万个节点嘛为什么这里的size大小是635238因为我们的插入逻辑是如果值相等就不插入了而我们产生了十万个节点当然存在重复值所以我们这里节点个数才会少一点我们上面查找的时候先查找了树中的每一个值然后再随机产生了十万个值进行查找显示结果是仅仅查找了19毫秒说明我们这里的查找效率极高我们可以看到这里的插入稍稍慢一点这里稍微差一点并不是在查找要插入位置的消耗上而是在创建节点的消耗了大量时间。
2.6 AVL树的删除(了解)
因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不 错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。
2.7 AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
3.红黑树
3.1 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出两倍假设最短路径是h最长路径是2h其他路径就是介于[h,2h]之间因而是接近平衡的。 3.2 红黑树的性质
1. 每个结点不是红色就是黑色2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点必须是黑色的 没有连续的红色节点4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
思考为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点 个数的两倍这里我们可以用极端场景分析根据上面的性质最短路径无非就是全黑最长路径就是一黑一红搭配此时最差情况下最长路径中节点个数才是最短路径节点个数的两倍。对比AVL树高度很是接近logN对于红黑树高度接近2*logN所以红黑树的搜索效率相对比AVL树差一点但是几乎可以忽略不计因为logN足够小差距很小但是插入同样的数据AVL树高度更低是通过更多旋转得到的。
注意这里的路径是根走到空节点而不是叶子节点。
3.3 红黑树节点的定义
// 节点的颜色
enum Colour
{RED,BLACK
};// 红黑树节点的定义
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};
思考在节点的定义中为什么要将节点的默认颜色给成红色的这里我们可以想象一下如果我们将插入的节点的默认颜色设置为黑色那么该条路径上的黑色节点就会增加一个为了满足对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点所以其他路径就必须增加要一个由红色变成黑色节点但是有时候我们插入的节点没有红色节点无法变色为黑色节点就比如下面场景插入一个值为1的黑色节点此时就不满足红黑树的特点。 3.4 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
1. 按照二叉搜索的树规则插入新节点2. 检测新节点插入后红黑树的性质是否造到破坏
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何 性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
情况一: cur为红p为红g为黑u存在且为红
p/u是g的左或者右都不影响cur是p的左或者右也不影响处理的方式都是一样的。 上面的抽象图我们还不是很理解我们这里来画一下具象图来好好好理解一下。
a/b/c/d/e都为空树情况 a/b的位置是红色的而c/d/e都是具有一一个黑色节点的红黑树(子树)的情况 解决方式将pu改为黑g改为红然后把g当成cur继续向上调整。
情况二: cur为红p为红g为黑u不存在/u存在且为黑 我们来画一下上面的具象图 u存在且为黑的时候再插入一个节点的时候我们会发现此时的已经违背规则了此时红黑树有一条路径会比其他路径长出两倍此时只能通过旋转解决。 解决方式p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色--p变黑g变红
情况三: cur为红p为红g为黑u不存在/u存在且为黑 我们来画一下上面的具象图 此时解决就需要双旋来解决 解决方式p为g的左孩子cur为p的右孩子则针对p做左单旋转再对g做右单旋转相反 p为g的右孩子cur为p的左孩子则针对p做右单旋转再对g做左单旋转。
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){//1. 先按照二叉搜索树的规则将节点插入到AVL树中if (_root nullptr){//第一个值直接插入//如果是_root颜色给成黑色_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为空cur new Node(kv);//默认新增节点是红色//此处可以不用写cur-_col RED;因为构造函数处已经控制好了if (parent-_kv.first kv.first)//要插入的值比当前值大{parent-_right cur;}else//要插入的值比当前值小{parent-_left cur;}cur-_parent parent;//如果parent的颜色是红色进入循环否则直接退出while (parent parent-_col RED){//这里不需要判断grandfather是存在//进入循环时cur为插入的时候此时树一定是红黑树//插入cur后cur为红parent为红此时parent不可能为根//那么grandfather一定存在且为黑Node* grandfather parent-_parent;if (parent grandfather-_left)//父亲是爷爷的左边{Node* uncle grandfather-_right;//叔叔存在且为红if (uncle uncle-_col RED){//父亲和叔叔都变黑爷爷变红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}//叔叔存在且为黑或者叔叔不存在else{/*g pp u c gc u*///右单旋 变色if(cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}/*g g cp u c u p gc p u*///p为旋转点进行左单旋g为旋转点进行右单旋else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}//此时parent为红色不能退出循环需要手动退出break;}}else{Node* uncle grandfather-_left;//叔叔存在且为红if (uncle uncle-_col RED){//父亲和叔叔都变黑爷爷变红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else{/*g pu p g cc u*///左单旋 变色if(cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}/*g g cu p u c g pc p u*///右单旋 左单旋 变色else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}//左单旋void RotateL(Node* parent){Node* ppnode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL ! nullptr)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}}//右单旋void RotateR(Node* parent){Node* ppnode parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}
private:Node* _root nullptr;
};3.5 红黑树的验证
红黑树的检测分为两步
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质
当我们要检查是否满足红黑树的性质的时候我们能不能直接求出最短路径和最长路径然后判断有没有超过2倍来判断一棵树是否是红黑树呢我们来看下这种图 我们可以看到上面的红黑树是是满足最长路径的长度是不超过最短路径长度的2倍但是上面的树依然违背了红黑树的性质不满足每条路径上的黑色节点个数相同所以我们就不能利用上面的规则判断一颗红黑树。其实我们能发现如果一棵树满足红黑树颜色的规则那么就能保证最长路径的长度是不超过最短路径长度的2倍所以我们根本不需要上面的规则直接判断颜色是否符合即可。 1.根是黑色的2.没有连续的红色节点3.每条路径上的黑色节点的数量相等 首先我们来解决第一条性质根是黑色的
bool IsBalance()
{if (_root _root-_col RED){cout 违反红黑树性质二根节点必须为黑色 endl;return false;}return Check(_root);
}
再来解决第二条性质没有连续的红色节点
bool Check(Node* root)
{//空树也是红黑树if (root nullptr)return true;//红色节点一定有父亲所以这里不需要判空if (root-_col RED root-_parent-_col RED){cout 违反性质三不在一起的红色节点 endl;return false;}return Check(root-_left) Check(root-_right);
}
我们这里是使用的前序遍历如果当前节点和父亲节点都是红色那么这里就违反规则。
再来解决第三条性质每条路径上的黑色节点的数量相等
先来看第一种思路来一个全局遍历path记录每条路径上的黑色节点的个数再来一个vector去存储每条路径上的黑色节点的个数然后遍历vector的所有元素是不是相同的
int path;//全局变量
vectorint v;//存储每条路径的黑色节点的个数
void _CountBlack(Node* root)
{if (root nullptr){v.push_back(path);return;}if (root-_col BLACK){path;}_CountBlack(root-_left);_CountBlack(root-_right);//恢复现场if (root-_col BLACK ){path--;}
}void CountBlack()
{_CountBlack(_root);for (auto e : v){cout e ;}cout endl;v.resize(0);path 0;
}
我们可以来一组数据测试上面的性质3
void TestRBTree1()
{int a[] { 13, 8, 17,1,11,15,25,6,22,27 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOder(); cout endl;t.CountBlack();t.CountBlack();
}
代码的运行结果 根据上面的代码所构建的红黑树我们发现节点数量是符合的。 由于我们这里使用的全局变量为了下次的调用需要每次将path和vector清空这样才不会影响下次调用。但是上面全局变量最好不要用它会影响我们的线程安全所以我们这里换一种思路先随便求一条路径的黑色节点的个数作为基准值利用前序递归求出每条路径的黑色节点的个数我们这里可以直接将每层的黑色节点传参待它返回上一层自动清理现场就不需要单独处理了当节点为空的时候就可以直接比较黑色节点个数和我们基准值是否相同。
bool Check(Node* cur, int blackNum, int refBlackNum)
{//空树也是红黑树if (cur nullptr){if (refBlackNum ! blackNum){cout 违反性质四每条路径中黑色节点的个数必须相同 endl;return false;}//cout blackNum endl;return true;}//红色节点一定有父亲所以这里不需要判空if (cur-_col RED cur-_parent-_col RED){cout 违反红黑树性质二根节点必须为黑色 endl;return false;}if (cur-_col BLACK)blackNum;return Check(cur-_left, blackNum, refBlackNum) Check(cur-_right, blackNum, refBlackNum);
}bool IsBalance()
{if (_root _root-_col RED){cout 违反红黑树性质二根节点必须为黑色 endl;return false;}int refBlackNum 0;//基准值Node* cur _root;while (cur){if (cur-_col BLACK)refBlackNum;cur cur-_left;}return Check(_root, 0, refBlackNum);
}
然后我们来测试一下
void TestRBTree1()
{int a[] { 13,8,17,1,11,15,25,6,22,27 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOder();if (t.IsBalance()){cout 当前树是红黑树 endl;}else{cout 当前树非红黑树 endl;}
}
为了观看每个节点的颜色是否符合上面的红黑树图我们中序遍历的时候输出一下节点的颜色
void _InOder(Node* root)
{if (root nullptr)return;_InOder(root-_left);cout root-_kv.first : root-_col endl;_InOder(root-_right);
}void InOder()
{_InOder(_root);
}
现在我们再来测试一下 首先中序遍历为有序然后我们中序还打印了节点的颜色并且符合我们下面的红黑树。 然后我们再来测试一下其他功能
size_t Size()
{return _Size(_root);
}size_t _Size(Node* root)
{if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;
}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;
}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 TestRBLTree2()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}size_t begin2 clock();RBTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}size_t end2 clock();cout Insert: end2 - begin2 endl;if (t.IsBalance()){cout 当前树是红黑树 endl;}else{cout 当前树非红黑树 endl;}cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl;
}
再来看一下效果 此时的树的高度稍微比AVL树高一点这也符合我们之前的结论。
3.6 红黑树的删除
红黑树的删除本节不做讲解有兴趣的同学可参考《算法导论》或者《STL源码剖析》
红黑树 - _Never_ - 博客园 (cnblogs.com)
3.7 红黑树与AVL树的比较
我们这里来测试一下一百万个随机值的结果 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O($log_2 N$)红黑树不追 求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数 所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
4.红黑树模拟实现STL中的map和set
4.1 初建map和set的框架 为了同时支持map和set都能够使用红黑树作为底层实现原理所以我们这里需要给上模板去实现不同的容器set和map所以我们这里的实现比较的大小的逻辑就要修改对于set可以直接比较但是对于map的pair虽然支持比较但是我们期望比较的是first对于second不需要参与比较所以我们这里就单独写一个仿函数获取要比较的元素。 所以我们的红黑树结点的定义和插入逻辑的代码需要修改一下。
templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;T _data;RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED), _data(data){}
};// set-RBTreeK, K, SetKeyOfT
// map-RBTreeK, pairK,T, MapKeyOfT
//KeyOfT 仿函数取出T对象中的key
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:bool Insert(const T data){//1. 先按照二叉搜索树的规则将节点插入到AVL树中if (_root nullptr){//第一个值直接插入//如果是_root颜色给成黑色_root new Node(data);_root-_col BLACK;return true;}KeyOfT kot;Node* parent nullptr;Node* cur _root;while (cur){//如果data是key那可以直接比较//如果data是pair期待的是first进行比较//pair是支持比较大小的/*template class T1, class T2bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs){ return lhs.firstrhs.first || (!(rhs.firstlhs.first) lhs.secondrhs.second); }比较规则是:first小就小first不小second小就小但是我们期望的只是用first进行比较second不参与比较需要仿函数解决*/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 false;}}//此时_cur为空cur new Node(data);//默认新增节点是红色//此处可以不用写cur-_col RED;因为构造函数处已经控制好了if (kot(parent-_data) kot(data))//要插入的值比当前值大{parent-_right cur;}else//要插入的值比当前值小{parent-_left cur;}cur-_parent parent;//其他代码不用修改和之前一样}
private:Node* _root nullptr;
};
我们发现我们上面好像只用了第二个模板参数第一个模板参数好像根本就没有使用那我们能不能不要第一个模板参数呢后面迭代器讲解了我们再来解释。
4.2 红黑树的迭代器
迭代器的好处是可以方便遍历是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代 器需要考虑以前问题
operator和operator--
我们先来看一下我们这里迭代器的逻辑如何控制首先我们知道初始位置肯定是这棵树的最左节点那么下一个节点该如何寻找呢我们可以从对红黑树进行中序遍历后 可以得到一个有序的序列出发。 Self operator()
{if (_node-_right ! nullptr){//右子树的中序第一个(最左节点)Node* subLeft _node-_right;while (subLeft-_left ! nullptr){subLeft subLeft-_left;}_node subLeft;}else{//右为空//祖先里面孩子是父亲左的那个节点Node* cur _node;Node* parent _node-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;
} 我们这里的迭代器减减的逻辑和迭代器加加的逻辑完全相反但是由于我们上面给的end()的位置是空所以我们这里不能直接--end()只能自己再写一个代码去找到最后一个元素的迭代器再去减减或者也可以单独处理一下但是如果此时为空树我们需要再单独处理一下就比较麻烦。
Self operator--()
{//说明此时的位置是end()if (_node nullptr){//_node指向最后结点//唯一的问题就是空树也指向空}//和逻辑相反return *this;
}
库里面因为对end()位置的迭代器进行--操作必须要能找最后一个元素因此最好的方式是将end()放在头结点的右的位置使用一个带哨兵位的结点指向end() begin()与end()
STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后 可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点(最右侧节点)的下一个位置关键是最大节点的下一个位置在哪块我们这里先将end()设置为空按照我们上面的迭代器的逻辑当访问到这棵树的最右节点此时的树的当前结点cur始终都是parent的右按照此时右为空的逻辑那么最终parent就会走到空cur就会走到根节点此时_node也就为nullptr刚好给end()构造为空。
typedef RBTreeIteratorT iterator;iterator begin()
{//找最左节点Node* subLeft _root;while (subLeft ! nullptr subLeft-_left ! nullptr){subLeft subLeft-_left;}return iterator(subLeft);//构造
}iterator end()
{return iterator(nullptr);
}
我们再来完善一下迭代器的其他接口
templateclass T
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT Self;RBTreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_right ! nullptr){//右子树的中序第一个(最左节点)Node* subLeft _node-_right;while (subLeft-_left ! nullptr){subLeft subLeft-_left;}_node subLeft;}else{//右为空//祖先里面孩子是父亲左的那个节点Node* cur _node;Node* parent _node-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}bool operator!(const Self s){return _node ! s._node;}private:Node* _node;
};
如果我们要实现const迭代器呢只需要添加两个模板参数即可
templateclass T,class Ptr,class Ref
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT,Ptr,Ref Self;RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}
private:Node* _node;
};typedef RBTreeIteratorT,T*,T iterator;
typedef RBTreeIteratorT,const T*,const T const_iterator;const_iterator begin() const
{//找最左节点Node* subLeft _root;while (subLeft ! nullptr subLeft-_left ! nullptr){subLeft subLeft-_left;}return const_iterator(subLeft);//构造
}const_iterator end() const
{return const_iterator(nullptr);
}
4.3 完善set和map框架
#include RBTree.hnamespace yu
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public://typename告诉编译器这是一个类型而不是一个静态成员变量typedef typename RBTreeK, K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K key){return _t.Insert(key);}private:RBTreeK, K, SetKeyOfT _t;};void test_set1(){setint s;int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}}
}
然后我们来测试一下结果这里迭代器加加的逻辑是按照中序因此有序即可判断。 此时符合我们的预期那我们再来看下面的测试代码。
void test_set1()
{setint s;int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}setint::iterator it s.begin();while (it ! s.end()){if (*it % 2 0)*it 100;cout *it ;it;}
}
我们来看一下运行结果。 我们发现此时结果不是有序的此时也不是我们的红黑树这里的结点的值是不允许修改的我们可以在迭代器里面的*操作符重载加上const修饰表示不可被修改也可以通过传入模板第二个参数的时候传入const此时const相当于间接*操作符重载加上const。
namespace yu
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public://typename告诉编译器这是一个类型而不是一个静态成员变量typedef typename RBTreeK, const K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K key){return _t.Insert(key);}private:RBTreeK, const K, SetKeyOfT _t;};void test_set1(){setint s;int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}setint::iterator it s.begin();while (it ! s.end()){if (*it % 2 0)*it 100;cout *it ;it;}}
}
我们来看一下测试结果。 现在我们来解释一下第一个模板参数为什么需要的原因第二个模板参数只能通过我们的仿函数获取到相应的key并不能获取到这个key的类型当我们需要find的时候就需要参数的类型此时对于map和set所查找的都是key类型都是相同的。
iterator find(const K key)
{KeyOfT kot;Node* cur _root;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return iterator(cur);}}return iterator(nullptr);
}
我们再来一下map的框架
#include RBTree.hnamespace yu
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public://typename告诉编译器这是一个类型而不是一个静态成员变量typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pairK, V kv){return _t.Insert(kv);}iterator find(const K key){return _t.Find(key)}private:RBTreeK, pairconst K,V, MapKeyOfT _t;};void test_map1(){mapint,int m;int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){m.insert(make_pair(e,e));}mapint,int::iterator it m.begin();while (it ! m.end()){cout it-first : it-second ;it;}}
}
前面我们也学到过map是支持operator[]操作的所以我们这里还要实现一下我们前面学习过operator[]它是利用insert进行修改的所以我们这里修改一下insert。
pairiterator,bool Insert(const T data)
{//1. 先按照二叉搜索树的规则将节点插入到AVL树中if (_root nullptr){//第一个值直接插入//如果是_root颜色给成黑色_root new Node(data);_root-_col BLACK;return return make_pair(iterator(_root),true);}KeyOfT kot;Node* parent nullptr;Node* cur _root;while (cur){//如果data是key那可以直接比较//如果data是pair期待的是first进行比较//pair是支持比较大小的/*template class T1, class T2bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs){ return lhs.firstrhs.first || (!(rhs.firstlhs.first) lhs.secondrhs.second); }比较规则是:first小就小first不小second小就小但是我们期望的只是用first进行比较second不参与比较需要仿函数解决*/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 false;return return make_pair(iterator(cur), false);}}//此时_cur为空cur new Node(data);//默认新增节点是红色Node* temp cur;//此处可以不用写cur-_col RED;因为构造函数处已经控制好了if (kot(parent-_data) kot(data))//要插入的值比当前值大{parent-_right cur;}else//要插入的值比当前值小{parent-_left cur;}cur-_parent parent;//如果parent的颜色是红色进入循环否则直接退出while (parent parent-_col RED){//这里不需要判断grandfather是存在//进入循环时cur为插入的时候此时树一定是红黑树//插入cur后cur为红parent为红此时parent不可能为根//那么grandfather一定存在且为黑Node* grandfather parent-_parent;if (parent grandfather-_left)//父亲是爷爷的左边{Node* uncle grandfather-_right;//叔叔存在且为红if (uncle uncle-_col RED){//父亲和叔叔都变黑爷爷变红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}//叔叔存在且为黑或者叔叔不存在else{/*g pp u c gc u*///右单旋 变色if(cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}/*g g cp u c u p gc p u*///p为旋转点进行左单旋g为旋转点进行右单旋else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}//此时parent为红色不能退出循环需要手动退出break;}}else{Node* uncle grandfather-_left;//叔叔存在且为红if (uncle uncle-_col RED){//父亲和叔叔都变黑爷爷变红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else{/*g pu p g cc u*///左单旋 变色if(cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}/*g g cu p u c g pc p u*///右单旋 左单旋 变色else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;//return true;return make_pair(iterator(temp), true);
} 然后我们用代码测试一下
void test_map2()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}
}
看一下测试的结果
