1.map的opeator[]

功能：

如果访问对象存在就返回指定键的值的引用，如果指定的键不存在会插入新的键值对，键是传递给operator[]的参数，值是使用该值类型的默认构造函数构造的(对于简单类型通常是0或者空字符)。

代码示例：

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));//key不存在->插入{"insert","string()"}dict["insert"];//key不存在->插入+修改dict["left"] = "左边";//key存在->修改dict["left"] = "z边";//查找 确定存在key使用，不然就插入了cout << dict["left"] << endl;return 0;
}

2.map的insert

插入成功会返回插入值所咋位置的迭代器，并且bool为true，插入失败说明已经存在，这会返回存在位置的迭代器，并且bool为false

3.operator的内部实现

这里有俩个pair需要注意，第一个是iterator和bool的，it指向的是map的某个元素，而map的元素也有pair键值对，所以it也有second，second是值。

4.例题

题目：

代码讲解：

 首先要把接受的words进行处理，把重复的累计起来，使用map可以得到{”单词名字“,"出现的次数"},然后可以提供排序去找到最多次的前几个，但是map是不能排序，因为map是只能排键值(会按照字典顺序排序好)，所以我们可以用vector或者multiset等，pair是可以比较的，它是比较键值和值，先比较键值，然后比较值大小，关系是 ||，前面大就大，只有俩个一样才相等，但是我们只比较值大小，所以要自定义仿函数，只比较值大小(second)，这里用sort的函数会导致一部分案例不通过，是因为sort快排是不稳定的排序，在相等值时可能会改变前后顺序，但是题目要求要字典顺序，sort会破坏前面map排序好的字典顺序，所以要用stable_sort，看名字就知道是稳定的快排，最后取出前k个放到vector里面，就完成了。

class Solution {
public:struct Compare{bool operator()(const pair<std::string,int>& left,const pair<std::string,int>& right) const{return left.second > right.second;}};vector<string> topKFrequent(vector<string>& words,int k){map<string,int> m;for(size_t i=0;i<words.size();i++)++(m[words[i]]);vector<pair<string,int>> v(m.begin(),m.end());stable_sort(v.begin(),v.end(),Compare());vector<string> str;for(size_t i=0;i<k;i++){str.push_back(v[i].first);}return str;}
};

 5.AVL树概念

AVL树是最先发明的自平衡树，AVL是空树，或者具备下列性质的二叉搜索树：左右子树都是AV树，且左右子树的高度差绝对值不超过1.AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。

AVL树实现引入平衡因子(balance factor)的概念，每个节点都有一个平衡因子，任何节点的平衡因子等于左右子树的高度，也就是说任何节点的平衡因子等于-1/0/1，AVL并不是必须要平衡因子，但是有了平衡因子方便我们去进行观察和控制树是否平衡。

AVL树整体结点数量和分布完全二叉树相似，高度可以控制在logN，那么增删查改的效率可以控制在0(logN).

平衡因子更新

更新原则：

平衡因子=右子树高度-左子树高度

只有子树高度变化才会影响当前结点平衡因子

插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子--。

parent所咋子树高度是否变化决定了是否会继续晚上更新平衡因子

更新停止条件：

更新后parent的平衡因子等于0，更新中的parent的平衡因子变化为-1->0或者1->0,说明更新前parent子树一边高一边底，即新增的结点插入在低的那一边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。

更新后的parent的平衡因子等于1/-1，更新前parent的平衡因子变化0->-1或者0->1,说明更新前parent子树俩边一样高，新增结点后，parent所在的子树一边高一边低，parent所在的子树满足平衡要求，但是高度加1，会影响parent的父节点的平衡因子，所以要继续向上更新。

更新后parent的平衡因子等于2/-2，更新前parent的平衡因子变化为1->2或者-1->2,说明更新前parent的子树一边高一边低，新增的插入结点在高的那一边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡了，需要旋转处理，旋转目标：1，把parent子树旋转平衡。2，降低parent子树的高度，恢复插入结点之前的高度。所以旋转后也不需要继续往上更新，插入结束。

左单旋

本图展示是10为根的树，有a/b/c抽象为三颗高度为h的子树，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。

在a子树插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变到2，10为根的子树左右高度差超过1，违反了平衡。需要旋转。

旋转的核心步骤，因为10<b子树的值<15，将b变为10的右子树，10变为15的左子树，15变成树的新根，符合搜索树的规则，同时这颗树的高度回复到了插入之前的h+2。

右单旋

这里b<10&&b>5，所以把5作为新根，把b旋转到10的左边，高度还是3. 

这里插入新结点后平衡破坏了，所以要旋转，把5作为新根，8到10的左结点，高度不变。

左边插入结点后，根的平衡因子变为2，所以把根10变为结点5的右子树，5为新根。

这里36是x，y和z三种，b和c是其中一种，就是3*3，而插入到a可以为俩个结点的左右俩边就是4种，所以是3*3*4=36。

代码实现

template<class k,class v>
struct AVLTreeNode
{pair<k, v> _kv;AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;AVLTreeNode<k, v>* _parent;int _bf;//balance factorAVLTreeNode(const pair<k,v>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(parent),_bf(0){}};template<class k,class v>
class avltree
{//typedef AVLTreeNode<k, v> Node;using AVLTreeNode < k, v >= Node;
public: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 (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (cur){if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1){//旋转break;}elseassert(false);}}private:Node* _root = nullptr;};