STL容器

STL的allocator
- allocator用途
- allocator原理
STL 技巧
STL的内存优化
STL组件
基础知识
序列式容器
关联式容器
容器对比

STL的allocator

allocator用途

标准库中包含一个名为allocator的类，允许我们将分配和初始化分离。
使用allocator通常会提供更好的性能和更灵活的内存管理能力。std::allocator是标准库容器的默认内存分配器（可以替换成你的分配器，这允许你控制标准容器分配内存的方式）。

new有一些灵活性上的局限，其中一方面表现在它将内存分配和对象构造组合在一起。类似的，delete将对象析构和内存释放组合在了一起。一般情况下，将内存分配和对象构造放在一起可能会导致不必要的浪费，同时带来性能上不必要的消耗。

标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分开来。它提供一种类型感知的内存分配方法，它分配的内存是原始的，未构造的。

allocator原理

STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中，其内存配置和释放如下：

new运算分两个阶段：（1）调用::operator new配置内存；（2）调用对象构造函数构造对象内容
delete运算分两个阶段：（1）调用对象析构函数；（2）调用::operator delete释放内存
为了精密分工，STL allocator将两个阶段操作区分开来：内存配置有allocator::allocate()负责，内存释放由allocator::deallocate()负责；对象构造由::construct()负责，对象析构由::destroy()负责。
同时为了提升内存管理的效率，减少申请小内存造成的内存碎片问题，SGI STL采用了两级配置器。
当分配的空间大小超过128B时，会使用第一级空间配置器。
第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放。
当分配的空间大小小于等于128B时，将使用第二级空间配置器。
第二级空间配置器采用了复杂的内存池技术，通过空闲链表来管理内存。

STL 技巧

首先SGI STL将可用内存整块的分配，使之成为当前进程可用的内存，当程序中确实需要分配内存时，先从这些已请求好的大内存块中尝试去取得内存，如果失败的话再尝试整块的分配大内存。这种做法有效的避免了大量内存碎片的出现，提高了内存管理效率。

为了实现这种方式，STL使用了placement new，通过在自己管理的内存空间上使用placement new来构造对象，以达到原有new operator所具有的功能。

traits可以省略简单类型的析构函数调用的耗费。即像int这种类型是不需要析构函数的，可以不调用析构函数。

STL的内存优化

STL内存管理使用二级内存配置器，第一级配置器，第二级配置器

第一级配置器

以malloc()、realloc()、free()等c函数执行实际的内存配置、释放、重新配置等操作，并且能在内存需求不被满足时调用一个指定的函数。
调用的是大于128字节的空间
如果分配不成功，调用句柄释放一部分内存。
如果还分配不成功，抛出异常。

第二级配置器

根据情况来判定，如果配置区块 大于128字节 ，说明足够大，调用 第一级配置器 。
而 小于等于128字节 ，则采用 复杂内存池（memory pool）来管理。
在STL的二级空间配置器中还多了一些机制，避免太多小区块造成的内存碎片，小区块带来的不仅是内存碎片，配置时还有额外的负担，区块越小，额外负担所占的比例就越大。

二级内存池

采用了16个空闲链表，分别管理大小为8、16、24、……128的数据块。
这里用了一个联合体既可以表示下一块空闲数据块（存于空闲链表中）的地址，也可以表示已经被用户使用的数据块（不存在空闲链表中）的地址。

总结STL内存管理原理

1、使用allocator向内存池请求size大小的内存空间，如果需要请求的内存大小大于128 B，直接使用malloc()
2、如果需要的内存大小小于等于128 B，allocator::allocate()根据size找到最适合的自由链表
①如果链表不为空，返回第一个node，链表头改为第二个node
②如果链表为空，使用blockAlloc，请求分配内存
③如果内存池中有一个大于一个node的空间，分配尽可能多的node（但最多20个），将一个node返回，其他的node添加到链表中。
④如果内存池只有一个node的空间，直接返回给用户
⑤若连一个node都没有，再次向操作系统请求分配内存
a.分配成功，再次进行(2的②)
b.分配失败，循环各个自由链表，寻找空间
①找到空间，再次进行(2的②)
②找不到空间，抛出异常
3、用户调用allcator::deallocate()释放内存空间，如果要求释放的内存空间大于 128 B，直接调用free()
4、否则按照其大小找到适合的自由链表，将其插入。

STL组件

STL主要由以下几个部分组成：
容器、迭代器、仿函数、算法、分配器、配接器。
容器：STL提供的存放数据的类
算法：处理元素的方法和操作
迭代器：为容器提供一组公共接口
仿函数：仿函数具有泛型编程强大的威力，是纯粹抽象概念的例证。（仿函数本质就是类重载了一个operator()，创建了一个行为类似于函数的对象。）
配接器（适配器）：实现不同类之间的数据转换
分配器：内存管理

STL的适配器

适配器：一种用来修饰容器、仿函数或迭代器接口的东西。例如，STL 提供的 queue 和 stack，虽然看似容器，其实只能算是一种容器适配器，因为它们的底部完全借助 deque，所有操作都由底层的 deque 供应；改变仿函数（functor）接口的，称为 function adapter等。
适配器(adapter) 在 STL 组件的灵活组合运用功能上，扮演者转换器的角色。也是一种设计模式（适配器模式）。

