在计算机中，树随处可在，可说是图论和计算机科学中的重中之重，理解树的结构、树的思想和树的优异性质对于程序设计大有裨益！

一、前言

我们都知道，数组的特点是查询快，直接可以通过下标获取元素，时间复杂度为O(1)；但是当我们在指定的位置插入元素或者删除元素的时候，数组下标和所对应的元素是需要重新排列的，所需要的时间复杂度为O(n)！

所以对于频繁的插入、删除的场景，不建议采用有序数组！

可能有的朋友会想到，对于需要频繁的插入、删除的场景，可以使用链表结构，因为对于链表结构来说，在进行插入或者删除的时候，只需要改变元素的前驱或者后继节点的引用就可以了，所需要的时间复杂度为O(1)；但是如果我们想查询指定的内容时候，需要遍历链表元素并逐步判断，直到查找到目标元素为止，所需要的时间复杂度为O(n)！

所以对于查找频繁的数据，不建议使用链表！

哪有没有一种查询速度快、插入删除也很快的一种数据结构呢？

树就是其中一个！树这种数据结构，在计算机领域中有着很多的实际应用！比如说：

• mysql 数据库的索引就是 B+ 树结构，查找效率极高；
• Windows OS 的文件系统结构也是采用 B+ 树进行存储的；
• Linux 的文件系统结构同样也是采用 B+ 树进行存储的；

如下图，看起来像一颗树，但不是树结构：

三、二叉树

在计算机科学中，二叉树（英文名：Binary Tree）是每个结点最多有两个子树的树结构，通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

按照这个定义，在逻辑上二叉树可以进行五种基本形态的分类：

• 1、空二叉树；
• 2、只有一个根结点的二叉树；
• 3、只有左子树的二叉树；
• 4、只有右子树的二叉树；
• 5、拥有左、右子树的二叉树；

在实际的开发中也有所应用，完全二叉树会使用二叉查找树算法（会在下文介绍），来保证查找的数据是有序的，叶子节点可以按从上到下、从左到右的顺序依次添加到数组中。知道一个节点的位置，就可以轻松地算出它的父节点、孩子节点的位置。

满二叉树，特性完全同完全二叉树，但是比完全二叉树更严格，每个叶节点到达根路径所需的长度都相同！而完全二叉树的k-1层可以为叶节点！

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

像 JDK1.8 中 HashMap、TreeMap 等就使用到了红黑树实现。

3.2、二叉查找树

上面介绍了完全二叉树、满二叉树、平衡二叉树都属于特殊类型的二叉树，需要我们从逻辑上去控制才可以满足要求！

上文中我们说到，二叉树的出现就是为了解决查询效率问题，按照二分进行查找，每次查询只需要选择其中一个子树就进行查找，从而减少查找次数，提升查询效率！

那么我们如何进行二分查找呢？

这就要求查找的数据必须是有序的，每次查找、插入删除时都要维护一个有序的数据集，于是就有了二叉查找树这个概念，英文全称 Binary Search Tree，简称 BST。

二叉查找树，也被称为二叉排序树，可以说是从算法层面来定义二叉树结构，这种算法思路适用于所有的二叉树结构，特性如下：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 它的左、右子树也分别为二叉查找树；

如果二叉查找树变成了单支树，查询效率就大大折扣了，于是就有平衡二叉查找树的出现！

3.3、平衡二叉查找树

平衡二叉查找树，又称 AVL 树，因为算法的发明者为Adel’son-Vel’skii和 Landis，被称为 AVL 树来自于大神的姓名缩写组合。

它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：

• 它的左子树和右子树都是平衡二叉树;
• 且它的左子树和右子树的深度之差的绝对值（平衡因子 ） 不超过1；

也就是说 AVL 树每个节点的平衡因子只可能是-1、0和1（平衡因子算法：左子树高度减去右子树高度）。

那么如何保证二叉查找树在添加元素的同时保证节点平衡呢？

基本思想就是：当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉查找树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。

所谓最小不平衡子树是指：离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

当新插入的节点导致树结构发生失衡就会进行调整，主要操作有左旋转、右旋转操作！

