各种树结构相关的知识，不但是很多面试的必考题，同时也是程序世界里很多算法的根基，尝试在这里做一个梳理。

二叉树

二叉树是非常简单的数据结构，具体定义和性质可以网上自行搜索。

对于二叉树最广泛的应用是排序和搜索，比如二叉搜索树（Binary Search Tree），简单的说，就是树中每个节点的左子树中的数据都比当前节点小，而右子树中的数据都比当前节点大。这样的结构对于插入、删除（保持有序）和查找都是非常方便的，但有一个问题，就是在流数据情况下，随着插入的不断进行，树的的高度不可预测。

平衡二叉树（AVL）

AVL数也是一颗二叉搜索树（BST），但附加了某些约束条件，使得它能够随着数据的不断插入，在满足BST基本性质的前提下能够同时动态调整自己的高度，使得树中每个节点的左右子树的高度不会大于1，从而使得整棵树的高度不会过快增长。

AVL是最简单的动态平衡树，平衡的规则也不复杂，参照相关资料手动撸一个AVL的实现不算太难。因此，在一些类似ACM的场景下还是比较实用的。但是由于AVL的动态调整规则比较严格（实时保证树的高度平衡），真正的工业环境下，有时候会遇到频繁调整所带来的严重的性能损耗。

红黑树（Red Black Tree）

红黑树也是一颗二叉搜索树（BST），也能够随着插入、删除操作自动进行高度平衡。但跟AVL不同的是，它的调整规则没有那么严格，它允许左右子树的高度在某些场合下>1（但相差不超过2倍），同时换来的是调整的次数大幅度减小，可以理解为“有限牺牲查找效率，大幅度提高插入或删除效率”。

红黑树的动态调整规则比AVL要复杂得多，手写的成本比较高，另外，它相对于AVL的优势，通常只在工业环境下会体现得比较明显。现实中，STL中的 map 就是用红黑树实现的。

B树（B-Tree）

红黑树每个节点只有两个叉，随着数据量的增长树的高度和动态调整的代价也会越来越大。所以当面临海量数据的时候（如数据库），一个很自然的想法是使用N叉树来实现。这就是B-树（读作“B树”，而不是“B减树”）的基本思想。

BST中的每个节点用健值区分左右子树中健值的大小，比如左子树保存健值小于当前节点的数据，右子树保存健值大于当前节点的数据。在B数中，每个节点可以保存 K-1 个健值，相应的可以区隔出 K 个子树的空间。

跟BST一样，B-树随着节点的插入，也需要做出动态调整以满足特性。BST是采用“旋转”的方式进行调整，B-树则采用“分裂”的方式。B-树中每个节点能保存的健值有一个上界，在健值数量未达到上界时可以直接插入到当前节点（由于需要保持健值有序，因此可能需要调整节点内的健值顺序），如果超过上界，则要对当前节点进行“分裂”操作，分裂会导致该节点的父节点的子树增加，进而可能导致父节点也要进行“分裂”，这种分裂有可能最终传导至根节点，使得整棵树的高度增加1层。

B+树（B+Tree）

相对于BST，B树的高度会明显降低，但是如果仔细想一下，对查找效率的提升并不会跟高度成正比。这是因为，B树每个节点内有多个健值，在当前节点内通常使用二分查找的方式进行搜索匹配，因此在健值数量相等的情况下，B树和BST的搜索复杂度其实是差不多的。那为什么有了BST，还需要B树呢？

在数据库这样的应用场景下，数据量级可能在百万、千万乃至亿级，在这种情况下数据通常是存储在磁盘上的，即便是索引本身也需要保存在磁盘上无法全部Load进内存，这时就需要考虑磁盘IO的性能问题。如果索引采用BST结构，对内存加载策略来说会比较复杂，例如：怎么决定将某个子树保存在一个存储页里？

对B树来说，这个问题就很容易解决，因为单个节点可以足够“大”，可以将整个节点都保存在一个独立页里，这样，每检索一个节点可以进行一次磁盘IO读取相应存储页，由于B树层级通常比较少，因此可以保证在有限次磁盘IO里得到想要的结果。

沿着这个思路，人们开始考虑如何提高每个节点存储信息的效率。无论是BST、还是B树，每个节点除了保存健值以外，还保存了该健值所对应的数据指针（对m阶B树来说，就要有m个指针）。

B+树针对这一点做了优化，除了叶子节点之外，所有的内部节点都不包含数据指针，而只有健值，以及该健值对应的子树指针。内部节点中的每个健值，同时也会出现在子树中（因为不包含该健值对应的数据指针，需要到子树中去继续查找，而B树则不同，找到该健值的同时就可以直接访问到对应数据）。这样一来，B+树的索引部分的信息更加精炼，在同样空间下能保存更多信息。

同时，B+树还有另外一个独立指针，把所有页节点串成一个有序链表，这样在进行范围查找的时候，只需要找到范围下限所对应的节点，就可以通过横向链表来遍历其他节点（而不需要再做树查找）。

跳跃表（SkipList）

B+树的底层是有序列表，同时还有树结构索引，看起来能解决很多问题，但唯一的问题都是比较“复杂”，例如：现场手写个B+树？

相比之下，跳跃表采用了非常简单粗暴的实现方式，但能够获取到跟AVL、B树等差不多的查找速度。

跳跃表的基本思路这里不多做介绍了，网上到处都能找得到。唯一比较有意思的是它在新节点插入时，使用“随机函数”来决策插入深度。

    int random_level()
    {
        int k = 1;
        while (random(0, 1))
            k++;
        return k;
    }

这个函数的巧妙之处是，它每次循环都有1/2的概率返回真，因此通过这个函数来返回插入深度的结果，就是在概率上，第二层节点大致是一层节点数的1/2，而三层节点大致是二层节点的1/2，以此类推。因此在查找上，能够获得近似 O(lgN)的效率。

现实工业中，Redis中的有序数据就是通过跳跃表来实现的。