应用于容器（container adapter）：STL 提供的两个容器 queue 和 stack，它们修饰 deque 的接口而形成的。
应用于迭代器（iterator adapter）：STL 提供了许多应用于迭代器的适配器。
应用于仿函数（function adapter）。

代码举例function adapter：
count_if（计算符合条件的个数）第三个参数是一个仿函数。minn的代码，这是有两个入参，我们希望使用minn这个仿函数作为count_if的第三个参数。所以我们需要写个配接器适配一下(将两个参数化成一个)。在STL中，提供了相关的函数 bind2nd的适配器，把第二个参数绑定让一个二元函数变成一元的。此前定义的minn不能直接使用在count_if上，因为和count_if的pred不符合，需要继承binary_function:

template<class InputIterator, class Predicate, class Size>
void count_if(const InputIterator first, const InputIterator last, Predicate pred, Size& n)//第三个参数pred是一个仿函数 
{//计算容器内小于5的元素个数 
	for( ; first != last; first++)
	{
		if(pred(*first))//只有一个参数
			++n;
	}
}

template<class T>//在定义一个仿函数（functor）时不会使用binary_function，但是如果需要函数适配器便需要使用它实现：
struct minn : public binary_function<T, T, bool>{//返回bool型值的二元函数 
	bool operator()(const T&x, const T&y) const{return x < y;}
}; 

class Foo
{
public:
	bool operator()(int i)//用一个算法判断是否小于5，是的话返回1
	{
		return minn<int>() (i, 5); 
	}
};

int main()
{
	vector<int> v = {1, 2, 3, 4, 5, 4, 3};
	cout<<count_if(v.begin(), v.end(), Foo())<<endl;
	return 0;
}

STL的二元函数binary_function

在我们使用STL的一些算法的时候，比如find_if等，需要使用仿函数，如果仿函数有2个参数，但是算法需要一个一元的仿函数的时候，我们可以使用适配器，比如：bind1st和bind2nd来将仿函数适配成一元的操作符。这个时候，如果仿函数是我们自己实现的，而不是STL提供的less、greater等等内置好的仿函数时，我们如果要让仿函数支持适配器，那么就必须从binary_function派生出来。
补充：该结构在C++11标准中已废弃，在C++17标准中已移除该结构，可使用该结构的最高C++标准为C++14。

binary_function可以作为一个二元函数对象的基类，它只定义了参数和返回值的类型，本身并不重载（）操作符，这个任务应该交由派生类去完成。
使用实例：

#include <iostream>
#include <functional>         
using namespace std;

struct TCompareNumSize : public std::binary_function<int,int, int>{
 
    int operator() (int num1, int num2)
    {
        return num1 < num2 ? num2 : num1;
    }
 
};

int main()
{
	TCompareNumSize oCompareSize;
	int iMaxNum = oCompareSize(1,2);
	std::cout<<"最大数是："<<iMaxNum<<endl;
	return 0;
}

【补充】
对应的有unary_function，unary_function可以作为一个一元函数对象的基类，它只定义了参数和返回值的类型，本身并不重载（）操作符，这个任务应该交由派生类去完成。

STL中迭代器的作用

Iterator(迭代器)模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中的元素，而又不需要暴露该对象的内部表示。
或者这么说：Iterator模式是运用于聚合对象的一种模式，通过运用该模式是的我们可以在** 不知道对象内部表示的情况下，按照一定顺序（由Iterator提供的方法）访问聚合对象中的各个元素**。
由于Iterator模式以上的特性：与聚合对象耦合，在一定程度上限制了它的广泛运用。一般仅用于底层聚合支持类，如STL的list、vector、stack等容器以及ostream_iterator等扩展iterator。

迭代器产生的原因，为何有指针还需要迭代器
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部结构而达到循环遍历的效果。
迭代器在遍历的时候为什么不用 <
迭代器的实现中没有重载这个操作符，所以遍历的时候应该是 != v.end()

迭代器和指针的区别

迭代器不是指针，是类模板，表现的像指针。它只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、–等。
迭代器封装了指针，是一个“可遍历STL(Standard Template Library)容器内全部或部分元素"的对象。本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为。相当于一种智能指针，它可以根据不同类型的数据结构来实现不同的++、–等操作。
迭代器返回的是对象引用而不是对象的值，所以cout输出迭代器使用 *取值后的值而不能直接输出其自身。

STL迭代器是怎么删除元素

这个主要考察的是迭代器失效的问题
1、对于序列容器vector，deque来说，使用erase(iterator)后，后边的每个元素的迭代器都会失效，后边的每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器。
2、对于关联容器map、set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。
3、对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。
其实都可以通过记录下一个有效位置来继续遍历

容器对应的迭代器

容器	迭代器
vector、deque	随机访问迭代器
stack、queue、priority_queue	无
list、(multi)set / map	双向迭代器
unordered_(multi)set/map、forward_list	前向迭代器

基础知识

STL里resize和reserve

