这里把树单独拿出来是因为树实在是太多种类了，也挺值得研究一下的
这里建议大家学习树的时候，能明确的知道一棵树在插入和删除节点之后的形态，最好能在纸上画一下，这样才能检查算法是否正确
< 我们经常需要面对一些复杂性，这时我们需要细致的分析来理清头绪 >
< 所有业务逻辑，都可以浓缩成算法，然后你会发现这个算法在很久以前就已经有人提出并实现了。所以，让我们好好研究下数据结构和算法吧 >
< 数据结构和算法固然重要，但是明白它们解决问题的出发点更重要 >
< 凡事，积累则快，应付则慢。想要快，则需要早早积累 >
- 二叉查找树(BST)
- 平衡二叉树(AVL)
- 红黑树(RBT)
- 哈希树
- B树
- B+树
- B*树
- Treap树
- Trie树
- R树 - 矩阵树
- 伸展树(Splay Tree)
- SB树 - Size Balanced Tree，由中国广东中山纪念中学的陈启峰发明
- Merkle Tree - Dynamo中用来同步数据一致性的算法
- LSM Tree - Log-Structured Merge-Trees，一种牺牲一定的读性能来大幅提高写性能的日志结构合并树
也就是 左节点 < 根节点 < 右节点 的二叉树
其实除了二叉查找树之外，AVL，红黑树，Treap，伸展树等都属于平衡二叉树
-
AVL树 - 是最先发明的自平衡二叉查找树
-
其平衡性最高
-
应用场景：查询较多，插入和删除较少的情况
-
-
红黑树 - 平衡性可能不如AVL树，但是其统计性能优异
- 红黑树本质上是一棵二叉查找树，只是需要再满足下面这几个特点：
- 每个节点非红即黑
- 根节点是黑色
- 每个叶节点都是黑色（包括NULL节点）
- 所有红节点的子节点都是黑色 - 为了保证不会有连续的两个红色节点
- 每个节点到其叶子节点的所有路径上都包含相同数目的黑色节点
-
上面五条保证了最坏情况下的最长路径不会大于两倍的最短路径，这也就是红黑树的核心诉求：控制最坏情况下的最长路径
-
红黑树实现平衡的核心在于为所有节点着色，并且通过以上五条来对节点颜色进行调整，并不是完全实现平衡，所以其平衡性是以颜色来驱动而非节点深度（所以其平衡性不如AVL树）
-
应用场景：查询，插入和删除都较多的情况
-
哈希树 - 一种附带哈希表的平衡二叉树
其实B树的出现还是因为成本的问题，目前内存的成本还是普遍高于磁盘，而因为大量数据不可能全部保存于内存中（例如数据库的索引），必然有一部分数据要转移到磁盘中，而这时对这些数据的操作，则需要考虑使用B类树来实现 所以也可以假设，如果有一天内存的成本已经足够低，生产内存已经和当前生成磁盘的成本一样的话，那么那个时候，可能B树就没有现在这样有用武之地了 所以说一切的一切，还是都在考虑成本和当前形势情况下做出的当下的最优选择（包括依赖于目前存储器的设计和计算机存取数据的方式，这些东西不是一成不变的，以后可能会发生变化），并不存在一个绝对完美的选择。选择是一直都在变化的。
因为B类树常常作为索引来使用，而衡量一个索引的最重要的指标就是在操作过程中I/O操作次数是否尽量少（比如为了尽量减少磁盘的读取次数，B树结构中的节点普遍设为页的大小，这样一个节点一次I/O就可以完全载入）
BTree -> B+Tree -> B*Tree 的整个演化就是减少节点空间的分配，减少分配新节点的概率（也就是尽量减少分裂节点的操作）
-
B树 - 几乎是所有数据库的默认索引结构，一种磁盘存储器的树算法
-
B+树 - 是一种读写代价更低，查询效率更稳定（因为非终端节点都是关键字的索引，所以每个关键字的查询长度相同）的B树的变形，适应于文件系统
-
B* 树 - 是B+树的变体，最主要区别在于节点中关键字使用率为(2/3)*M（M为树的阶）
-
Treap树 - 一种二叉树与堆特征结合的树
-
Trie树 - 一种单词查找树，适合于匹配查找（效率高于哈希树）
-
R树 - Rectangle Tree - A dynamic index structure for spatial searching
-
伸展树
-
SB树
-
Merkle Tree , 又称为 Merkle Hash Tree, 因为其所有节点都是哈希值
-
是Amazon Dynamo中用来同步数据一致性的算法
-
Git在集群机器中的文件同步也是采用Merkle Tree
-
在分布式环境下进行比对和校验时，Merkle Tree会大大减少数据的传输量和计算复杂度
-
-
LSM Tree , 一种redis和HBase中使用的树