3.3.1、绕某元素左旋转

从图中可以看出，在插入数据 30 之前，左图 BST 树只有 80 节点的平衡因子是 1（左子树高度减去右子树高度），但整棵树还是平衡的。

插入 30 之后，80节点的平衡因子就成为了 2，此时平衡被破坏，需要进行调整，绕节点 50 进行右旋转，最终树型结构变成右图。

右旋转场景：当树中节点 X 的左孩子的左孩子上插入新元素，且平衡因子从 1 变成 2 后，就需要绕节点 X 进行右旋转。

3.3.3、绕某元素的左子节点左旋转，接着再绕该元素自己右旋转

很多时候，插入元素一次调整满足不了要求，如下图就是左旋与右旋的结合，具体操作时可以分解成这两种操作，只是围绕点不一样而已。

由此可见，通过左旋转、右旋转操作，平衡二叉树不会出现普通二叉查找树的最差情况，其查找的时间复杂度为O（logN）！

在查询的时候，操作与普通二叉查找树上的查找操作相同；插入的时候，每一次插入结点操作最多只需要单旋转或双旋转，总体上插入操作的代价仍然在O（logN）级别；如果是动态删除，删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子，最多可能需要O（logN）次旋转。

为了解决尽可能少的旋转调整，红黑树出现了！

3.4、红黑树

红黑树，英文名称：red-black tree，简称 RBT！红黑树也是基于平衡二叉树结构的一种实现，但是它的平衡指标没有像 AVL 算法那样要求很严格，并不是高度平衡但基本平衡，特性如下：

• 每一个结点要么是红色，要么是黑色；
• 根结点是黑色的；
• 所有叶子结点都是黑色的（实际上都是Null指针，下图用NIL表示）。叶子结点不包含任何关键字信息，所有查询关键字都在非终结点上；
• 每个红色结点的两个子节点必须是黑色的。换句话说：从每个叶子到根的所有路径上不能有两个连续的红色结点；
• 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点；

红黑树，在插入的时候，与 AVL 一样，结点最多只需要2次旋转；在删除的时候，因为没有像 AVL 那样高度平衡的要求，删除一个结点最多只需要3次旋转操，可见红黑树的删除操作代价要比 AVL 要好的多；因为不是高度平衡，在查询方面，红黑树在查询效率方面稍逊于 AVL，但是比二叉查找树强很多！

在 JDK 中就有很多红黑树的具体实现，最典型的就是 JDK1.8 中的 HashMap，当冲突链表长度大于 8 时，链表就会以红黑树结构存储。

3.5、哈夫曼树

哈夫曼树是一种特殊结构的二叉树，主要由哈夫曼编码实现，内容定义如下：

给定N个权值作为N个叶子结点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为Huffman树。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在 B 树应用到数据库中的时候，数据库充分利用了磁盘块的原理，把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

4.2、B+ 树

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

一棵m阶的B+树和m阶的B-树的差异，内容如下：

• 有n棵子树的结点中含有n个关键字；（B~树是n棵子树有n+1个关键字）
• 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接；（B~树的叶子节点并没有包括全部需要查找的信息）
• 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字；（B~树的非终节点也包含需要查找的有效信息）

例如：下面就是一棵3阶B+树，我们可以和B~树做一个明显的对比，如图所示：

B*树相比B+树的优势：在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而在非根和非叶子结点上增加指向兄弟的指针，可以向兄弟节点转移关键字的特性使得B*树的分解次数变得更少！

五、总结

关于树的故事，基本介绍完了，内容比较多，尤其B树模型，比较深奥复杂，有兴趣的朋友可以自己研究一些，如果有理解不当的地方，欢迎网友指出！

六、参考

1、百度百科 – 树

2、维基百科 – 树

3、掘金 – 西召 – 树结构与Java实现

4、掘金 – 张拭心 – 二叉树、平衡二叉树、二叉查找树

5、iteye – Heart.X.Raid – 动态查找树比较

6、知乎 – 勤劳的小手 – 平衡二叉树、B树、B+树、B*树