C map 底层、AVL 树与 LeetCode 692 高频单词 —— 学习大纲本文基于手写笔记整理std::map 接口与插入语义、LeetCode 692 前 K 个高频单词、AVL 树的定义/旋转/失衡修复。可作为 Feynman 复习入口先看核心知识链再用主动回忆清单自测。摘要核心结论一览模块核心结论一句话要点std::map底层为有序容器平衡 BSToperator[]缺键时自动插入默认值insert返回pairit, bool成功指向新元素失败指向等效元素且不覆盖旧值LeetCode 692哈希表统计词频 小顶堆取 top-k比较器频次小者堆顶频次相同字典序大者堆顶堆大小恒为 kAVL 树最早的自平衡 BST1962任意节点 |bf| ≤ 1失衡分 LL/LR/RR/RL 四类插入修复最多 2 次旋转查找/插入/删除均 O(log n)关键点mymap[str]是最简词频统计写法不存在则插默认值 0再自增。AVL1962高度差 ≤ 1读多写少场景更快与 RB1972颜色弱平衡C11 起 std::map/std::set 实际采用是两类最主要的平衡 BST。LC 692 中字典序只约束频次相同的词堆内保留前 k 后逆序弹出即得答案。易错点insert失败时不覆盖已有 value与operator[]的赋值语义相反LR/RL 情形必须两步旋转先子节点、再父节点不能只旋一次每次旋转后必须回溯更新路径上的高度/平衡因子手写 AVL 最常漏掉LC 692 堆 size 超过 k 后必须立刻 pop否则堆中保留的不是前 k。1. std::map 的接口与实现概览1.1 成员变量与成员函数// map 的核心成员示意// 底层有序容器C11 起标准实现为红黑树早期/教学场景常用 AVL 树public:intmap_count(intn);// 统计接口示例publicmember functions:void:insert,remove,find,...1.2 operator[] 的行为operator[]是 map 特有的按键访问找到 key 对应的元素并返回其引用找不到则自动插入一个key - 默认值的键值对再返回引用。统计场景常用写法笔记示例mapK,Vmymap;for(constautostr:arr){mymap[str];// 等价于不存在则插入默认值 0然后 }有序性与插入的关系笔记要点插入后容器保持字典序有序按 key 的比较已有 key 重复插入不会改变原值配合operator[]是自增/覆盖语义。1.3 map::insert 的返回值insert返回pairiterator, bool情形first迭代器secondbool插入成功指向新元素的迭代器true插入失败key 已存在指向等效元素的迭代器falsemapK,Vmymap;std::pairmapK,V::iterator,boolret;retmymap.insert(pairK,V(key,value));if(ret.second){// 新插入成功ret.first 指向新元素}else{// key 已存在ret.first 指向已有元素value 未被修改}易错点insert失败时不会覆盖已有 value区别于operator[]的赋值。想要有则更新、无则插入用mymap[key] value想要只在没有时插入用insert_or_assign/ 检查ret.second。2. LeetCode 692. 前 K 个高频单词Tags哈希表、堆、排序、字符串、Trie、桶排序题目给定字符串数组words和整数k返回前 k 个高频单词答案按字典序排序频次相同时按字典序。2.1 核心思路用unordered_mapstring, int统计词频用小顶堆保留前 k 个高频词堆大小恒为 k堆的比较器频次小的在堆顶频次相同则字典序大的在堆顶这样字典序更优的先被弹出留下的就是字典序较小的 k 个弹出堆中全部元素逆序得到答案。2.2 参考代码classSolution{public:vectorstringtopKFrequent(vectorstringwords,intk){unordered_mapstring,intcountMap;for(autos:words)countMap[s];autocmp[](conststringa,conststringb,constunordered_mapstring,intm){if(m[a]m[b])returnab;// 频次相同字典序小的优先级低returnm[a]m[b];// 频次小的堆顶};priority_queuestring,vectorstring,decltype(cmp)pq(cmp,vectorstring(),countMap);for(autos:countMap){pq.push(s);if(pq.size()k)pq.pop();}vectorstringans;while(!pq.empty()){ans.push_back(pq.top());pq.pop();}reverse(ans.begin(),ans.end());returnans;}};笔记中出现了自定义结构体比较器MyString带count、重载operator的写法本质相同把频次 字典序编码进一个可排序的类型交给堆完成 top-k 选择。2.3 复杂度时间O(n log m m log k)n 为 words 长度m 为不同词数空间O(m)。3. AVL 树Adaptive Balance Tree / 自平衡二叉搜索树3.1 定义与历史AVL 树是最早发明的自平衡二叉搜索树由苏联科学家 Adelson-Velskii 和 Landis 于1962 年论文《An algorithm for the organization of information》中提出1973 年 Knuth 在《The Art of Computer Programming》第 3 卷中再次提及。为什么叫最早它定义的平衡因子概念早于红黑树AVL 1962 vs RB 1972最早的 AVL 定义节点数不超过 2^h − 1h 为高度最早的平衡约束左右子树高度差不超过 1。3.2 核心性质是二叉搜索树BST左子树 节点 右子树每个节点的左右子树高度差平衡因子绝对值不超过 1左右子树本身也必须是 AVL 树递归定义。平衡因子Balance Factor定义节点左子树高度 − 右子树高度。允许值 ∈ {−1, 0, 1}|bf| 1 即失衡需要旋转修复。3.3 四种失衡与旋转情形触发位置相对失衡节点修复旋转LL左子树的左子树插入对失衡节点右旋LR左子树的右子树插入先对左子节点左旋再对失衡节点右旋RR右子树的右子树插入对失衡节点左旋RL右子树的左子树插入先对右子节点右旋再对失衡节点左旋左旋以 x 为轴其右孩子 y 上移x y \ --左旋-- / y x / \ \ β γ γ步骤笔记 2.2.1设 y x-righty 的左子树 β 挂到 x 的右子树x 整体成为 y 的左子树更新 x、y 的高度回溯路径上的平衡因子。右旋左旋的镜像x y / --右旋-- \ y x / \ / α β β3.4 插入修复实例笔记图示推演基础树Root(10)左 6右 14再插入 8、20、4、12、18、16 等节点逐层检查平衡因子插入 2 的过程2.3.2 图在节点 10 的左子树方向插入 2节点 4 的左子树插入 2 后节点 4 平衡因子 1节点 10 平衡因子仍 0若某节点 |bf| 1按上表执行对应旋转示例中对节点 10 / 节点 4 做左旋恢复。主动回忆插入导致失衡时旋转发生在从新节点往上第一个 |bf|1 的节点且只需一次或两次旋转即可恢复整棵树的 AVL 性质。3.5 查找过程笔记 2.3.4 图搜索从根节点如 a开始在 a 处比较目标按 BST 性质决定进左子或右子在 b 处继续比较在 c 处继续结果找到返回节点找不到返回空。AVL 树高度 O(log n)查找/插入/删除均为 O(log n)。3.6 AVL vs 红黑树补充可展开AVL严格平衡高度差 ≤ 1查找更快旋转次数更多插入/删除稍慢RB 树1972弱平衡增删更稳定std::map / std::set / C11 起 std 容器实际采用应用场景读多写少选 AVL写多或对最坏情况敏感选 RB。4. 知识链条串联Feynman 视角operator[] 自动插入→map 的有序性来自底层平衡 BST→平衡 BST 的平衡约束AVL高度差≤1→失衡检测平衡因子→旋转修复LL/LR/RR/RL 四种→top-k 场景用堆替代遍历排序LC 692。5. 主动回忆清单map::insert返回的 pair 中bool 为 false 时迭代器指向谁value 会被改吗mymap[str]对不存在的 key会发生什么AVL 树和 RB 树谁最早分别在哪一年平衡因子的定义式是什么允许取值LL 情形应该做左旋还是右旋LR 情形分几步插入后需要旋转的位置如何确定为什么旋转后整棵树恢复平衡LC 692 堆比较器为什么要求频次相同时字典序小的优先级低为什么旋转只影响 O(1) 个节点每次最多 2 次旋转6. 易错点总结混淆insert与operator[]的覆盖语义把 AVL 记成 RBAVL 是 1962、高度差 ≤ 1RB 是 1972、颜色弱平衡LR/RL 情形只做一次旋转必须先对子节点旋一次再对父节点旋一次旋转后忘记回溯更新高度这是手写 AVL 最容易漏的一步LC 692 堆大小超过 k 不及时 pop导致答案不是前 k。任何的批评和建议欢迎指出我们共同进步
C++ map 底层与AVL 树
C map 底层、AVL 树与 LeetCode 692 高频单词 —— 学习大纲本文基于手写笔记整理std::map 接口与插入语义、LeetCode 692 前 K 个高频单词、AVL 树的定义/旋转/失衡修复。可作为 Feynman 复习入口先看核心知识链再用主动回忆清单自测。摘要核心结论一览模块核心结论一句话要点std::map底层为有序容器平衡 BSToperator[]缺键时自动插入默认值insert返回pairit, bool成功指向新元素失败指向等效元素且不覆盖旧值LeetCode 692哈希表统计词频 小顶堆取 top-k比较器频次小者堆顶频次相同字典序大者堆顶堆大小恒为 kAVL 树最早的自平衡 BST1962任意节点 |bf| ≤ 1失衡分 LL/LR/RR/RL 四类插入修复最多 2 次旋转查找/插入/删除均 O(log n)关键点mymap[str]是最简词频统计写法不存在则插默认值 0再自增。AVL1962高度差 ≤ 1读多写少场景更快与 RB1972颜色弱平衡C11 起 std::map/std::set 实际采用是两类最主要的平衡 BST。LC 692 中字典序只约束频次相同的词堆内保留前 k 后逆序弹出即得答案。易错点insert失败时不覆盖已有 value与operator[]的赋值语义相反LR/RL 情形必须两步旋转先子节点、再父节点不能只旋一次每次旋转后必须回溯更新路径上的高度/平衡因子手写 AVL 最常漏掉LC 692 堆 size 超过 k 后必须立刻 pop否则堆中保留的不是前 k。1. std::map 的接口与实现概览1.1 成员变量与成员函数// map 的核心成员示意// 底层有序容器C11 起标准实现为红黑树早期/教学场景常用 AVL 树public:intmap_count(intn);// 统计接口示例publicmember functions:void:insert,remove,find,...1.2 operator[] 的行为operator[]是 map 特有的按键访问找到 key 对应的元素并返回其引用找不到则自动插入一个key - 默认值的键值对再返回引用。统计场景常用写法笔记示例mapK,Vmymap;for(constautostr:arr){mymap[str];// 等价于不存在则插入默认值 0然后 }有序性与插入的关系笔记要点插入后容器保持字典序有序按 key 的比较已有 key 重复插入不会改变原值配合operator[]是自增/覆盖语义。1.3 map::insert 的返回值insert返回pairiterator, bool情形first迭代器secondbool插入成功指向新元素的迭代器true插入失败key 已存在指向等效元素的迭代器falsemapK,Vmymap;std::pairmapK,V::iterator,boolret;retmymap.insert(pairK,V(key,value));if(ret.second){// 新插入成功ret.first 指向新元素}else{// key 已存在ret.first 指向已有元素value 未被修改}易错点insert失败时不会覆盖已有 value区别于operator[]的赋值。想要有则更新、无则插入用mymap[key] value想要只在没有时插入用insert_or_assign/ 检查ret.second。2. LeetCode 692. 前 K 个高频单词Tags哈希表、堆、排序、字符串、Trie、桶排序题目给定字符串数组words和整数k返回前 k 个高频单词答案按字典序排序频次相同时按字典序。2.1 核心思路用unordered_mapstring, int统计词频用小顶堆保留前 k 个高频词堆大小恒为 k堆的比较器频次小的在堆顶频次相同则字典序大的在堆顶这样字典序更优的先被弹出留下的就是字典序较小的 k 个弹出堆中全部元素逆序得到答案。2.2 参考代码classSolution{public:vectorstringtopKFrequent(vectorstringwords,intk){unordered_mapstring,intcountMap;for(autos:words)countMap[s];autocmp[](conststringa,conststringb,constunordered_mapstring,intm){if(m[a]m[b])returnab;// 频次相同字典序小的优先级低returnm[a]m[b];// 频次小的堆顶};priority_queuestring,vectorstring,decltype(cmp)pq(cmp,vectorstring(),countMap);for(autos:countMap){pq.push(s);if(pq.size()k)pq.pop();}vectorstringans;while(!pq.empty()){ans.push_back(pq.top());pq.pop();}reverse(ans.begin(),ans.end());returnans;}};笔记中出现了自定义结构体比较器MyString带count、重载operator的写法本质相同把频次 字典序编码进一个可排序的类型交给堆完成 top-k 选择。2.3 复杂度时间O(n log m m log k)n 为 words 长度m 为不同词数空间O(m)。3. AVL 树Adaptive Balance Tree / 自平衡二叉搜索树3.1 定义与历史AVL 树是最早发明的自平衡二叉搜索树由苏联科学家 Adelson-Velskii 和 Landis 于1962 年论文《An algorithm for the organization of information》中提出1973 年 Knuth 在《The Art of Computer Programming》第 3 卷中再次提及。为什么叫最早它定义的平衡因子概念早于红黑树AVL 1962 vs RB 1972最早的 AVL 定义节点数不超过 2^h − 1h 为高度最早的平衡约束左右子树高度差不超过 1。3.2 核心性质是二叉搜索树BST左子树 节点 右子树每个节点的左右子树高度差平衡因子绝对值不超过 1左右子树本身也必须是 AVL 树递归定义。平衡因子Balance Factor定义节点左子树高度 − 右子树高度。允许值 ∈ {−1, 0, 1}|bf| 1 即失衡需要旋转修复。3.3 四种失衡与旋转情形触发位置相对失衡节点修复旋转LL左子树的左子树插入对失衡节点右旋LR左子树的右子树插入先对左子节点左旋再对失衡节点右旋RR右子树的右子树插入对失衡节点左旋RL右子树的左子树插入先对右子节点右旋再对失衡节点左旋左旋以 x 为轴其右孩子 y 上移x y \ --左旋-- / y x / \ \ β γ γ步骤笔记 2.2.1设 y x-righty 的左子树 β 挂到 x 的右子树x 整体成为 y 的左子树更新 x、y 的高度回溯路径上的平衡因子。右旋左旋的镜像x y / --右旋-- \ y x / \ / α β β3.4 插入修复实例笔记图示推演基础树Root(10)左 6右 14再插入 8、20、4、12、18、16 等节点逐层检查平衡因子插入 2 的过程2.3.2 图在节点 10 的左子树方向插入 2节点 4 的左子树插入 2 后节点 4 平衡因子 1节点 10 平衡因子仍 0若某节点 |bf| 1按上表执行对应旋转示例中对节点 10 / 节点 4 做左旋恢复。主动回忆插入导致失衡时旋转发生在从新节点往上第一个 |bf|1 的节点且只需一次或两次旋转即可恢复整棵树的 AVL 性质。3.5 查找过程笔记 2.3.4 图搜索从根节点如 a开始在 a 处比较目标按 BST 性质决定进左子或右子在 b 处继续比较在 c 处继续结果找到返回节点找不到返回空。AVL 树高度 O(log n)查找/插入/删除均为 O(log n)。3.6 AVL vs 红黑树补充可展开AVL严格平衡高度差 ≤ 1查找更快旋转次数更多插入/删除稍慢RB 树1972弱平衡增删更稳定std::map / std::set / C11 起 std 容器实际采用应用场景读多写少选 AVL写多或对最坏情况敏感选 RB。4. 知识链条串联Feynman 视角operator[] 自动插入→map 的有序性来自底层平衡 BST→平衡 BST 的平衡约束AVL高度差≤1→失衡检测平衡因子→旋转修复LL/LR/RR/RL 四种→top-k 场景用堆替代遍历排序LC 692。5. 主动回忆清单map::insert返回的 pair 中bool 为 false 时迭代器指向谁value 会被改吗mymap[str]对不存在的 key会发生什么AVL 树和 RB 树谁最早分别在哪一年平衡因子的定义式是什么允许取值LL 情形应该做左旋还是右旋LR 情形分几步插入后需要旋转的位置如何确定为什么旋转后整棵树恢复平衡LC 692 堆比较器为什么要求频次相同时字典序小的优先级低为什么旋转只影响 O(1) 个节点每次最多 2 次旋转6. 易错点总结混淆insert与operator[]的覆盖语义把 AVL 记成 RBAVL 是 1962、高度差 ≤ 1RB 是 1972、颜色弱平衡LR/RL 情形只做一次旋转必须先对子节点旋一次再对父节点旋一次旋转后忘记回溯更新高度这是手写 AVL 最容易漏的一步LC 692 堆大小超过 k 不及时 pop导致答案不是前 k。任何的批评和建议欢迎指出我们共同进步