resize()：
改变当前容器内含有元素的数量（size()）
eg:vector<int>v; v.resize(len);
$v$ 的 $s i z e$ 变为 $l e n$ ，如果原来 $v$ 的 $s i z e$ 小于 $l e n$ ，那么容器新增 $(l e n - s i z e)$ 个元素，元素的值默认为 $0$ 。当 $v.push_back(3)$ 之后，则 $3$ 是放在了 $v$ 的末尾，即下标为 $l e n$ ，此时容器时 $s i z e$ 为 $l e n + 1$ 。
reserve()：
改变当前容器的最大容量，它不会生成元素，只是确定这个容器允许放入多少对象
如果 $r e s e r v e （ l e n ）$ 的值大于当前的 $最大容量$ ，那么会重新分配一块能存 $l e n$ 个对象的空间，然后把之前 $v . s i z e ()$ 个对象通过copy constructor复制过来，销毁之前的内存。
reserve()
如果不够大，重新分配一块size大小的内存空间，但多出来的空间没有元素

vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
  	void reserve(size_type __n) {
      	if (capacity() < __n) {
          	const size_type __old_size = size();
          	iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
          	destroy(_M_start, _M_finish);
          	_M_deallocate(_M_start, _M_end_of_storage - _M_start);
          	_M_start = __tmp;
          	_M_finish = __tmp + __old_size;
          	_M_end_of_storage = _M_start + __n;
    }
}

resize()
元素个数设置为size个

void resize(size_type __new_size, const _Tp& __x) {
	if (__new_size < size()) 
		erase(begin() + __new_size, end());
 	else
		insert(end(), __new_size - size(), __x);
}

遍历容器

//反向迭代器map
std::map<int, string> mp;
std::map<int, string>::reverse_iterator riter;
mp[1] = "aaa";
mp[2] = "bbb";
riter = mp.rbegin();
while(riter != mp.rend())
{
	std::cout<<riter->first<<" "<<riter->second<<endl;
	riter++;
}

//反向迭代器vector
std::vector<int> v;
std::vector<int>::reverse_iterator riter;
v.push_back(1);
v.push_back(2);
riter = v.rbegin();
wihle(riter != v.rend())
{
	std::cout<<*riter++<<endl;
}

clear()

clear()可以清空所有元素。但即使clear()，容器所占用的内存空间依旧如故，无法保证内存的回收。

如果需要空间动态缩小，可以考虑使用deque。
①deque没有容量概念，支持下标操作。
std::deque中的元素并非连续存储：典型的实现是使用一个单独分配的固定大小数组的序列。
std::deque的存储空间会自动按需扩大或缩小。
②扩大std::deque比扩大std::vector要便宜，因为它不涉及到现有元素复制到新的内存位置。

STL中的assign()

STL中不同容器之间是不能直接赋值的，assign()可以实现不同容器但相容的类型赋值。

list<string> names;
vector<const char*> oldstyle = { "I","love","you" };
//names = oldstyle;错误！不同的类型不能执行"="操作
names.assign(oldstyle.cbegin(), oldstyle.cend());
list<string>::iterator it;
for (auto it = names.begin(); names.begin() != names.end(); it++)
	cout << *it << " ";

有两点要注意：
1.赋值运算会导致指向左边容器内部的迭代器、引用和指针失效，而swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效(容器类型为array和string的情况除外)。
2.向一个vector、string或deque插入元素会使得所有指向容器的迭代器，引用和指针失效。

【补充】
vector<const char*> oldstyle = { "I","love","you" };该行报错，[Error]在C++98中，“vec”必须由构造函数初始化，而不是由{…}；
原因：是因为编译的时候是编译默认用的是c++98标准，但是运行需要C++11。
解决方法，编译选项-代码生成-语言标准设置为C++11。
【拓展】
C++ 98 标准
C++标准第一版，1998年发布。正式名称为ISO/IEC 14882:1998[18] 。绝大多数编译器都支持C++98标准。不过当时错误地引入了export关键字。由于技术上的实现难度，除了Comeau C++编译器export关键字以外，没有任何编译器支持export关键字。并且这个标准对现代的一些编译理念有相当的差距，有很多在高级语言都应当有的功能，它都没有。这也正是后来需要制定C++11标准的原因所在。

C++ 11 标准
C++标准第三版，2011年8月12日发布。由C++标准委员会于2011年8月12日公布，并于2011年9月出版。2012年2月28日的国际标准草案(N3376)是最接近于现行标准的草案（编辑上的修正）。C++11包含了核心语言的新机能，并且拓展C++标准程序库，并且加入了大部分的C++ Technical Report 1程序库(数学上的特殊函数除外)。此次标准为C++98发布后13年来第一次重大修正。
注意： C++11标准（ISO/IEC 14882:2011）与C11标准（ISO/IEC 9899:2011）是两个完全不同的标准，后者是C语言的标准。

STL中的容器可分为序列式容器（sequence）和关联式容器（associative）。

顺序容器通过元素在容器中的位置顺序存储和访问元素，而关联容器则是通过键(key)存储和读取元素的。
这里的“顺序”和“关联”指的是上层接口表现出来的访问方式，并非底层存储方式。为什么这样划分呢？因为对STL的用户来说，他们并不需要知道容器的底层实现机制，只要知道如何通过上层接口访问容器元素就可以了，否则违背了泛型容器设计的初衷。

