一、树

（1）BST-二叉查找树、二叉排序树；

　　  左子树所有结点的值均小于或等于它根结点的值；右子树上所有结点的值均大于或等于它根结点的值；

（2）RBT-红黑树、平衡二叉查找树；

　　  防止二叉查找树变成线性，

（2）AVL-平衡二叉树：任何结点的两个子树高度差不会超过1；

　 　 根据平衡因子做判断，左旋右旋等完整解析：https://baijiahao.baidu.com/s?id=1669654153406486945&wfr=spider&for=pc

 

一、迭代器失效

（1）关联容器迭代器，比如map、set、multimap、multiset, 删除当前的iterator, 仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可，因为map类的容器；使用了红黑树或者平衡二叉树来实现；即便插入、删除一个结点，可以调整自身的平衡性，不会对其它结点产生影响；erase迭代器只是被删元素的迭代器失效，但是返回值为void, 所以要采用erase(iter++)自增的方式来删除迭代器；

// 正确代码
for (it = m.begin(); it != m.end(); it++) {
　　if (it->first==5) {
　　　　m.erase(it++);
　　}
}

（2）序列容器迭代器，比如vector、deque, 删除当前的迭代器iterator时，其后所有元素的迭代器都会失效，这是因为序列式容器都是连续分配的内存空间，当对其进行erase操作时，后面的所有元素都会向前移动；因此earse需要返回下一个有效的iterator；

for (it = m.begin(); it != m.end(); it++) {
　　(*it)->doSomething();
　　if (*it > 3) {
　　　　it = m.erase(it); // 返回下一个有效的迭代器
　　} else {
　　　　++ it;
　　}
}