Tree在现代操作系统内核、数据库工具以及各类编程语言提供的基础结构中有广泛的应用，本文将分析几种常见的树结构及其特点。
二叉查找树（BST）
二叉查找树又称有序二叉树，满足以下性质：
- 所有非叶子节点最多拥有两个子节点（left/right）
- 若节点N的左子树不为空，则左子树的值均小于该节点的值；
- 若节点N的右子树不为空，则右子树的值均大于该节点的值；
- 任意节点的左右子树也分别是二叉查找树；
- 任意节点的值不相等。
二叉查找树的查找从根节点开始，如果值相等则命中，小于则查找左子树，大于则查找右子树。如果BST的结构对称，即左右子树的节点数差不多（平衡），该树的查找性能逼近二分查找。BST对比连续内存空间的二分查找，优点在于，BST的插入删除不需要挪动大段内存数据。但BST树在经过数次插入删除之后，结构可能会改变（非平衡），如下图所示：
在这种情况下，二分查找树的查找性能会大幅下降，因此引出平衡二叉树（AVL）的概念。
平衡二叉查找树（AVL）
平衡二叉树本质上是加了约束的二叉查找树，其在二叉查找树的定义上加了如下性质：
- 左右子树的深度之差的绝对值不超过1；
- 左右子树仍为平衡二叉树。
左右子树深度之差即为该节点的平衡因子，绝对值小于1保证了结构上的对称。上图中b即为平衡二叉树。AVL树为了严格保证平衡性，在插入删除时，需要对子树进行一定次数的旋转，即保证了查询性能，却牺牲了插入删除的性能。在此基础上，弱平衡的概念（红黑树）被引入。
红黑树（RBT）
红黑树取消了平衡树（AVL）中用平衡因子的约束，转而使用红黑颜色来维持二叉树的平衡性（弱平衡）。红黑树满足以下约束：
- 每个节点非黑即红；
- 根节点一定是黑色；
- 每个叶节点（NIL节点、空节点）一定是黑色；
- 如果节点N为红色，则它的两个子节点一定是黑色；
- 从任一节点到其每一叶节点所途径的黑色节点数目一定相同。
最后一个约束是保证红黑树平衡的关键约束。这五点约束共同保证了红黑树的关键性质：从根节点到叶节点的最长路径不大于最短路径的两倍（弱平衡性）。红黑树上每一个节点包含5个关键字–color，key，left，right，p。若某一个关键字没有值，则为NIL。如下图所示：
红黑树应用广泛，比如JAVA中TreeMap的实现，JDK1.8以上HashMap的扩容等。
旋转操作
旋转分为左旋和右旋。对于红黑树而言，在我们实现某些操作中可能会出现红色右链接或则两个连续的红链接，这时候就要通过旋转修复。
其过程如下图（右旋）所示：
B树
二叉树中，对于每一个节点而言，其子节点最多只有两个，而当子节点数M > 2时，就是B树。该结构是为磁盘存储而设计的数据结构，是一种平衡多路查找树。由上面的分析可以得知，若存储同样的节点，B树的深度最浅，AVL次之，红黑树最高，深度越浅，读取磁盘IO的次数就越少。
B树满足以下约束：
- 任意非叶子结点最多只有M个儿子（M>2）；
- 根结点的儿子数为[2, M]；
- 除根结点以外的非叶子结点的儿子数为[M/2, M]；
- 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
- 非叶子结点的关键字个数=指向儿子的指针个数-1；
- 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
- 所有叶子结点位于同一层。
一个M = 3的B树结构如下图所示：
对B树进行检索时，会从根节点开始，对节点内的关键字进行二分查找，如未找到，则进入查找字所在范围对应的子节点进行查找，直至命中或者至叶子节点。由该过程可以看出，其检索性能等价于二分查找性能O（logN）。
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。
B+树
B+树是由B树修改而来，与B树的不同点在于：
- 非叶子结点的子树指针与关键字个数相同；
- 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B树是开区间，也就是说B树不允许关键字重复，B+树允许重复）；
- 所有叶子节点增加一个链指针；
- 所有关键字都在叶子节点出现(稠密索引，且链表中的关键字恰好是有序的)。
对于B+树而言，非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储(关键字)数据的数据层。这样的特性使得B+树更适合文件系统。B+树结构如下图所示：
B+树由于关键字只在叶子节点中储存，这样使得B+树的检索命中只会在叶子节点发生。
B*树
B*树是在B+树的非根和非叶子结点再增加指向兄弟节点的指针。
B*树定义了非叶子节点的关键字字数至少为M的2/3倍。
B*树结构如下图所示：
