3红黑树了解原理即可时间复杂度重点1规则1二叉搜索树左根右2 根结点和叶子节点是黑色,注意这里的叶子节点不是常规意义上的叶子节点,而是空节点根叶黑-也就是说红黑树的叶子结点是常规下叶子结点都再挂上两空结点那些空结点3,红色节点的左右孩子是黑色,也就是说任意一条路径中不会存在连续的红色节点不红红4,任意节点的叶子节点的路径上黑色节点数量相同黑路同2举个栗子N 空叶子节点默认黑色/验证是否为红黑树1左根右20 左边10, 5, 15 都小于 2020 右边30, 25, 40 都大于 2010 左边 5 10右边 15 1030 左边 25 30右边 40 30✔️2根叶黑根节点20叶子结点NULL都是黑色球球✔️3不红红这里只需要看红色节点的孩子必须是黑色那就可能有可爱的小朋友发问了父亲结点怎么办-假设法如果父节点红此节点红那么在检验父节点的时候是不是他的孩子就是红违背了规则然后就不是红黑树红色节点有10, 25, 40他们的孩子都是黑色球球✔️4黑路同注意1. 不是只从根节点看而是任意节点都要满足 2. 数的是黑色节点红色节点不计数那就来验证吧①从⚫20出发到每个NIL20 - 10 - 5 - NIL黑色节点20, 5, NIL共 3 个20 - 10 - 15 - NIL黑色节点20, 15, NIL共 3 个20 - 30 - 25 - NIL黑色节点20, 30, NIL共 3 个20 - 30 - 40 - NIL黑色节点20, 30, NIL共 3 个②再看节点⚫3030 - 25 - NIL黑色节点⚫30、NIL共 2 个30 - 40 - NIL黑色节点⚫30、NIL共 2 个③再看515 全部符合所以√所以-这是一棵红黑树3.性质最长路径不超过最短路径两倍这里的“路径长度”一般指实际节点数或边数不把空节点当作普通节点算进去给大家小小类比举例证明一下把一条路径看成一串珠子黑 必须有的珠子 红 可以插进去的珠子红黑树规定1. 每条路上的黑珠子数量一样 2. 红珠子不能连续所以最短黑 黑 黑 NIL 最长黑 红 黑 红 黑 红 NIL除去空结点​ 最短黑 黑 黑 最长黑 红 黑 红 黑 红 正好二倍 ​因为红色不能连着放所以每个黑色旁边最多插一个红色。因此最长路径 最短路径的 2 倍最长路径 最短路径的 2 倍可以推出要用数学归纳法证明很麻烦感兴趣的小朋友自己探寻吧我是不感兴趣的(●◡●)红黑树的树高 h 2log₂(n 1)算这个干嘛啊当然是为了时间复杂度哇~4时间复杂度O(logN)5,插入1步骤1按二叉搜索树方式插入新结点2默认该点为红色如果破坏了红黑树规则然后分情况调整那么就会可能有超级可爱的小朋友发问了~①为什么默认红色规则怪谈第4条法则黑路同假设默认黑色我们就直接违反了但红色就不会了②分情况调整是什么鬼嗯~ o(*▽*)o一起往下看吧2破坏规则后调整1,插入节点为根结点1方法直接变黑根叶黑2例子小插曲 节点叔叔就是父节点的兄弟嘛2,插入节点叔叔为红色1方法叔父爷变色爷爷变插入节点2例子插入前现在插入5因为叔叔30是红色-step 1叔父爷变色step 2 爷爷变插入节点也就是我们把爷爷结点重新审视为插入节点为根结点的情况3,插入节点叔叔为黑色1方法旋转LL,RR,LR,RL)然后变色旋转中心旋转点颜色交换2例子1LL型插入后⚫30 / \ 20 NIL / 10这是10 是 30 的左孩子的左孩子 LL 型先旋转对旋转点 30 右旋 旋转中心是 2020 / \ 10 ⚫30再变色旋转中心 20 和旋转点 30 颜色交换结果⚫20 / \ 10 302. RR 型插入后⚫10 \ 20 \ 30这是30 是 10 的右孩子的右孩子 RR 型先旋转对旋转点 10 左旋 旋转中心是 2020 / \ ⚫10 30再变色旋转中心 20 和旋转点 10 颜色交换结果⚫20 / \ 10 303. LR 型插入后⚫30 / 10 \ 20这是20 是 30 的左孩子的右孩子 LR 型先旋转先对 10 左旋 再对 30 右旋第一步对10左旋⚫30 / 20 / 10第二步对30右旋20 / \ 10 ⚫30再变色旋转中心 20 和旋转点 30 颜色交换结果⚫20 / \ 10 304. RL 型插入后⚫10 \ 30 / 20这是20 是 10 的右孩子的左孩子 RL 型先旋转先对 30 右旋 再对 10 左旋第一步对30右旋⚫10 \ 20 \ 30第二步对10左旋20 / \ ⚫10 30再变色旋转中心 20 和旋转点 10 颜色交换结果⚫20 / \ 10 304set/multiset1,区别set:不可存相同元素multiset:可存相同元素所以set可以用于去重操作又因为他们其他使用一样接下来只说set2set创建#includeset setint se;和栈队列一样3基本术语函数作用返回值时间复杂度记忆点size()查看set中元素个数元素数量O(1)有几个empty()判断set是否为空true / falseO(1)空不空begin()指向第一个元素迭代器O(1)最小值位置end()指向最后一个元素的后一个位置迭代器O(1)结束标记不是最后元素insert(x)插入元素x通常返回插入结果O(log N)加进去erase(x)删除元素x删除数量或迭代器相关O(log N)删掉它find(x)查找元素x迭代器O(log N)找位置count(x)判断元素x是否存在0或1O(log N)存不存在lower_bound(x)找第一个 x的元素迭代器O(log N)大于等于upper_bound(x)找第一个 x的元素迭代器O(log N)严格大于4代码示例#include iostream #include set using namespace std; int main() { setint s; // insert插入元素 s.insert(30); s.insert(10); s.insert(20); s.insert(40); s.insert(20); // set 自动去重 // size元素个数 cout size s.size() endl; // empty判断是否为空 cout empty s.empty() endl; // begin / end遍历 set cout set elements: ; for (auto it s.begin(); it ! s.end(); it) { cout *it ; } cout endl; // find查找元素返回迭代器 auto it s.find(20); if (it ! s.end()) { cout find 20: *it endl; } else { cout 20 not found endl; } // count判断元素是否存在 if (s.count(30)) { cout 30 exists endl; } else { cout 30 does not exist endl; } // lower_bound找第一个 x 的元素 auto it1 s.lower_bound(25); if (it1 ! s.end()) { cout lower_bound(25) *it1 endl; } else { cout no element 25 endl; } // upper_bound找第一个 x 的元素 auto it2 s.upper_bound(30); if (it2 ! s.end()) { cout upper_bound(30) *it2 endl; } else { cout no element 30 endl; } // erase删除元素 s.erase(20); cout after erase 20: ; for (auto x : s) { cout x ; } cout endl; return 0; }5map/multimap1,区别map通常是“映射”或“字典结构”用一个键找到一个值。key - valueset 是“集合”只关心某个元素是否存在不关心它对应什么值而且不允许重复。2map创建#include map #include string mapstring, int scores;3基本术语术语作用好记理解时间复杂度size()返回元素个数有几个键值对O(1)empty()判断是否为空有没有东西O(1)begin()返回第一个元素的迭代器从最小 key 开始O(1)end()返回最后一个元素后面的位置不是最后一个是“终点后面”O(1)insert()插入元素放入一组key - valueO(logN)operator[]通过 key 访问 value像数组一样用 mapO(logN)erase()删除元素按 key 删除O(logN)find()查找 key找到了返回位置找不到返回end()O(logN)count()判断 key 是否存在map中结果只会是0或1O(logN)lower_bound(x)找第一个key x的元素大于等于 x 的第一个O(logN)upper_bound(x)找第一个key x的元素严格大于 x 的第一个O(logN)//注意operator[]如果里面内容不存在可能会插入原本不想要的元素4代码示例#include iostream #include map #include string using namespace std; int main() { // 创建 mapkey 是 intvalue 是 string mapint, string mp; // 1. insert插入元素 mp.insert({3, three}); mp.insert({1, one}); mp.insert({5, five}); // 2. operator[]像数组一样插入或修改 mp[2] two; mp[3] THREE; // 修改 key 为 3 的 value // 3. size元素个数 cout size mp.size() endl; // 4. empty判断是否为空 if (mp.empty()) { cout map is empty endl; } else { cout map is not empty endl; } // 5. begin / end遍历 map // map 会按照 key 从小到大自动排序 cout all elements: endl; for (auto it mp.begin(); it ! mp.end(); it) { cout it-first - it-second endl; } // 6. find查找 key int key 3; auto it mp.find(key); if (it ! mp.end()) { cout find key : it-second endl; } else { cout key not found endl; } // 7. count判断 key 是否存在 if (mp.count(5)) { cout key 5 exists endl; } else { cout key 5 does not exist endl; } // 8. erase删除元素 mp.erase(1); cout after erase key 1: endl; for (auto p : mp) { cout p.first - p.second endl; } // 9. lower_bound找第一个 key x 的元素 int x 3; auto low mp.lower_bound(x); if (low ! mp.end()) { cout lower_bound( x ) low-first - low-second endl; } else { cout no key x endl; } // 10. upper_bound找第一个 key x 的元素 auto up mp.upper_bound(x); if (up ! mp.end()) { cout upper_bound( x ) up-first - up-second endl; } else { cout no key x endl; } return 0; }