首页 - 技术栈

建设银行怎么在网站设置限额从化电子商务网站建设

作者: 五速梦信息网
时间: 2026年04月20日 10:41

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

建设银行怎么在网站设置限额,从化电子商务网站建设,旅游网站模板手机,报告网站开发环境致努力前行的人#xff1a; 要努力#xff0c;但不要着急#xff0c;繁花锦簇#xff0c;硕果累累都需要过程#xff01; 目录 1.关联式容器 2.键值对 3.树形结构的关联式容器 3.1set的介绍 3.2set的使用 3.3multiset的使用 3.4map的使用 3.5multimap的使用 4.常见的面试题…致努力前行的人要努力但不要着急繁花锦簇硕果累累都需要过程目录 1.关联式容器 2.键值对 3.树形结构的关联式容器 3.1set的介绍 3.2set的使用 3.3multiset的使用 3.4map的使用 3.5multimap的使用 4.常见的面试题 5.底层结构 6.AVL树 6.1AVL树的概念 6.2AVL树节点的定义 6.3AVL树的插入 6.4AVL树的旋转 6.5AVL树的验证 6.6AVL树的性能 7.红黑树 7.1红黑树的概念编辑 7.2红黑树的性质 7.3红黑树结点的定义 7.4红黑树的插入操作 7.5红黑树的验证 7.6实例代码 7.8红黑树和AVL树的比较 8.红黑树模拟实现STL中的map和set 8.1STL中红黑树map和set结构搭建 8.2改造红黑树 8.3map的模拟实现 8.4set的模拟实现 1.关联式容器在之前我们已经接触过STL中的部分容器比如vector、list、deque等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 2.键值对用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。 3.树形结构的关联式容器根据应用场景的不同STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。 3.1set的介绍