STL主要采用向量、链表、二叉树及他们的组合作为底层存储结构来实现容器。尽管一种容器可以采用多种存储方式来实现，但是出于效率的考虑，STL必须为不同的容器类型选择最恰当的存储方式而且不能改变容器的数学模型定义。顺序容器主要采用向量和链表及其组合作为基本存储结构，如堆、栈和各种队列，而关联式容器采用平衡二叉搜索树作为底层存储结构。

序列式容器

序列容器大致包含以下几类容器：
①array<T,N>（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
②vector（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
③deque（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
④list（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
⑤forward_list（正向链表容器）/ slist：和 list 容器非常类似，只不过它以单向链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。
注意，其实除此之外，stack 和 queue 本质上也属于序列容器，只不过它们都是在 deque 容器的基础上改头换面而成，通常更习惯称它们为容器适配器。

vector

vector概念

连续存储的容器，动态数组，在堆上分配空间。
适用场景：经常随机访问，且不经常对非尾节点进行插入删除。

底层实现：数组
两倍或1.5倍容量增长：
不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。
vector增加（插入）新元素时，如果未超过当时的容量，则还有剩余空间，那么直接添加到最后（插入指定位置），然后调整迭代器。
如果没有剩余空间，则会重新配置原有元素个数的两倍空间，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素，最后析构并释放原空间，之前的迭代器会失效。

vector性能：

访问：O(1)
插入：
在最后插入（空间够）：很快
在最后插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。
在中间插入（空间够）：内存拷贝
在中间插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。
删除：
在最后删除：很快
在中间删除：内存拷贝

list

list概念

动态链表，在堆上分配空间，每插入一个元素都会分配空间，每删除一个元素都会释放空间。
底层：双向链表，也是环形链表，对任何位置的元素的插入删除都是常数时间。
适用场景：经常插入删除大量元素。
list中的node节点指针始终指向尾端的一个空白节点，因此是一种“前闭后开”的区间结构。

list性能

访问：随机访问性很差，智能快速访问头尾节点。
插入：很快，一般是常数开销。
删除：很快，一般是常数开销
实现逆向递减排序（还可以配合使用reverse），三种方式：

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};//代码在#include <functional>头文件里
std::sort(numbers.begin(), numbers.end(), greater());
std::sort(numbers.begin(), numbers.end(), std::greater<int>());
std::sort(numbers.rbegin(), numbers.rend());
// note: reverse iterators

关联式容器

关联式容器尽量使用其自身提供的find()函数查找指定的元素，效率更高，因为STL提供的find()函数是一种顺序搜索算法。

set

set属于关联式容器，set的特性是，所有元素都会根据元素的值自动被排序（默认升序），set元素的键值就是实值，实值就是键值，set不允许有两个相同的键值，不允许迭代器修改元素的值，其迭代器是一种constance iterators。

标准的STL set以红黑树作为底层机制，几乎所有的set操作行为都是转为调用RB-tree的操作行为，这里补充一下红黑树的特性：

每个节点不是红色就是黑色
根结点为黑色
如果节点为红色，其子节点必为黑
任一节点至（NULL）树尾端的任何路径，所含的黑节点数量必相同

map

map的特性是：所有元素都会根据元素的键值被自动排序，map的所有元素都是pair，同时拥有实值（value）和键值（key），pair的第一元素被视为键值，第二元素被视为实值，通常通过仿函数select提取出节点的键值进行比较，我们能修改节点的实值但不能修改其键值，对其他元素操作时，其之前和之后的迭代器都不会失效。map使用rb-tree作为底层容器，rb-tree提供了所有map需要的操作，map使用RB_tree的 insert_unique 来插入元素。

其他

map由红黑树实现，key是唯一的。
在map的源码中，不仅重载了运算符 $<$ ，也重载了运算符 $= =$

当以自己构造的结构体为键时，只重载 $<$ 也是可以的，在插入值的时候是使用红黑树中的 insert_unique() 来保证键的唯一性，而非insert_euqal()（multimap使用）
· _Rb_tree 有 insert_unique() 和 insert_equal() 两种，前者不允许有重复值，后者可以。

下标操作

下标（subscript）操作既可以作为左值运用（修改内容）也可以作为右值运用（获取实值）。
map的下标运算符[ ]的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的某个值插入，因此在单纯查找的时候最好使用 .find() 或者 .count()

erase()函数，只能删除内容，不能改变容量大小;clear()函数，只能清空内容，不能改变容量大小;换句话说：clear()函数的作用是清空容器中的内容但并不回收内存，erase()用于清空容器中的内容以及释放内存，并返回指向删除元素的下一个元素的迭代器。

代码运行过程是：首先根据键值和实值做出一个元素，这个元素的实值未知，因此产生一个与实值型别相同的临时对象替代。

hash_table哈希表

hash_table在C++的STL里占据着比较重要的一席之地。其中的hash_set、hash_map、hash_multiset、hash_multimap四个关联容器都是以hash_table为底层实现方法（技巧）。应该说，上述的四个关联式容器提供的api都是对hash_table原生态api的高层封装，因为hash_table本身都提供了它们所需要的基础api。
api:已经写好的可以实现特定功能的函数，而你只需要根据它提供好的接口，也就是调用它的方法，传入它规定的参数，然后这个函数就会帮你实现这些功能。
unordered_map的底层实现是hash_table，hash_map底层使用的是hash_table，而hash_table使用的开链法进行冲突避免，所有hash_map采用开链法进行冲突解决。

