树的演化

这是训练营的第二周，也持续的做了几十道算法题，每道题自己都竭尽全力的去找尽可能多的解法，且每个解法都实现出来。此前一直对树这个数据结构理解的不是很彻底很到位，以及围绕树相关的算法也感觉很飘忽很神秘，所以本周就萌生了全方位总结树这个数据结构以及和它相关的算法。

为什么需要树？当在面临大量的输入数据时，线性表的访问时间就变的很慢了，有没有一种数据结构可以加速访问呢，树就是其中一种，树可以将大部分的操作都优化到 O(logn) 的时间复杂度，可以大大提升效率；此外，我们在日常生活中无时无刻不在使用树，比如想中午吃什么的时候，我们不自觉的构建了一颗决策树，操作系统的文件系统等；（在这篇总结中，不再罗列概念）

树的数学性质

有时候了解更多关于树的数学性质有助于解决很多问题，所有的数学性质是直接可以使用的

高度为 h 的二叉树至多有 2^h 个叶子结点
高度为 h≥0 的二叉树至少有 h+1 个结点
高度不超过 h(≥0) 的二叉树至多有 2^(h+1)-1 个结点
含有 n≥1 个结点的二叉树的高度至多为 n-1
含有 n≥1 个结点的二叉树的高度至少为 logn，因此其高度为 Ω(logn)
高度为 h 的满二叉树，共有 2^(h+1)-1 个结点
满二叉树共有 2^h 个叶子
满二叉树共有 2^h-1 个内结点，内结点个数比叶子少1
完全二叉树第 h 层的从左到右第 k 个结点的编号为 2^h + k - 1
完全二叉树叶子个数或者和内结点个数相等或者多1
完全二叉树通过本结点的编号可以快速得到父结点、左右孩子的编号；编号为i的父节点为 i/2, 左子节点为 2*i, 右子节点为 2*i + 1（这个性质在堆中得到了很好的应用）
etc.

为什么会有那么多特殊化的树

这是本次总结想要好好分析的。

树的一般化定义是：一棵树是一些节点的集合。这个集合可以是空；若非空，一个树由根节点以及0个或多个非空子树组成，每一棵子树都和根有一条有向边所连接；一颗树是N个节点和N-1条边的集合。从树的定义中，我们可以推论出很多树的数学性质，例如上面描述的。

树的演化过程，其实是从一般到特殊化的过程，在演化中出现各种特殊的树，来解决不同种类的问题。但是一颗一般化的树，在一些特殊的场景下，并不能为我们解决很多问题

从二叉树开始：在树中如何利用二分查找的思想

二叉树是一颗每个节点最多有两个孩子的树，分别是左孩子和右孩子。可以看出，我们在树的基础上做了限制，二叉树为我们提供了每次二分的可能，也简化了树以及各种操作的实现。在使用这颗二叉树的时候，我们可以尽可能的去构造这颗树，但是怎么解决快速查找的问题，尤其是在有大量数据存在时？如果查找的时间复杂度还不如链表，那就没有意义了。

我们知道在一个排好序的数组中进行二分查找的时间复杂度是 O(logn), 是非常高效的（40亿量级的数据，只需要32次左右的查找）；所以将二分查找的思想应用在二叉树中，就是一颗二叉查找树，它是这么一棵树：在树中的任意一个节点，其左子树中的每个节点，都要小于这个节点的值，其右子树的每个节点，都要大于这个节点的值。可见，二叉查找树在二叉树的基础上又做了限制，更加特殊化了。

为什么二叉查找树的查找效率高？我们首先来分析一颗完全二叉查找树，这是一种比较理想的状态，因为树的高度是 logn, 也是二叉查找树所有形态中高度最小的树；我们试着来分析一下：

// 对于一颗包含 n 个节点完全二叉树
// 1. 除了最后一层外，每一层的节点是上一层节点个数的2倍; 一般的，第一层是1个节点，第二层是2个节点，第三层是4个节点，以此类推
// 2. 最后一层节点的个数在 1 ~ 2^(L-1), 其中 L 表示最大层数
// 综上可知，n 满足
n <= 1 + 2 + 4 + ... + 2^(L-2) + 2^(L-1)
n >= 1 + 2 + 4 + ... + 2^(L-2) + 1

=> log(n+1) <= L <= log(n) + 1

