高级树结构
导语：总结所有的树结构
1 哈希树
哈希树（hash tree， Merkle tree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。
哈希树的概念由瑞夫*墨客于1979年申请专利，故亦称墨克树（Merkle tree）。
概念：哈希树中，哈希值的求取通常使用诸如SHA-2的加密哈希函数，但如果只是用于防止非故意的数据破坏，也可以使用不安全的校验和获取，比如CRC。
哈希树的顶部为顶部哈希（top hash），亦称根哈希（root hash）或主哈希（master hash）。以从P2P网络下载文件为例：通常先从可信的来源获取顶部哈希，如朋友告知、网站分享等。得到顶部哈希后，则整棵哈希树就可以通过P2P网络中的非受信来源获取。下载得到哈希树后，即可根据可信的顶部哈希对其进行较验，验证数据是否完整，是否遭到破坏。
2 二叉树
在计算机科学中，二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
二叉树的第i层至多拥有$2^{i-1}$个节点；深度为k的二叉树至多共有$2^{k+1}-1$个节点（定义根节点所在深度k0=0），而总计拥有节点数符合的，称为“满二叉树”；深度为k的n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度k的满二叉树，序号为1到n的节点一对一对应，称为完全二叉树。对任何一颗非空的二叉树T，如果其叶片（终端节点）数为n0，分支度为2的节点数为n2，则n0=n2+1。
与普通树不同，普通树的节点个数至少为1，而二叉树的节点个数可以为0；普通树节点的最大分支没有限制，而二叉树节点的最大分支度为2；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。
二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆。
-
完全二叉树：在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点；则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为$log_2n+1$。深度为k的完全二叉树，至少有$2^{k-1}$个节点，至多有$2^{k}-1$个节点。
-
二叉搜索树：也称二叉查找树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：
-
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为$O(log~n)$。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如
-
集合：集合是一组可变数据量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同（若使用的语言支持继承）。列表（或数组）通常不被人为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。集合的种类包括列表、集、多重集、树和图。枚举类型可以是列表或集。
-
多重集：是数学中的一个概念，是集合概念的推广。在一个集合中，相同的元素只能出现一次，因此只能显示出有或无的属性。在多重集中，同一个元素可以出现多次。正式的多重集的概念大约出现在1970年代。
-
关联数组：又称映射（Map）、字典（Dictionary）是一种抽象的数据结构，它包含类似于（键、值）的有序对。一个关联数组中的有序对可以重复（C++中的multimap），也可以不重复（C++中的map）。这种数据结构包含以下几种常见的操作：
- 向关联数组添加配对
- 从关联数组删除配对
- 修改关联数组内的配对
- 根据已知的键寻找配对
字典问题是设计一种能够具备关联数组特性的数据结构。解决字典问题的常用方法，是利用散列表，但有些情况下，也可以直接使用二叉查找树或其他结构。许多程序设计语言内置基本的数据类型，提供对关联数组的支持。而内容寻址存储器则是硬件层面上实现对关联数组的支持。
-
-
二叉堆：是一种特殊的堆，二叉堆是完全二叉树或者近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个节点的键值，且每个节点的左子树和右子树都是一个二叉堆。当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个节点的键值时为“最小堆”。
3 红黑树
是一种自平衡二叉查找树，是计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫*贝尔发明，被称为“对称二叉B树”，它现代的名字源于1978发表的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在$O(logn)$时间内完成查找、插入和删除，这里的n是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或者黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
- 节点是红色或者黑色。
- 根是黑色。
- 所有叶子都是黑色。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径不能有连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点。
这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个高度上的理论上限允许红黑树在最坏的情况下都是高效的。
最短的可能路径都是黑色节点，最长的可能路径有交替的红色或黑色节点。
用途和好处
- 红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是它们在时间敏感的应用，如实时应用中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。
- 红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构建关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了$O(logn)$的时间之外，红黑树的持久版本对每次插入或删除需要$O(logn)$的空间。
- 红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在时间中不经常使用。
- 红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作的时少量的旋转操作，整体来说性能要优于AVL树。
4 B树
在计算机科学中，B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
在B树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如，在一个2-3 B树（通常简称2-3树），每一个内部节点只能有2或3个子节点。
B树中每一个内部节点会包含一定数量的键，键将节点的子树分开。例如，如果一个内部节点有3个子节点（子树），那么它就必须有两个键： a1 和 a2 。左边子树的所有值都必须小于 a1 ，中间子树的所有值都必须在 a1 和a2 之间，右边子树的所有值都必须大于 a2 。
通常，键的数量被选定在d和2d之间。其中d是键的最小数量，d+1是树最小的度或分支因子。在实际中，键值占用了节点中大部分的空间。因数2将保证节点可以被拆分或组合。如果一个内部节点有 
一个节点的分支（或子节点）的数量会比存储在节点内部键值的数量大1。在 2-3 B树中，内部节点将会存储1个键值（带有2个子节点）或2个键值（带有3个子节点）。一个B树有时会被描述为 {\displaystyle (d+1)-(2d+1)}
一个Ｂ树通过约束所有叶子节点在相同深度来保持平衡。深度在元素添加至树的过程中缓慢增长，而整体深度极少地增长，并导致所有叶子节点与根节点距离加1。
在存取节点数据所耗时间远超过处理节点数据所耗时间的情况下，Ｂ树在可选的实现中拥有很多优势，因为存取节点的开销被分摊到里层节点的多次操作上。这通常出现在当节点存储在二级存储器如硬盘存储器上。通过最大化内部里层节点的子节点的数量，树的高度减小，存取节点的开销被缩减。另外，重新平衡树的动作也更少出现。子节点的最大数量取决于，每个子节点必需存储的信息量，和完整磁盘块的大小或者二次存储器中类似的容量。虽然 2-3 树更易于解释，实际运用中，Ｂ树使用二级存储器，需要大量数目的子节点来提升效率。
变体：
B+树：这些键值的拷贝被存储在内部节点：键值和记录存储在叶子节点；另外，一个叶子节点可以包含一个指针，指向另一个叶子节点以加快顺序存取。
B*树：分支出更多的内部邻居节点以保持内部节点更密集地填充。此变体要求非根节点至少2/3填充，而不是1/2.为了维持这样的结构，当一个节点填满之后将不会再立即分割节点，而是将它的键值与下一个节点共享。当两个节点都填满之后，分割成3个节点。
计数B树存储：每一树都带有一个指针和其指向子树的节点数目。这就允许了以键值为序快速查找第N笔记录，或者统计2笔记录之间的记录述目，还有其他很多相关的操作。
5 AVL树
AVL树是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两颗子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是$O(log n)$。增加和删除元素的操作在可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0、-1的节点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的，并且需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
6 伸展树
是一种自我平衡的二叉查找树，它能在均摊$O(log n)$的时间内完成基于伸展（splay）操作的插入、查找、修改和删除操作。是在1985年发明的。
在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单的方法，在每次查找之后对数进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自我调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。
优点
伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。（用于数据库设计过程中，利用相似的思想设计一个计算器，每次查询自增，查询时首先计数器大的开始查询）
- 可靠的性能–它的平均效率不输于其他平衡树
- 存储所需的内存少–伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
缺点
伸展树最显著的缺点是它有可能会变成一条链。例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的$O(log n)$
即使以”只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。
7 散列表
散列表，也叫哈希表，是根据键直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查询速度。这个映射函数称作散列函数，存放记录的数组称作散列表。
基本概念：
- 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需要比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表；
- 对不同的关键字可能得到同一散列地址，即k1!=k2，而f(k1)=f(k2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词。综述所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
- 若对于关键字集合中的任一个关键字，经散列函数映射到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就使得关键字经过散列函数得到一个“随机的地址”，从而减少冲突。