简介

1.哈希表的定义：
哈希表是一种根据关键码取寻找值数据的映射（数据）结构，该结构通过把关键码映射的位置去寻找存放值的地方，就比如查字典。关键字通过哈希函数f(key)查找对应的哈希值，这过程就是键码映射。

2.哈希冲突
由于一格上可以存放多个值，也就是公式表达上key1 != key2，但是f(key1) = f(key2)，这就是哈希冲突。
一个好的Hash函数不仅性能优越，而且还会让存储于底层数组中的值分配的更加均匀，减少冲突发生。之所以是减少冲突，是因为取Hash的过程，实际上是将输入键（定义域）映射到一个非常小的空间中，所以冲突是无法避免的，能做的只是减少Hash碰撞发生的概率。
(*)比较好的哈希函数：time33算法。

3、哈希函数构造方式
①直接定址法：取关键字或者关键字的一个线性函数值为散列地址即：hash(k) = k 或者 hash(k) = ak + b(a、b为常数)，这种散列函数又称为自身函数.由于直接定址法所得的地址集合和关键字集合的大小相同，因此对于不同的关键字不会发生冲突，但是实际中能使用这种哈希函数的情况比较少；

②(*)数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可以取关键字的若干位组成哈希地址。
例如：假设８０个关键字的一部分如下图所示：
可以发现：
第１和第２位都是８和１，
第３位只能取３或４，
第８位只能取２．５或者７；
因此在取地址的时候不能取这四位（１．２．３和８）。由于中间的四位（４．５．６．７）近似于随机，因此可以选择其中两位或者其中两位和另外的两位叠加求和然后舍去进位作为哈希地址。

③平方取中法：取关键字的平方后的中间几位为散列地址，位数由表长决定。这是一种比较常用的方法，通常在选定哈希函数时不一定能知道关键字的全部情况，因此去其中的哪几位不一定合适，而一个数的平方后的中间几位是和一个数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的；
例如：在计算机内可用两位八进制数表示字母和数字，取标识符在计算机中的八进制数为它的关键字，假设表长为512(2^9)则可取关键字平方后中间９位二进制数【八进制为三位】为哈希地址。

④除留余数法：取关键字被某个不大于哈希表表长m的数p除后取得的余数为散列地址即：hash(k) = k mod p (p < m)。这是一种最常用的方法获取哈希地址，可以直接对关键字取模，也可以先对关键字平方等运算之后再取模（一般使用mod = 13131……）。
注意：在使用该方法时一定要注意p的选择，p选择不好很容易产生冲突如下:
假设取标识符在计算机中的二进制表示为它的关键字（每个字母都用两位八进制数表示），然后对p = 2^6取模，相当于将关键字左移直至只留下最低的６位二进制数。这样的算法问题所在：最后一个字符相同的所有标识符都会产生冲突；
若p含有质因子pf,则所有含有pf因子的关键字的哈希表地址都是pf的倍数；
总结：一般来说，p可以选择为质数或者不包含小于20的质因数的合数

⑤随机数法：通常用于关键字长度不等时采用。

实现原理

hash_table底层是通过开链法实现的，hash_table表格内的元素称为桶(bucket)，而桶所链接的元素称为节点(node)，其中存入桶元素的容器为STL本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器，只要是因为vector容器本身具有动态扩容能力，无需人工干预。
在hash_table的实现过程中，我们会认识到一个专有名词：负载系数（loading factor)，意指元素个数除以表格大小。很显然，通过开链法，负载系数会大于1。同样在开链方法中，用于装载桶元素的vector容器大小恒定为一个质数大小，在具体实现中表现为28个从小到大的28个质数，如：53、97、193、389……。每次重新分配vector容器大小时，总是将新容器大小设定为第一个大于当前需要的新容器大小的质数值（上述28个质数中的其中一个）。

重建表格：
当元素个数 > hash_table表格大小时，要求重建表格，重建表格是要将每一个元素重新进行hash，然后再delete掉旧的hash_table的所有元素。
对于不是整型的键值要进行数值化（即对应的ASCII码），再进行hash
迭代器
hash_table迭代器必须永远维系着与整个“bucket vector”的关系，并记录目前所指节点，其前进操作时首先尝试从目前所指的节点出发，前进一个位置(节点)，由于节点被安置于list内，所以利用节点的next指针即可轻易达到前进操作。如果目前节点正巧是list的尾端，就跳至下一个bucket身上，那正是指向下一个list的头部节点。
其迭代器没有减操作，也没有逆向迭代器。

解决冲突的方法

线性探测
使用hash函数计算出的位置如果已经有元素占用了，则向后依次寻找，找到表尾则回到表头，直到找到一个空位。
开链
每个表格维护一个list，如果hash函数计算出的格子相同，则按顺序存在这个list中。
再散列
发生冲突时使用另一种hash函数再计算一个地址，直到不冲突。
二次探测
使用hash函数计算出的位置如果已经有元素占用了，按照 $1^2$ 、 $2^2$ 、 $3^2$ …的步长依次寻找，如果步长是随机数序列，则称之为伪随机探测。
公共溢出区
一旦hash函数计算的结果相同，就放入公共溢出区。

哈希表的性能