可知，L 的最大值是 log(n) + 1, 高度h最大是 log(n); 所以在查找某个元素时，最大查找次数是 log(n), 故而时间复杂度是 O(logn), 很高效；同理，插入、删除操作时间复杂度也是 O(logn)

上面我们说了是一种理想状态，因为数据特点的不同，我们构造出来的二叉查找树可能会退化成链表结构，比如每次都一直插入左子树或一直插入右子树，这个时候查找时间复杂度就是 O(n), 这是不可接受的。那怎么办呢？

问题出在了构建二叉查找树的时候，在插入和删除的时候会影响二叉查找树的形态，所以我们需要控制动态构建的这个二叉查找树，让他保持平衡，以便于更加接近一颗完全二叉查找树，这样就是一个比较好的状态。为了解决二叉查找树的时间复杂度退化问题，保持平衡，我们可以动态的维护一颗平衡二叉查找树（AVL），这个就是我们想要的。

平衡二叉查找树是一颗任何节点的左右子树高度相差不超过1的二叉查找树，可见AVL是对二叉查找树的进一步限制。但是AVL的实现还是比较复杂的，在维护平衡时，涉及到了多种情况和各种旋转操作。

AVL的实现有很多，如红黑树，伸展树，AA树，treap 树等，这些树的工程实现普遍都很复杂，每一个都值得写一篇长长的总结。

对树来说，其实落在工程中的实现是像红黑树这种性能表现比较好的数据结构，通过一步步的分析，我们也知道了为什么不在工程中直接使用一般化的二叉查找树，而是使用AVL。无非是分析各种情况下，给出的这个数据结构和算法的设计，在最好和最坏的情况下有多大差别，我们是否能容忍最坏情况的发生，这个需要根据工程中的实际场景来权衡。数据结构和算法没有哪一个是完美的，只有最合适的，我们要分析实际场景。

一个特殊化的完全二叉树：堆

完全二叉树是一个平衡树，所以高度最大是 O(logn)，所以堆具有这个性质；此外，堆规定了每个节点的值必须大于等于（小于等于）其子树中每个节点的值；可见，堆是一颗受限的完全二叉树。

堆适合使用数组来存储。更加详细的分析参考：堆和堆排序

B+Tree：由二叉查找树演变而来的多叉索引树

有这样一个实际应用，我们需要一个数据库，要将数据持久化存储在磁盘上，并且支持： 1. 根据某个值快速查找数据 2. 根据某个区间值来查找数据 3. 希望能够按顺序输出某个区间内的数据，升序和降序

我们可以构建这样一颗平衡二叉查找树，叶子节点存储数据，非叶子节点只存储索引，这样索引和数据就可以分开存储了；但是二叉查找树可以快速查找数据，但是无法进行区间查找和按序输出；我们可以将叶子节点用双向链表串联起来，这样就可以支持区间查找和顺序输出了。

存在另外一个问题，因为数据库有存储大量数据的需求，比如可能是上亿条数据，如果把索引节点都放在内存中是不现实的，我们希望索引不占用太多的内存空间，那只能把一部分索引放在内存，一部分放在磁盘，等需要的时候再把磁盘的索引载入内存（时间换空间的思路，牺牲了一定的时间）磁盘的访问速度远低于内存访问速度；我们知道平衡二叉查找树的查找是 O(logn),采用这种方式后，会带来一个问题，就是需要多次访问磁盘来加载索引文件，会严重降低查找的速度，一次磁盘IO需要10ms左右，对于一个有上亿数据量的数据查找，需要大概20次左右的磁盘IO，就是200ms，所以真的是很慢；

那如何解决平衡二叉查找树带来的磁盘IO过多的问题呢？答案是降低树的高度，树的高度减少了，磁盘需要IO的次数就对应减少了，同时还能更好的利用内存的局部性原理，增加树的度可以减少树的高度，比如每个树的度最大是1000时；这样就形成了一颗m叉的平衡查找树。这正是B+树的核心，也是众多存储引擎使用的数据结构。

当然，B+树在存储引擎的实现要复杂很多，要考虑的点也有很多，专门的探讨放在后续的总结中。

通过分析各种类型的树及其操作，很清楚的知道了他们的由来、特性、适用的场景以及它能解决的问题，而这个也是我们学习数据结构和算法最核心的地方；在理解了这些的基础上，然后用代码去实现出来并不断优化工程代码。

最后更新于3年前