set是按照一定次序存储元素的容器 2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。 3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。 5. set在底层是用二叉搜索树(红黑树)实现的。注意
与set/multiset不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。 4. 使用set的迭代器遍历set中的元素可以得到有序序列 5. set中的元素默认按照小于来比较 6. set中查找某个元素时间复杂度为log n7. set中的元素不允许修改. 8. set中的底层使用二叉搜索树(红黑树)来实现。 3.2set的使用 1.set的模板参数列表 T: set中存放元素的类型实际在底层存储value, value的键值对。Compareset中元素默认按照小于来比较Allocset中元素空间的管理方式使用STL提供的空间配置器管理 2.set的构造 set (const Compare comp Compare(), const Allocator Allocator() );构造空的setset (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() );用[first, last)区间中的元素构造setset ( const setKey,Compare,Allocator x); set的拷贝构造void Test() {setints; //构造空的setvectorintv;setints1(v.begin(), v.end());//迭代器区间的元素构造setsetints2(s);//拷贝构造 }
set的迭代器 iterator begin() 返回set中起始位置元素的迭代器iterator end() 返回set中最后一个元素后面的迭代器const_iterator cbegin() const返回set中起始位置元素的const迭代器const_iterator cend() const返回set中最后一个元素后面的const迭代器reverse_iterator rbegin() 返回set第一个元素的反向迭代器即endreverse_iterator rend()返回set最后一个元素下一个位置的反向迭代器即rbeginconst_reverse_iterator crbegin() const返回set第一个元素的反向const迭代器即cendconst_reverse_iterator crend() const返回set最后一个元素下一个位置的反向const迭代器即crbegin使用set的迭代器遍历set中的元素可以得到有序序列 void Test() {setint s;s.insert(3);s.insert(10);s.insert(4);s.insert(9);s.insert(7);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl; } 4.set的容量 bool empty ( ) const 检测set是否为空空返回true否则返回falsesize_type size() const 返回set中有效元素的个数5.set修改操作 pairiterator,bool insert (const value_type x )在set中插入元素x实际插入的是x, x构成的键值对如果插入成功返回该元素在set中的位置true,如果插入失败说明x在set中已经存在返回x在set中的位置falsevoid erase ( iterator position ) 删除set中position位置上的元素size_type erase ( const key_type x )删除set中值为x的元素返回删除的元素的个数void erase ( iterator first,iterator last )删除set中[first, last)区间中的元素void swap (setKey,Compare,Allocatorst );交换set中的元素void clear ( ) 将set中的元素清空iterator find ( const key_type x ) const返回set中值为x的元素的位置size_type count ( const key_type x ) const返回set中值为x的元素的个数 void Test() {setint s;//插入s.insert(3);s.insert(10);s.insert(4);s.insert(9);s.insert(7);//返回set中值为x的元素的位置setint::iterator ret s.find(3);//删除set中position位置上的元素s.erase(ret);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;cout s.count(10) endl; //返回set中值为10的元素的个数s.clear(); //将set中的元素清空 } 3.3multiset的使用
multiset是按照特定顺序存储元素的容器其中元素是可以重复的。 2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。 3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。 4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列。 5. multiset底层结构为二叉搜索树(红黑树)。注意
multiset中再底层中存储的是value, value的键值对 2. mtltiset的插入接口中只需要插入即可 3. 与set的区别是multiset中的元素可以重复set是中value是唯一的 4. 使用迭代器对multiset中的元素进行遍历可以得到有序的序列 5. multiset中的元素不能修改 6. 在multiset中找某个元素时间复杂度为log n7. multiset的作用可以对元素进行排序与set的区别是multiset中的元素可以重复set是中value是唯一的: void Test() {multisetint s;s.insert(3);s.insert(10);s.insert(10);s.insert(10);s.insert(10);s.insert(4);s.insert(9);s.insert(7);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;cout s.count(10) endl; } 3.4map的使用
map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中键值key通常用于排序和唯一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair:typedef pairconst key, T value_type;
在内部map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。
map支持下标访问符即在[]中放入key就可以找到与key对应的value。
map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 1.map的模板参数说明 key: 键值对中key的类型T 键值对中value的类型Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器 2.map的构造 map (const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 构造空的map template class InputIteratormap (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 用[first, last)区间中的元素构造map map (const map x); 拷贝构造void Test() {mapint, intm; //构造空的mapvectorintv;mapint, intm1(v.begin(), v.end()); //用[first, last)区间中的元素构造mapmapint, intm2(m1); //拷贝构造 } 3.map的迭代器 begin()和end()begin:首元素的位置end最后一个元素的下一个位置cbegin()和cend()与begin和end意义相同但cbegin和cend所指向的元素不能修改rbegin()和rend()反向迭代器rbegin在end位置rend在begin位置其和–操作与begin和end操作移动相反crbegin()和crend()与rbegin和rend位置相同操作相同但crbegin和crend所指向的元素不能修改void Test() {mapstring, stringdict;dict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(右边, right));//pairstring, string 等价于 make_pairdict.insert(make_pair(字符串, string));mapstring, string::iterator it dict.begin();while (it ! dict.end()){//cout (*it).first : (*it).second endl;cout it-first : it-second endl;it;}cout endl;for (const auto e : dict){cout e.first : e.second endl;}cout endl; } 4.map的容量与元素访问 bool empty ( ) const检测map中的元素是否为空是返回true否则返回falsesize_type size() const 返回map中有效元素的个数mapped_type operator返回去key对应的valuevoid Test() {mapstring, stringdict;dict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(右边, right));dict[insert]; //插入dict[insert] 插入; //修改dict[iterator] 迭代器; //插入修改cout dict[左边] endl; //key在就是查找 } 5.map中元素的修改 pairiterator,bool insert (const value_type x )在map中插入键值对x注意x是一个键值对返回值也是键值对iterator代表新插入元素的位置bool代表插入成功void erase ( iterator position ) 删除position位置上的元素size_type erase ( const key_type x )删除键值为x的元素void erase ( iterator first, iterator last )删除[first, last)区间中的元素void swap (mapKey,T,Compare,Allocatormp )交换两个map中的元素void clear ( ) 将map中的元素清空iterator find ( const key_type x)在map中插入key为x的元素找到返回该元素的位置的迭代器否则返回endconst_iterator find ( const key_type x ) const在map中插入key为x的元素找到返回该元素的位置的const迭代器否则返回cendsize_type count ( const key_type x ) const返回key为x的键值在map中的个数注意 map中key是唯一的因此该函数的返回值要么为0要么为1因此也可以用该函数来检测一个key是否在map中 void Test() {//统计水果出现的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, intcountMap;for (const auto e : arr){mapstring, int::iterator it countMap.find(e);if (it countMap.end()){countMap.insert(make_pair(e, 1));}else{it-second;}}for (const auto e : countMap){cout e.first : e.second endl;}cout endl; } 3.5multimap的使用
multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key,value其中多个键值对之间的key是可以重复的。 2. 在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起value_type是组合key和value的键值对:typedef pairconst Key, T value_type;3. 在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对key进行排序的。 4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。 5. multimap在底层用二叉搜索树(红黑树)来实现注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。 multimap中的接口可以参考map功能都是类似的。 void Test() {multimapstring, stringdict;dict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(右边, right));dict.insert(pairstring, string(右边, right));for (const auto e : dict){cout e.first : e.second endl;}cout endl; } 4.常见的面试题前K个高频单词实现思路定义一个map,然后将统计出现的字符串次数然后放到一个vectorpairint,string中按照降序的方式进行排序需要注意的是sort排序的时候是不稳定的所以当出现的次数相同的时候应该按照字典序的方式进行排序然后将前k的字符串放到vectorstring中返回 class Solution { public:struct Compare{bool operator()(const pairint, string left, const pairint, string right){return left.first right.first || (left.first right.first left.second right.second);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring, int countMap;for (const auto e : words){countMap[e];}vectorpairint, stringv;for (const auto e : countMap){v.push_back(make_pair(e.second, e.first));}sort(v.begin(), v.end(),Compare());vectorstringstr;for (size_t i 0; i k; i){str.push_back(v[i].second);}return str;} }; 两个数组出现的交集实现思路实现set排序加去重的特性如果两个数据相等就将数据加入到vectorint中否则就数据小的那个迭代器 class Solution { public:vectorint intersection(vectorint nums1, vectorint nums2){setints1(nums1.begin(), nums1.end());setints2(nums2.begin(), nums2.end());vectorintv;auto it1 s1.begin();auto it2 s2.begin();while (it1 ! s1.end() it2 ! s2.end()){if (*it1 *it2){v.push_back(*it1);it1;it2;}else if (*it1 it2)it2;elseit1;}return v;} }; 5.底层结构前面对map/multimap/set/multiset进行了简单的介绍这几个容器有个共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。 6.AVL树 6.1AVL树的概念二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。一棵AVL树或者是空树或者是具有以下性质的二叉搜索树它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在logn搜索时间复杂度O(log n)。一般规定平衡因子右子树的高度 - 左子树的高度 6.2AVL树节点的定义 templateclass K,class V struct AVLTreeNode {pairK, V_kv;AVLTreeNodeK, V _left; // 该节点的左孩子AVLTreeNodeK, V* _right; //该节点的右孩子AVLTreeNodeK, V* _parent; // 该节点的双亲int _bf; //balance fectorAVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} }; 6.3AVL树的插入 AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点2. 调整节点的平衡因子更新完之后是否继续更新判断标准 1.parent-_bf 0,说明之前parent-_bf是1或者是-1也就是说parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新 2、parent-_bf 1 或 -1 说明之前是parent-_bf 0两边一样高现在插入一边更高了parent所在子树高度变了继续往上更新 3、parent-_bf 2 或 -2说明之前parent-_bf 1 或者 -1现在插入严重不平衡违反规则需要做旋转处理旋转后需要达成的目标 1.让这颗子树的左右高度不超过1 2.旋转完之后继续保持是二叉搜索树 3.更新调整孩子结点的平衡因子 4.让这颗子树的高度跟插入前保持一致 6.4AVL树的旋转 AVL树的旋转分为四种 6.5AVL树的验证 AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步 1. 验证其为二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树 2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确 6.6AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log2 N。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。实例代码 templateclass K, class V class AVLTree {typedef AVLTreeNodeK, V Node; public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}else{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){if (parent-_left cur){parent-_bf–;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -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){RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}}return true;}void Inorder(){_Inorder(_root);}bool IsBalance(){return _IsBalance(_root);} private:bool _IsBalance(Node* root){if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){return false;}return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}int Height(Node* root){if (root nullptr)return 0;int lh Height(root-_left);int rh Height(root-_right);return lh rh ? lh 1 : rh 1;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}parent-_bf subR-_bf 0;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (ppNode nullptr){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}parent-_bf subL-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);//subLR的左子树新增if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}//subLR的右子树新增else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}//subLR自己本身就是新增else if(bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);//subRL的右子树新增if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}//subLR的左子树新增else if (bf -1){subRL-_bf 0;subR-_bf 1;parent-_bf 0;}//subRL自己本身就是新增else if (bf 0){subRL-_bf 0;subR-_bf 0;parent-_bf 0;}else{assert(false);}} private:void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}private:Node* _root nullptr; }; 7.红黑树 7.1红黑树的概念红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。如图所示 7.2红黑树的性质 1.每个结点不是红色就是黑色 2.根节点是黑色的 3.如果一个结点是红色的则它的两个孩子结点是黑色的没有连续的红色结点
对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每条路径上都包含相同数量的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 7.3红黑树结点的定义 //结点的颜色 enum Color {RED,BLACK }; templateclass K,class V struct RBTreeNode {pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {} }; 7.4红黑树的插入操作红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
按照二叉搜索的树规则插入新节点
检测新节点插入后红黑树的性质是否造到破坏因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点情况一: cur为红p为红g为黑u存在且为红解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。如图所示情况二: cur为红p为红g为黑u不存在/u存在且为黑解决方式p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色–p变黑g变红如图所示情况三: cur为红p为红g为黑u不存在/u存在且为黑解决方式p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转则转换成了情况2双旋转如图所示 7.5红黑树的验证红黑树的检测分为两步1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质 7.6实例代码 //结点的颜色 enum Color {RED,BLACK }; templateclass K,class V struct RBTreeNode {pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {} };templateclass K,class V class RBTree {typedef RBTreeNodeK, V Node; public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;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 (grandfather nullptr)break;if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent grandfather-_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;parent grandfather-_parent;cur grandfather;}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 true;}void Inorder(){_Inorder(_root);}bool IsBalance(){if (_root nullptr)return false;//判断根节点if (_root-_col ! BLACK)return false;//获取任意路径上黑色节点的数量int ref 0;Node* left _root;while (left){if (left-_col BLACK)ref;left left-_left;}return CheckRBTree(_root, 0, ref);} private:bool CheckRBTree(Node* root, int blackNum, int ref){if (root nullptr){if (blackNum ! ref){cout 违反规则本条路径上黑色结点的数量和最左路径上的不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续的红色结点 endl;return false;}if (root-_col BLACK){blackNum;}return CheckRBTree(root-_left, blackNum, ref) CheckRBTree(root-_right, blackNum, ref);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_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;Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (ppNode nullptr){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);} private:Node* _root nullptr; }; 7.8红黑树和AVL树的比较红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是Olog2 N红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 8.红黑树模拟实现STL中的map和set 8.1STL中红黑树map和set结构搭建 8.2改造红黑树 enum Color {RED,BLACK }; templateclass T struct RBTreeNode {T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Color _col;RBTreeNode(const T val):_data(val), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {} }; templateclass T,class Ref,class Ptr struct __RBTreeIterator {typedef RBTreeNodeT Node;typedef __RBTreeIteratorT,Ref,Ptr Self;typedef RBTreeIteratorT, T, T* iterator;Node* _node;RBTreeIterator(Node* node):_node(node) {}//普通迭代器的时候是拷贝构造//const迭代器的时候是构造用普通迭代器构造const迭代器__RBTreeIterator(const iterator s):_node(s._node){}Ref operator(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_right){Node min _node-_right;while (min-_left){min min-_left;}_node min;}else{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return this;}Self operator–(){if (_node-_left){Node max _node-_left;while (max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur 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;} }; templateclass K,class T,class KeyOfT class RBTree {typedef RBTreeNodeT Node; public:typedef __RBTreeIteratorT,T,T iterator;typedef __RBTreeIteratorT, const T, const T* const_iterator;iterator begin(){Node* left _root;while (left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}iterator begin() const{Node* left _root;while (left-_left){left left-_left;}return iterator(left);}iterator end() const{return iterator(nullptr);}pairiterator,bool Insert(const T data){if (_root nullptr){_root new Node(data);return make_pair(iterator(_root), true);}KeyOfT kot;Node* cur _root;Node* parent nullptr;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(iterator(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 (grandfather nullptr)break;if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent grandfather-_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;parent grandfather-_parent;cur grandfather;}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(iterator(newNode), true);}void Inorder(){_Inorder(_root);}bool IsBalance(){if (_root nullptr)return false;//判断根节点if (_root-_col ! BLACK)return false;//获取任意路径上黑色节点的数量int ref 0;Node* left _root;while (left){if (left-_col BLACK)ref;left left-_left;}return CheckRBTree(_root, 0, ref);} private:bool CheckRBTree(Node* root, int blackNum, int ref){if (root nullptr){if (blackNum ! ref){cout 违反规则本条路径上黑色结点的数量和最左路径上的不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续的红色结点 endl;return false;}if (root-_col BLACK){blackNum;}return CheckRBTree(root-_left, blackNum, ref) CheckRBTree(root-_right, blackNum, ref);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_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;Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (ppNode nullptr){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);} private:Node* _root nullptr; }; 8.3map的模拟实现 namespace ns {templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pairiterator, bool insert(const pairK, V kv){return _t.Insert(kv);}V operator{pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K, V, MapKeyOfT _t;}; 8.4set的模拟实现 namespace ns {templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator,bool insert(const K key){pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key);return pairiterator, bool(ret.first, ret.second);}private:RBTreeK, K, SetKeyOfT _t;};