查找或者插入得情况在大多数情况下可以达到O(1)，时间主要花在计算hash上。最坏得情况就是hash值全都映射到同一个地址上，这是哈希表就退化成链表，查找的时间复杂度就变成O(n)，但是这种情况比较少，一般不会出现。
在这里插入图片描述

扩容

hash_table表格内的元素称为桶，而由桶所连接的元素称为节点，其中存入桶元素的容器为STL本身很重要的一种序列式容器——vector。选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。
**扩容（resize）**就是重新计算容量，向hash_map对象里不停添加元素，当hash_map对象内部的数组无法装载更多元素时。对象就要扩大数组的长度，以便能装入更多的元素。
**什么时候扩容：**当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值，即当前数组的长度乘以加载因子的值的时候，就要进行自动扩容。
前进操作：首先尝试从当前所指的节点出发，前进一个位置（节点），由于节点被安置于list内，所以利用节点的next指针即可轻易完成前进操作，如果目前节点正巧是list的尾端，就跳至下一bucket身上，那正是下一个list的头部节点。

基本操作

hash_map的函数和map的函数差不多，这里介绍几个常用函数：
1、hash_map(size_type n)如果讲究效率，这个参数是必须要设置的。n主要用来设置hash_map容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。n越大，效率越高，但是内存消耗也越大。
2、const_iterator find(const key_type& k) const用于查找，输入为键值，返回为迭代器
3、data_type& operator[](const key_type& k)注意：当使用[key ]操作符时，如果容器中没有key元素，就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，可以使用find()，当你希望插入该元素时，你可以直接使用[ ]操作符。
4、insert函数，在容器中不包含key值时，insert函数和[ ]操作符的功能差不多，但是当容器中元素越来越多时，每个桶中的元素会增加，为了保证效率，hash_map会自动申请更大的内存，以生成更多的桶。因此在insert以后，以前的iterator有可能是不可用的。
5、erase函数，在insert的过程中，当每个桶的元素太多时，hash_map可能会自动扩充容器的内存。**但是在SGI STL中erase并不会自动回收内存，因此在调用earse后，其他元素的iterator还是可用的。**但是在调用count或者find的时候，这个键就当作不存在。

slist

list是双向链表，而slist（single linked list）是单向链表，它们的主要区别在于：
list的迭代器是双向的Bidirectional iterator，slist的迭代器属于单向的Forward iterator。虽然slist的很多功能不如list灵活，但是其所耗用的空间更小，操作更快。
根据STL的习惯，插入操作会将新元素插入到指定位置之前，而非之后，然而slist是不能回头的，只能向后走，因此在slist的其他位置插入或者移除元素是十分不明智的，但是在slist开头却是可取的，slist特别提供了insert_after()和earse_after供灵活使用。
考虑到效率问题，slist只提供push_front()操作，元素插入到slist后，存储的次序和插入的次序是相反的。push_front()之后，输出是反向的，即存储也是反向的。
需要注意的是C++标准委员会没有使用slist的名称，forward_list在C++11中出现。它与slist的区别是没有size()方法。

deque

vector是单向开口（尾部）的连续线性空间，deque则是一种双向开口的连续线性空间，虽然vector也可以在头尾进行元素操作，但是其头部操作的效率十分低下（主要是涉及到整体的移动）
-deque与vector的区别
- deque运行在常数时间内对头端进行元素操作
- deque没有容量概念，它是动态地以分段连续空间组合而成，可以随时增加一段新的空间并链接起来。
- deque虽然也提供随机访问的迭代器，但是其迭代器并不是普通的指针，其复杂程度比vector高很多，因此除非必要，否则一般使用vector而非deque。如果需要对deque进行排序，先将deque中的元素复制到vector中，利用sort对vector排序，再将结果复制回deque。

deque的实现

deque内部有一个指针指向map，map是一小块连续空间，其中的每个元素称为一个节点(node)，每个node都是一个指针，指向另一端较大的连续空间，称为缓冲区，这里就是deque中实际存放数据的区域，默认大小512bytes。
deque迭代器的“++”、“–”操作是远比vector迭代器繁琐，其主要工作在于缓冲区边界，如何从当前缓冲区跳到另一个缓冲区，当然deque内部在插入元素时，如果map中node数量全部使用完，且node指向缓冲区也没有多余空间，这时会配置新的map(2倍于当前的数量)来容纳更多的node，也就是可以指向更多的缓冲区。在deque删除元素时，也提供了元素的析构和空闲缓冲区空间的释放等机制。

stack

栈是一种先进后出（First In Last Out）的数据结构，只有一个入口和出口，那就是栈顶，除了获取栈顶元素外，没有其他方法可以获取到内部的其他元素。
stack这种单向开口的数据结构很容易由双向开口的deque和list形成，只需要根据stack的性质对应移除某些接口即可实现。
stack这种“修改某种接口，形成另一种风貌”的行为，成为adapter(配接器)。常将其归类为容器配接器而非容器。
stack除了默认使用deque作为其底层容器之外，也可以使用双向开口的list，只需要在初始化stack时，将list作为第二个参数即可。由于stack只能操作顶端的元素，因此其内部元素无法被访问，也不提供迭代器。

queue

