树
这里有一个网站提供了html5的可视化数据结构，会对学习有帮助。
AVL树
顺序表查找快，链表增删快，有没有一种数据结构能将二者的优点都结合起来呢？有，那就是平衡二叉树。平衡二叉树的左子树中的节点都小于根节点，右子树中的节点都大于根节点，假设左右子树相等，搜索时只需判断一次大小就排除了一半的数据，这不就是二分查找么！！！所以查找的复杂度为，又因为平衡二叉树是由指针构造的逻辑结构，所以增删节点只需要。
| 查找 | 增删(已知节点位置) | 增删(先查询节点位置) | |
|---|---|---|---|
| 有序顺序表 | |||
| 链表 | |||
| 平衡二叉树 |
初学时会觉得又不是常数，也没有改善多少嘛，和有多少区别呢？
举个例子，假如从条数据中搜索，大概需要搜索一千亿次，而是二分查找的效率，每次减半，只需要搜索50次。优化效果恐怖如斯，即便是世界上最大的数据库也可以在50次内完成搜索。
AVL树在失衡的时候需要左旋或右旋来重平衡，而左旋、右旋的操作和记忆都比较麻烦，比较好的方法是“3+4重构”，因为调整的目的就是为了平衡，所以我们只需将失衡的节点按照平衡时的样子重新组装，无需关注如何旋转。
“3+4重构”的难点在于确定T0、T1、T2、T3，例如：
添加关键字48，如何“3+4重构”？
48添加在37上，添加后会导致24不平衡，所以24到37经过的这三个节点就是a、b、c，它们的孩子是T0、T1、T2、T3。
我们来总结一下：不平衡节点到被添加节点所经过的三个节点就是a、b、c。
伸展树
有没有比平衡二叉树更快的搜索方法？有的，不过只能保证大多数情况。平衡二叉树复杂度中的其实就是平衡二叉树的高度，树越高复杂度越大，那么就想办法降低树高呗！计算机中有个局部性原理，常用的数据只占很小一部分，例如我们计算机中有那么多文件，你常用的是不是就那么几个？伸展树就是利用这个原理，将常用的数据提到树顶，而其它大量的数据又不常用，这相当于无形中降低了树的高度，将原来高度为h的树将为常用数据组成的高度为k的树。伸展树不是平衡的二叉树，在最差的情况复杂度会退化为，不过伸展树不会连续出现这种情况。
B树
以上所提到的数据结构都是基于内存的，但是如果数据大到一定程度就需要将数据存储到硬盘中，考察硬盘的特点：
- 硬盘的速度比内存慢的多，假如访问内存需要1秒，那么访问硬盘就需要一天。
- 从硬盘中读1B和1KB速度几乎是一样的。
B树就是根据硬盘的特点设计出来的m路平衡搜索树。
它相当于将二叉树的多个节点结合成一个节点，目的是为了尽量少的访问硬盘，一旦访问硬盘则多读取一些数据。B树还有一个特点就是叶节点的高度完全一致。
B树阶的概念可以类比二叉树，二叉树说明最多有两个分支，5阶B树说明最多有5个分支。B树不仅最多分支数有限制，最小分支数也有限制，例如m阶B树，最多有m个分支，最少有个分支。特别的，根节点没有最少分支数的限制。
考研中B树的高度是不包括最下层没有任何关键字的叶节点的(有些书中包括)。
| 条件 | 解决方法 | ||
|---|---|---|---|
| 上溢 | 当插入新节点后，分支总数超过阶数 | 分裂 | 以中间节点一分为二，中间节点变成父节点，左右两份变成其孩子。若节点个数为偶数，取中间靠右的那个节点作为中间节点。 |
| 下溢 | 删除节点后，分支总数少于最低要求 | 旋转 | 就是向兄弟节点借(三角借债，向父亲，兄弟给父亲，) |
| 合并 | 如果借不到，连同兄弟和父亲一起合并成为新的节点 |
B+树
B+树是B树的扩展，与B树有如下几处不同：
- 在B树中，含n个关键字的“超级节点”有n+1个孩子；在B+树中含n个关键字的“超级节点”有n个孩子。
- 在B树中，每个节点的关键字个数范围是；在B+树中每个节点的关键字个数范围是。
- 在B树中，非叶节点包含信息，每个关键字在树中仅会出现一次；在B+树中只有叶节点包含信息，而非叶节点只起到索引的作用，所以有些关键字会出现多次。
- B+树的叶节点相互串联，便于顺序查找。
多叉树
多叉树有一个重要的公式，高度为h的m叉树至多有个节点，反过来具有n个节点的m叉树的最小高度为。
节点的分支树就是该节点的度。所有节点的度数等于所有节点数减1。
任何一棵多叉树都可以转换为二叉树吗？是的。因为，树有多种存储方式，其中一种是孩子兄弟表示法，如果你将多叉树转换为孩子兄弟表示法，从结构上看它就是一颗“二叉树”。
多叉树转换为二叉树的规则：每个节点左指针指向它的第一个孩子，右指针指向它在树中的相邻的右兄弟，这个规则又称为“左孩子右兄弟”。
树、森林与二叉树的转换
树转换为二叉树：
每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子石兄弟”。
森林转换为二叉树：
先将森林中的每颗树转换为二叉树，再将二叉树的根节点相连即可。
线索树二叉树
在含有n个节点的二叉树中，含有n+1个空指针。我们可以用这些空指针指向其遍历序列的前驱节点和后继节点。这种树被称作线索二叉树。根据遍历序列的不同，线索树也分为中序线索树、先序线索树、后续线索树。
若无左子树，lchild指向前驱节点；若无右子树，rchild指向其后继节点。为此我们还有添加两个标识，以区分指向的是孩子还是线索。
哈夫曼树
节点的带权路径长度 = 节点的权值 x 该节点的路径长度
树的带权路径长度 = 所有叶节点的带权路径长度之和
上述3棵树的带权路径长度分别为：
WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36
WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46
WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35
带权路径长度最小的树称为哈夫曼树。
给定n个权值分别为的结点，构造哈夫曼树的算法描述如下：
1）将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
2）构造一个新结点， 从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4）重复步骤2）和3），直至F中只剩下一棵树为止。
哈夫曼编码
哈夫曼编码是哈夫曼树的重要应用之一。在数据通信中，对高频字符赋以短编码，对低频字符赋以较长编码，这样可以缩短平均编码长度。若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。前缀编码的解码是唯一的。例如：若A、B、C的编码为0，101，100，则编码00101100的解码为AABC。若A、B、C、D的编码为0，101，100，00，则编码00101100的解码不唯一。
由哈夫曼树可以得到平均编码长度最短的前缀编码。我们可以根据以往数据通信中字符的频率构造出哈夫曼树，传输数据时根据哈夫曼树进行编码，解码根据哈夫曼树进行解码。
优先级队列 && 堆
优先级队列希望将队列里的元素按照优先级排序，显然AVL树以优先级为关键字肯定能实现需求。不过，大多数情况，我们只关心优先级最高或最低的元素，用AVL树有点杀鸡用牛刀之嫌，堆是能够完成这个任务的一个更精简的数据结构。
堆
堆在逻辑上可以看作是一颗遵循堆序性的完全二叉树，堆序性是指任何节点的关键字都不大于(小于)它的父亲。堆在物理存储上是用顺序表存储的，因为完全二叉树除了最后一层，每一层都是满的，所以可以由位置关系将完全二叉树与顺序表相对应。
因为堆序性，堆中的最大元素(最小元素)必然在堆顶。
当插入节点时，仅需将其插入到末尾，如果违反堆序性递归的将其与其父亲交换位置，目标节点一直往上走，所以这一过程称为上滤。
当删除元素时，用末元素填补空位，然后递归的将其与更大(小)的孩子交换，目标节点一直往下走，这一过程被称为下滤。
初始化堆
将长度为n的顺序表初始化成堆，逻辑上相当于为完全二叉树增加堆序性。有两种简明的做法，一是对所有元素做上滤，二是对所有元素做下滤。两种方法都可以为每个元素增加堆序性。然而这两种方法的效率是完全不同的。
下滤时，节点走的距离是节点的高度，上滤时，节点走的距离是节点的深度，而树形结构下面的节点远比上面的节点多，这就造成了所有节点的深度之和要大于所有节点的高度之和。所以对所有节点上滤的复杂度为，对所有节点下滤的复杂度为。所以初始化堆时应选择对所有节点下滤。