其他二叉树
平衡二叉树-AVL 树(没有很严格)
平衡二叉树（balanced binary tree）,又称 AVL 树。它或者是一棵空树,或者是具有如下性质的二叉树：
- 它的左子树和右子树都是平衡二叉树，
- 左子树和右子树的深度之差的绝对值不超过1。
平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是，树的结构是无法预料的，随意性很大，它只与节点的值和插入的顺序有关系，往往得到的是一个不平衡的二叉树。在最坏的情况下，可能得到的是一个单支二叉树，其高度和节点数相同，相当于一个单链表，对其正常的时间复杂度有O(log(n))变成了O(n)，从而丧失了二叉排序树的一些应该有的优点。
###
红黑树
红黑树的五个基本原则：
- 首先它一颗平衡树，每个节点是红色或黑色的。
- 根节点是黑色的。
- 每个叶节点（null）是黑色的。
- 如果一个节点是红色的，则它的两个子节点是黑色的。
- 对每个节点，从该节点到其所有后代叶节点上的简单路径，包含相同数目的黑色节点。
比较重要的是第4点和第5点，因为它可以保证我们树的最长路径不超过最短路径的两倍。也就是说一个n个节点的红黑树，它的高度至多为2lg（n+1），虽然不是严格平衡，但至少查找的效率还是可以接受的。
红黑树在高度方面不像AVL有个左右子树高度差不超过1的限制，同时红黑树的维护效率比AVL高很多。红黑树需要旋转的次数较少。
Java中的map就是通过红黑树来实现的。
Question：动态数据结构支持动态地数据插入、删除、查找操作，除了红黑树，还有哪些？比较优劣和场景。
动态数据结构是支持动态的更新操作，里面存储的数据是时刻在变化的，通俗一点讲，它不仅仅支持查询，还支持删除、插入数据。
而且，这些操作都非常高效动态数据结构有链表，栈，队列，哈希表等等。
链表适合遍历的场景，插入和删除操作方便；
栈和队列可以算一种特殊的链表，分别适用先进后出和先进先出的场景。
哈希表适合插入和删除比较少（尽量少的扩容和缩容），查找比较多的时候。
红黑树对数据要求有序，对数据增删查都有一定要求的时候。
B树（平衡多路查找树）
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构;
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理，把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;
目的：使树的层级减少达到快速查找数据的目的。
适合：外部存储。磁盘。
##B+树
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。
- 特点
1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
哈弗曼树
定义：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。
构造：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
- 将w1、w2、…，wn看成是有 n 棵树的森林(每棵树仅有一个结点)；
- 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
- 从森林中删除选取的两棵树，并将新树加入森林；
- 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。