队列是一种先进先出（First In First Out）的数据结构，只有一个入口和一个出口，分别位于最底端和最顶端，除了出口元素外，没有其他方法可以获取到内部的其他元素。
类似的，queue这种“先进先出”的数据结构很容易由双向开口的deque和list形成，只需要根据queue的性质对应移除某些接口即可实现。
同样，queue也可以使用list作为底层容器，不具有遍历功能，没有迭代器。

priority_queue

heap

heap（堆）并不是STL的容器组件，是priority queue（优先队列）的底层实现机制，因为binary max heap（大根堆）总是最大值位于堆的根部，优先级最高。

binary heap本质是一种complete binary tree（完全二叉树），整棵binary tree除了最底层的叶节点之外，都是填满的，但是叶节点从左到右不会出现空隙。
特点：插入、删除的时间复杂度：O(lgn)；获取最大值/最小值的时间复杂度：O(1)

大根堆

大根堆就是根节点是整棵树的最大值(根节点大于等于左右子树的最大值)，对于他的任意子树，根节点也是最大值。大根堆有两个操作，一个创建堆heapInsert时间复杂度是O(N),还有一个操作是当大根堆里的某个节点的值，发生变化的时候，需要对这个大根堆进行调整，每一次调整时间复杂度是O(logn)，调整的次数是跟这个堆的高度有关，为O(h)。

堆排序

堆排序就是利用了heapinsert和heapify来进行排序，当创建完大根堆以后，每一次都把堆顶的元素和堆的最后一个元素进行交换，并且把堆的长度减小1，然后对新的堆进行调整，重新调整为大根堆，然后再取堆顶的元素和堆的最后一个节点进行交换，大根堆的长度减小1，然后再调整，重复这个过程，直到堆里面剩余的元素个数为1。这就是堆排序。这样子取出来的元素序列是有序的。
特点（没有绝对的优缺点）：堆排序的时间复杂度是O(nlgn)，堆排序的时间复杂度不是O(n^2)。堆可以采用额外的空间，来降低了时间复杂度（用O(1)时间求堆内最小元素，加一个栈去存最小元素值，用空间换时间）。
由于它在直接选择排序的基础上利用了比较结果形成，效率提高很大。它完成排序的总比较次数为O(nlogn)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：一是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。
  1)最坏情况下o(nlgn)的时间复杂度
   2)就地排序，不用辅助数组

priority_queue

优先队列，是一个拥有权值观念的queue，它跟queue一样是顶部入口，底部出口，在插入元素时，元素并非按照插入次序排列，它会自动根据权值（通常是元素的实值）排列，权值最高，排在最前面。
默认情况下，priority_queue使用一个max-heap完成，底层容器使用的是一般为vector为底层容器，堆heap为处理规则(保持堆性质)来管理底层容器实现。priority_queue的这种实现机制导致其不被归为容器，而是一种容器配接器。

int arr[100];
int n;

void swap(int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void heapInsert(int index)//创建大根堆 1
{
	while(arr[index] > arr[(index - 1) / 2]){
		swap(index, (index-1) / 2);
		index = (index - 1) / 2;		
	}
}

/*
void heapInsert(int index)//创建大根堆 2
{
	for(int i = index/2; i >= 0; i--)
	{
		heapify(i, index);
	}
}
*/
void heapify(int index, int heapSize)//堆调整，保持堆特性 
{
	int left = index * 2 + 1;
	while(left < heapSize)//直至这个节点的父节点不再小于这个节点 
	{
		int largest = left;
		if(left + 1 < heapSize){
			largest = arr[left + 1] > arr[left] ? left + 1 : left;
		}
		largest = arr[largest] > arr[index] ? largest : index;
		if(largest == index){
			break;
		}
		swap(largest, index);
		index = largest;
		left = index * 2 + 1;
		//heapify(largest, heapSize);	
	}
}

void heapSort(int n)//堆排序 = heapInsert + swap + heapify 
{
	if(n == 0 || n < 2)
	{
		return ;
	}
	for(int i = 0; i < n; i++)
	{
		heapInsert(i);
	}
	int size = n;
	swap(0, --size);
	while(size > 0)
	{
		heapify(0, size);
		swap(0, --size);
	}
	/*for(int i = size; i >= 2; i--)
	{
		swap(0, size-1);
		size--;
		heapify(0, size);
	}*/
}

//以下为优先队列操作 
//返回最大元素 
int heapMax()
{
	return arr[n-1];
} 

//返回最大元素并取出
int heapExtractMax()
{
	int maxn = arr[n-1];
	arr[n] = 0;
	n--;
	for(int i = 0; i < n; i++)
	{
		heapInsert(i);
	}
	return maxn;
}

//将第i个元素优先级增长为 key，与 heapInseert逻辑差不多 
void heapIncreaseKey(int i, int key)
{
	i = i - 1;//第 i个元素在下标从 0开始存的数组中，在 i-1 位 
	if(key > arr[i])
	{
		arr[i] = key;
		while(arr[i] > arr[(i - 1) / 2]){
		swap(i, (i-1) / 2);
		i = (i - 1) / 2;
		}
	}
}

//将元素x插入到优先级队列
void heapInsertx(int key)
{
	arr[n] = -1;
	n++;//注意这两步的顺序 
	//cout<<n<<" "<<key<<endl;
	heapIncreaseKey(n, key);
}

int main()
{
	cin>>n;
	for(int i = 0; i < n; i++)
		cin>>arr[i];
	
	//堆排序 
	heapSort(n);
	for(int i = 0; i < n; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	
	//返回最大元素值 
	cout<<heapMax()<<endl;
	
	//返回最大元素值并取出 
	cout<<heapExtractMax()<<endl;
	for(int i = 0; i < n; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	
	//将第i个元素优先级增长为 key
	heapIncreaseKey(2, 9);
	for(int i = 0; i < n; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	
	//将元素x插入到优先级队列
	heapInsertx(6);
	for(int i = 0; i < n; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}
/*
8
4 5 8 2 3 9 7 1
*/

红黑树

红黑树基本概念:

它是二叉排序树（继承二叉排序树特显）：
- 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值。
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
它满足如下几点要求：
- 树中所有节点非红即黑。
- 根节点必为黑节点。
- 红节点的子节点必为黑（黑节点子节点可为黑）。
- 从根到NULL的任何路径上黑结点数相同。
查找时间一定可以控制在O(logn)。

容器对比

map和set的区别、实现

相同点：map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调用RB-tree 的操作行为。

map和set区别在于：

map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。
set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。
map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，

· const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用。
· mapped_type类型没有默认值也不应该使用。如果find()能解决需要，尽可能用find()。

vector和list的区别

vector底层实现是数组；list是双向链表。
vector支持随机访问，list不支持。
vector是顺序内存，list不是。
vector在中间节点进行插入删除会导致内存拷贝，list不会。
vector一次性分配好内存，不够时才进行2（或1.5）倍扩容；list每次插入新节点都会进行内存申请。
vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。
应用
vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

map与unordered_map区别及使用

需要引入的头文件不同
map: #include < map >
unordered_map: #include < unordered_map >
内部实现机理不同
map： map内部实现了一个红黑树，红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树存储的，使用中序遍历可将键值按照从小到大遍历出来。
unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。
优缺点以及适用处
map：
优点：有序性，这是map结构最大的优点，其元素的有序性在很多应用中会简化很多操作，内部实现一个红黑树使得map的很多操作在log(n)的时间复杂度下就可以实现，因此效率非常高。
缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
适用处：对于那些有顺序要求的问题，用map会更高效一些。
unordered_map：
优点：因为内部实现了哈希表，因此其查找速度非常的快。
缺点：哈希表的建立比较耗费时间。
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。
· 其底层实现是完全不同的，但是就外部使用来说却是一致的。

平衡二叉树与二叉查找树

二叉查找树

二叉查找树，也称二叉搜索树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的二叉树：
（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）任意节点的左、右子树也分别为二叉查找树；
（4）没有键值相等的节点。

在这里插入图片描述
二叉查找树是对要查找的数据进行生成树，左支的值小于右支的值。在查找的时候也是一样的思路，从根节点开始，比节点大进入右支，比节点小进入左支，直到查找到目标值。
二叉查找树的插入算法比较简单：空树，就首先生成根节点；不是空树就按照查找的算法，找到父节点，然后作为叶子节点插入，如果值已经存在就插入失败。
删除操作稍微复杂一点，有如下几种情况：
（1）如果删除的是叶节点，可以直接删除；
（2）如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
（3）如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除。
二叉查找树还有一个性质：即对二叉查找树进行中序遍历，即可得到有序的数列。
二叉查找树的查询复杂度，和二分查找一样，插入和查找的时间复杂度均为 O(logn) ，但是在最坏的情况下仍然会有 O(n) 的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) 。

平衡二叉树

&nnbsp;由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，这也是平衡二叉树设计的初衷。平衡二叉树是一棵高度平衡的二叉查找树，根据定义，平衡二叉树（AVL树）有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树。
平衡因子：结点的左子树的深度减去右子树的深度。即：结点的平衡因子 = 左子树的高度 - 右子树的高度。
在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1;
构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡(插入失衡)，如果是，则需要做旋转去改变树的结构。旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。即左旋就是往左变换，右旋就是往右变换。
在这里插入图片描述

可能出现的情况就有4种，分别称作左左，左右，右左，右右。
例如：左左：

在这里插入图片描述
左右：

右右跟左左一样，只需要旋转一次就能把树调整平衡，而左右跟右左也一样，都要进行旋转两次才能把树调整平衡，将左右进行第一次旋转，将左右先调整成左左，然后再对左左进行调整，从而使得二叉树平衡。
平衡二叉树构建的过程，就是节点插入的过程，插入失衡情况就上面4种。
平衡二叉树节点的删除，删除的情况会复杂一点，复杂的原因主要在于删除了节点之后要维系二叉树的平衡，但是删除二叉树节点总结起来就两个判断：①删除的是什么类型的节点？②删除了节点之后是否导致失衡？
节点的类型有三种：1.叶子节点；2.只有左子树或只有右子树；3.既有左子树又有右子树。
针对这三种节点类型，再引入判断②，所以处理思路分别是：
（1）当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整。
（2）删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。
（3）删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。

平衡二叉树是一棵高度平衡的二叉树，所以**查询的时间复杂度是 O(logN) **。插入的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，**插入复杂度是 O(1) **，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树。

红黑树

待更新，跑路

原文链接：https://blog.csdn.net/m0_49069293/article/details/122472946