树与数据结构

什么是数据结构

在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。数据结构可透过程序语言所提供的数据类型、引用及其他操作加以实现。一个设计良好的数据结构，应该在尽可能使用较少的时间与空间资源的前提下，支持各种程序运行。正确的数据结构选择可以提高算法的效率；不同种类的数据结构适合不同种类的应用。常用的数据结构有数组（Array），链表（Linked），队列（Queue），堆（Heap），栈（Stack），树（Tree），图（Graph），散列表（Hash）。

什么是树

树（Tree）是一种抽象数据类型（ADT）或是这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，它具有以下的特点：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；子树与子节点区别，子节点，指的是一个树上的一个节点，而子树指的是这个节点和包括属于这个节点的所有子节点，只有是叶子节点的时候，子树才等于子节点。

树的一些专业术语（概念）

节点的度：一个节点含有的子树的个数称为该节点的度（该节点，有多少个子节点）；

树的度：一棵树中，最大的节点的度称为树的度（所有子节点中度数最大的那个节点的度数）；

叶子节点或终端节点：度为零的节点（也就是没有子节点的节点）；

非终端节点或分支节点：度不为零的节点；

父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0，高度为整个树的高度；

高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶（叶子节点）的高度为0；

堂兄弟节点：父节点在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：由m（m>=0）棵互不相交的树的集合称为森林；

在图中A为根节点。A节点的度是2，因为他有B和C两个子树（子节点）。没有父亲节点，B和C是A的子节点（孩子节点），层次是第一层，深度是0，高度是4，可以说他是这个树上所有节点的祖先，其他节点都是他的子孙。
图中B节点是分支节点（非叶子节点，非终端节点），他的父节点是A，B与C是兄弟节点，他是第二层，深度是1，高度是三，D，E，F是他的子节点。
图中的F节点叶子节点（终端节点），他的父节点是B，兄弟节点是D和E，他是第三层，深度是2，高度是0（他是叶子节点，叶子节点高度为0），F与G和H是堂兄弟节点。
图中的M节点是分支节点，他的父节点是G，与L是兄弟节点，他是第第四层，深度是3，高度是1，兄弟节点是L，堂兄弟节点是I，J，N节点，子节点是O。
图中的节点K是叶子节点，他的父节点是I，的没有兄弟节点，他的堂兄弟节点是O和P，他的深度是4，高度是0，他是第五层

树的种类

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

一般在计算机中比较常用的都是有序树，因为有序树有个好处，就是查找速度比较快，可以根据顺序查找。也有很多应用的实例。有序树比较常用的有二叉查找树，霍夫曼树，B树。这里的B值指的是Balance平衡的意思，意味着，查找和插入的都很快的树。

二叉树（Binary Tree）：每个节点最多含有两个子树（子节点，分支）的树称为二叉树。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。二叉树的第i层，有$2^{i-1}$的节点个数，深度为K的二叉树至多有$2^{k+1}-1$的节点个数，定义根节$K_{0}$的深度为0；而总计拥有节点数匹配的，称为“满二叉树”。（所有叶节点都在最底层的完全二叉树）。对任何一棵非空的二叉树T，如果其叶片(终端节点)数为$n_0$，分支度为2的节点数为$n_2$，则$n_0 =n_2+1$。
对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，（除了最底层其他层都是满的）；
一棵深度为k的二叉树，且有 $2^{k+1}-1$ 个节点的二叉树，称为满二叉树（Full Binary Tree）。若这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度为 $log_2n+1$。深度为k的完全二叉树，至少有$2^k$个节点，至多有$ 2^{k+1}-1$个节点。

完全二叉树：总结点树K，$2^{h-1}<K<2^h-1$,树的高度$h=log_2K+1$

满二叉树：总结点$K=2^{h}-1$,树的高度$h=log_2(K+1)$

如果要访问二叉树中的某一个节点，通常需要逐个遍历二叉树中的节点，来定位那个节点。它不象数组那样能对指定的节点进行直接的访问。所以查找二叉树的渐进时间是线性的 O(n)，在最坏的情况下需要查找树中所有的节点。也就是说，随着二叉树节点数量增加时，查找任一节点的步骤数量也将相应地增加。（这个时候二叉树不是有序树）

如果一个二叉树的查找时间是线性的，定位时间也是线性的，那相比数组来说到底哪里有优势呢？毕竟数组的查找时间虽然是线性 O(n)，但定位时间却是常量 O(1) 。的确是这样，所以普通的二叉树确实不能提供比数组更好的性能。然而，如果我们按照一定的规则来组织排列二叉树中的元素，就可以很大程度地改善查询时间和定位时间。
二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树。1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；3、任意节点的左、右子树也分别为二叉查找树；4、没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构。二叉查找树的查找过程和其他二叉树差不多，有前序遍历，中序遍历，后序遍历。（其他树还有广度优先，和深度优先）。中序遍历二叉查找树可得到一个节点关键字（值）的有序序列（从小到大），一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。搜索、插入、删除的复杂度等于树高（存储的数据越多，树会越高），期望O(logn)，最坏O(n)（数列有序，树退化成线性表，他是十分依赖于树中节点的拓扑结构，也就是节点间的布局关系）。

排序（或称构造）一棵二叉查找树：用一组数值建造一棵二叉查找树的同时，也把这组数值进行了排序。其最差时间复杂度为$O(n^2)$。例如，若该组数值经是有序的（从小到大），则建造出来的二叉查找树的所有节点，都没有左子树。自平衡二叉查找树可以克服上述缺点，其时间复杂度为$O(nlog n)$。一方面，树排序的问题使得CPU Cache性能较差，特别是当节点是动态内存分配时。而堆排序的CPU Cache性能较好。另一方面，树排序是最优的增量排序（incremental sorting）算法，保持一个数值序列的有序性。

二叉查找树性能分析：每个结点的Ci为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度为n，其平均查找长度为$\frac{n+1}2$（和顺序查找相同），最好的情况是二叉查找树的形态和折半查找的判定树相同，其平均查找长度和$log_2n$成正比。

二叉查找(搜索)树的遍历：对于线性的连续的数组来说，遍历数组采用的是单向的迭代法。从第一个元素开始，依次向后迭代每个元素。而 BST 则有三种常用的遍历方式：前序遍历（Perorder traversal）；中序遍历（Inorder traversal）；后序遍历（Postorder traversal）；当然，这三种遍历方式的工作原理是类似的。它们都是从根节点开始，然后访问其子节点。区别在于遍历时，访问节点本身和其子节点的顺序不同。

如图一个满二叉查找树：

前序遍历（Perorder traversal）

前序遍历从当前节点（节点 c）开始访问，然后访问其左孩子，再访问右孩子。开始时，节点 c 为 BST 的根节点。算法如下：1、访问节点 c；2、对节点 c 的左孩子重复第 1 步；3、对节点 c 的右孩子重复第 1 步；

则上图中树的遍历结果为：90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175, 166, 200。

中序遍历（Inorder traversal）

中序遍历是从当前节点（节点 c）的左孩子开始访问，再访问当前节点，最后是其右节点。开始时，节点 c 为 BST 的根节点。算法如下：1、访问节点 c 的左孩子；2、对节点 c 重复第 1 步；3、对节点 c 的右孩子重复第 1 步。

则上图中树的遍历结果为：5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200。(从小到大排序)

后序遍历（Postorder traversal）

后序遍历首先从当前节点（节点 c）的左孩子开始访问，然后是右孩子，最后才是当前节点本身。开始时，节点 c 为 BST 的根节点。算法如下：1、访问节点 c 的左孩子；2、对节点 c 的右孩子重复第1 步；3、对节点 c 重复第 1 步；

则上图中树的遍历结果为：5, 25, 20, 66, 80, 75, 50, 92, 111, 95, 166, 200, 175, 150, 90。

遍历时候都是用递归去实现的，一般会使用组合设计模式来实现树。

二叉查找(搜索)树的插入与删除：

当向树中插入一个新的节点时，该节点将总是作为叶子节点(终端节点)。所以，最困难的地方就是如何找到该节点的父节点。类似于查找算法中的描述，我们将这个新的节点称为节点 n，而遍历的当前节点称为节点 c。开始时，节点 c 为二叉搜索树（BST）的根节点。则定位节点 n 父节点的步骤如下：(三个节点很重要。遍历当前节点c，遍历当前节点的父节点m，要插入的节点n)

1、如果节点 c 为空，则节点 c 的父节点将作为节点 n 的父节点。如果节点 n 的值小于该父节点的值，则节点 n 将作为该父节点的左子节点（左孩子节点）；否则(大于父节点的值)节点 n 将作为该父节点的右子节点(右孩子节点)。

2、如果c节点有值，比较节点 c 与节点 n 的值。
- 如果节点 c 的值与节点 n 的值相等，则说明用户在试图插入一个重复的节点。解决办法可以是直接丢弃节点 n，或者可以抛出异常。
- 如果节点 n 的值小于节点 c 的值，则说明节点 n 一定是在节点 c 的左子树中。则将父节点m设置为节点 c，并将节点 c 设置为节点 c 的左子节点（左孩子节点），然后返回至第 1 步。
- 如果节点 n 的值大于节点 c 的值，则说明节点 n 一定是在节点 c 的右子树中。则将父节点m设置为节点 c，并将节点 c 设置为节点 c 的右子节点（右孩子节点），然后返回至第 1 步。
当合适的节点找到时，该算法结束。从而使新节点被放入二叉搜索树中成为某一父节点合适的孩子节点

BST 的插入算法的复杂度与查找算法的复杂度是一样的：最佳情况是$O(log_2n)$，而最坏情况是 O(n)。因为它们对节点的查找定位策略是相同的。这种插入操作一般都使用递归去实现。

从二叉搜索树中删除节点比插入节点难度更大。因为删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂，那么就违背了 BST 的性质要求。删除节点算法的第一步是定位要被删除的节点，这可以使用前面介绍的查找算法，因此运行时间为 $O(log_2n)$。如果没有子节点是叶子节点，直接删除，如果有子节点，应该选择合适的节点来代替删除节点的位置，它共有三种情况需要考虑。
- 情况 1：如果删除的节点没有右子节点（右孩子节点），那么就选择它的左子节点（左孩子节点）来代替原来的节点（要删除的节点）。二叉查找树的性质保证了被删除节点的左子树必然符合二叉查找树的性质。因此左子树的值要么都大于，要么都小于被删除节点的父节点的值，这取决于被删除节点是左孩子还是右孩子。因此用被删除节点的左子树来替代被删除节点，是完全符合二叉搜索树的性质的。（其实如果删除节点没有左子节点也可以用右子节点去代替。有一个孩子删除节点：删除节点并将其替换为其子节点）
- 情况 2：如果被删除节点的右子节点（右孩子节点）没有左孩子节点，那么这个右子节点被用来替换被删除节点。因为被删除节点的右子节点都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左子节点还是右子节点。因此，用右子节点来替换被删除节点，符合二叉查找树的性质。
- 情况 3：如果被删除节点的右子节点有左孩子节点，就需要用被删除节点右子节点的左子树中的最下面的节点来替换它，就是说，我们用被删除节点的右子树中最小值的节点来替换。

自平衡二叉树（(Balanced Binary Tree）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；是一种结构平衡的二叉搜索树，即叶节点深度差不超过1，它能在$O(log n)$内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树，后续的有红黑树，树堆（Treap），伸展树。平衡二叉查找树是二分查找的一种算法实现。
AVL树：AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者(G. M. Adelson-Velsky和E. M. Landis**)查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(logn)$。也就是每次修改改树就进行AVL翻转，实现平衡。节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。所以带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来**。

失去平衡后进行的规律可归纳为下列四种情况：
1. 单向右旋平衡处理LL：由于在a的左子树根节点的左子树上插入节点，a的平衡因子由1增至2，致使以 a为根的子树失去平衡，则需进行一次右旋转操作；（左左）
2. 单向左旋平衡处理RR：由于在a的右子树根节点的右子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行一次左旋转操作；（右右）
3. 双向旋转（先左后右）平衡处理LR：由于在a的左子树根节点的右子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。（左右）
4. 双向旋转（先右后左）平衡处理RL：由于在a的右子树根节点的左子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。（右左）
AVL的四种翻转，也可说是AVL调平，一般都是用递归实现。
红黑树：红黑树（Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 $O(logn)$时间内做查找，插入和删除，这里的 n是树中元素的数目。他和AVL树不一样的地方就是他们自平衡的方式一样。也可以是他们保证自己是完全二叉树的策略不一样。因为只有在完全二叉树的情况下才能保证树的效率。红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保logn。这不只是使它们在时间敏感的应用如实时应用（real time application，即时计算）中有价值，而且使它们有在提供最坏情况担保的。同时也为其他数据结构中作为基础，也就是其他的数据结构有红黑树。比如Java的HashMap中，当冲突导致后面链表过长，当长度超过8个的时候，就会把链表转换成红黑树；红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
红黑树的性质：红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求。1、节点是红色或黑色；2、根是黑色（这个规则有时被省略。由于根可以总是从红色变为黑色，但不一定反之，这个规则对分析影响不大）；3、所有叶子都是黑色（叶子是NIL节点）；4、每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点）；5、从任一节点到其每个叶子（NIL）的所有简单路径都包含相同数目的黑色节点；从根节点到节点的黑色节点的数量是节点的黑色深度 ; 从根到叶的所有路径中统一的黑色节点数称为红黑树的黑色高度

红黑树的5条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的。树上的增删改查操作的最坏情况时间都与树的高度成正比，所以红黑树在最坏情况下也是高效的。在红黑树中一般用黑的NIL节点表示叶节点，不包含值，只是标志该分支结束，有时候绘图中会直接省略。导致了这些树好像同上述原则相矛盾，而实际上不是这样。是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。
关于红黑树在插入和删除：

红黑树的插入和删除其实和上面BTS很类似，只不过就是在上面插入和删除的之后要对颜色进行判断然后对树进行翻转实现平衡，也可以说红黑树的插入和删除是建立在二叉搜索树之上的。所以红黑树的插入和查找维护起来相对复杂，但是他调整的次数少，其实红黑树不是严格的平衡二叉树。

因为每一个红黑树也是一个特殊化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质。恢复红黑树的性质需要少量$O(log n)$的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为$O(logn)$次

插入首先以与标准二叉搜索树插入非常相似的方式添加节点，并将其着色为红色（也就是只要是插入的N节点就是红色）。最大的区别在于二叉查找树中新增了一个节点作为叶子，而叶子在红黑树中不包含任何信息，所以新的节点替换了现有叶子，然后增加了两个自己添加的黑叶子。接下来发生什么取决于其他附近节点的颜色。有几个红黑树插入案件处理：(N是要新插入的节点，P是N的父节点，U是N的叔叔节点即不父节点的兄弟节点)
- N是根节点，即红黑树的第一个节点
- N的父母（P）是黑色的
- P是红色的（所以它不能是树的根），而N的叔叔（U）是红色的
- P是红色的，U是黑色的
插入时注意：属性1（每个节点都是红色或黑色）和属性3（所有叶子都是黑色的）始终成立。属性2（根部是黑色）通过第一种情况进行检查和纠正。属性4（红色节点只有黑色子节点）只会通过添加红色节点，从黑色到红色重新绘制节点或旋转来威胁。属性5（从任何给定节点到其叶节点的所有路径具有相同数量的黑节点）仅受到添加黑节点，重绘节点或旋转的威胁。
- 当前节点N在树的根部。在这种情况下，为了满足属性2（根部是黑色），将其重新涂成黑色。由于这会一次向每条路径添加一个黑色节点，属性5（从给定节点到其叶节点的所有路径都包含相同数量的黑色节点）不会被违反。
- 当前节点的父P是黑色的，所以属性4（每个红色节点的子节点都是黑色的）不会失效。在这种情况下，树仍然有效。属性5（从任何给定节点到其叶节点的所有路径都包含相同数量的黑节点）没有受到威胁，因为当前节点N有两个黑色叶子节点，但是因为N是红的，通过其每个孩子的路径黑色节点的数量与通过它所替换的叶子的路径数量相同，这是黑色的，所以这个属性保持满意。（换句话说就是什么都不用做）
- 如果父节点P和父母U都是红色的，那么他们都可以被重新粉刷成黑色，并且祖父节点G变成红色来维护属性5（从给定节点到其叶子节点的所有路径都包含相同数量的黑色节点）。由于通过父节点或叔父节点的任何路径都必须经过祖父母，所以这些路径上的黑色节点的数目没有改变。然而，祖父G现在可能违反了属性2（根是黑色的，G可能是根），如果它是根或属性4（每个红色节点的子女都是黑色的），如果它有一个红色的父节点。为了解决这个问题，树上的红黑修复程序重新运行在G上。（把G当成是新加入的节点进行各种情形的检查）请注意，这是一个尾递归调用（java里没有尾递归，所以这里及时递归），所以它可以被重写为一个循环。由于这是唯一的循环，并且在该循环之后发生任何旋转，这证明发生了恒定数量的旋转。
- 父节点P是红色，但叔父节点U是黑色。步骤1：最终目标是将父节点旋转到祖父节点位置，但是如果当前节点位于G子树的“内部” （如果N是子节点的右子节点的左子节点祖父节点或祖父节点的左子节点的正确节点，这里很绕）。在这种情况下，可以执行在P上左转以切换当前节点N和其父节点P的角色。旋转导致一些路径（子树中标记为“1”的路径）通过节点N.他们以前没有。它也会导致一些路径（子树中标记为“3”的路径）不能通过之前做过的节点P. 但是，这两个节点都是红色的，所以属性5（从任何给定节点到其叶节点的所有路径都包含相同数量的黑色节点）不会受到旋转的影响。在这一步完成之后，属性4（每个红色节点的孩子都是黑色的）仍然被违反，但是现在我们可以通过继续步骤2来解决这个问题。
  
  步骤2：当前节点N现在肯定位于G下的子树的外部（P的左子节点或右子节点）。在这种情况下，执行G上的右旋转。结果是前一个父节点P现在是当前节点N和前一个祖父G的父节点的父节点。G是已知的黑色，因为它的前孩子P不可能是红色而不违反属性4 。一旦P节点和G节点的颜色得到的树满足属性4（每个红色节点的子节点都是黑色的）。属性5（从任何给定节点到它的叶节点的所有路径包含相同数量的黑色结点）也就满意，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。
  
  在上面的算法中，除了情况3外，所有情况都只被调用一次，在情况3中，可以使用祖父节点递归回到情况1，这是迭代实现将有效循环的唯一情况。因为修复的在这种情况下，问题被上报每次更高两个级别，它需要最大限度h/ 2次迭代来修复树（其中h是树的高度）。由于升级的概率随着每次迭代呈指数下降，所以平均插入成本实际上是恒定的。（上述图中的1,2,3,4,5指的都是子树，而不是叶子节点）
节点的删除：同样，红黑树的删除也是基于二叉搜索树的删除。也是在二叉搜索树删除后进行红黑调整，使整棵树处于红黑平衡，也就是符合上面的5个属性。所以删除要比插入相对麻烦。当二叉搜索树要删除一个节点(非叶子结点，不过红黑树的叶子节点都是null也没有意义)的时候，他会选择其他节点的填补。(这样的填补就打乱原来红黑顺序)，所以下面讲的是删除完修复整个红黑树的过程。下面就在简单回顾一下二叉搜索树的删除过程，1、如果是叶子节点直接删除；2、如果删除节点D只有一个子节点，那么用那个子节点去代替（这样就会出现红黑不平衡，如果删除节点的父节点是红色，那么删除节点D的子节点也是红色，违背属性4）；3、如果删除节点D有两个子节点，那么删除就要进行左旋或者右旋。也就是说D节点不是被删除而是被其他节点覆盖（代替了）。

我们在BST中执行标准的删除操作时，我们总是删除一个叶子节点或者只有一个子节点，剩下的都是用递归去搞定（对于一个内部节点，我们复制后继节点，然后递归地调用删除作为后继节点，后继节点在被后继节点的后继节点代替，后继节点总是一个叶节点，或者有一个子节点的节点，然后结束递归）。所以我们只需要处理一个节点是叶子还是有一个子节点的情况。假设C是要删除的节点，并且是替换C的子节点（请注意，当C是叶子节点，NIL的颜色被视为黑色时）

我们首先把要删除的节点替换为它的子节点。出于方便，称呼这个子节点为N（在新的位置上），称呼它的兄弟节点S（它父亲的另一个子节点）。在下面的示意图中，我们还是使用P称呼N的父节点，SL称呼S的左子节点，SR称呼S的右子节点。在情形2、5和6下，我们假定N是它父节点P的左儿子。如果它是右儿子，则在这些情形下的左右应当对调。
- 如果删除的是根节点C，那么代替原来根节点的节点也是黑色的节点S，在这种情况下。我们从每个路径中删除一个黑色节点，新的黑色根节点保留属性，树的高度减1。（情况1）
- 删除完节点C，替换的节点是黑色的N。节点P是黑色，兄弟节点S是红色，S节点的子节点是黑色的。所以要对P为根节点的整个树做左旋转，把红色兄弟节点S转换成N的祖父节点，我们接着对调N的父节点P和祖父节点S的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟节点SR是黑色，它是原来红色节点S的一个子节点），剩下的我们可以接下去按情况4，情况5或情况6来处理。（情况2）这里的图中没有显示出来，N是删除了黑色节点后替换上来的子节点，所以这个过程中由P->X->N变成了P->N，实际上是少了一个黑色节点，也可以理解为P(Parent,Black)和S(Silbing,Red)那么他们的孩子黑色节点的数目肯定不等，让他们做新兄弟肯定是不平衡的，还需后面继续处理。就是情况4。
- 删除完节点C，节点P，节点S和节点S的子节点是黑色的。在这种情况下，我们重新绘制节点S为红色。结果是所有通过S的路径，正好是那些不经过N的路径，有一个黑色节点。因为删除N的原始父节点使得所有经过N的路径都有一个黑节点。然而，通过P的所有路径现在比没有经过P的路径少一个黑节点，所以属性5（从任何给定节点到其叶节点的所有路径包含相同数量的黑节点）仍然被违反。为了纠正这一点，我们在P上执行重新平衡程序，从情况1开始。（情况3）
- 节点S和S的子节点都是黑色，但是N的父节点是红色。在这种情形下，我们简单的交换N的兄弟节点和父节点的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了1，添补了在这些路径上被删除的黑色节点。（应对前面情况2中的问题）
- 经过上面的旋转，N的兄弟节点S是黑色，S的左子节点是红色，S的右子节点是黑色，而N是它父节点的左子节点，也就是P的右子节点。在这种情形下我们在S节点为根节点做右旋转，这样S的左子节点SL成为S的父节点和N节点的新兄弟节点。我们接着交换S和它的新父节点的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右子节点是红色的。（情况5）所以我们进入了情形6。N节点和它的父节点P都不受这个变换的影响。
- 节点 S是P节点右子节点黑色，S的右子节点是红色SR，N是其父节点P的左子节点。在这种情况下，我们在P处向左旋转，S成为P和S的右子节点的父节点。然后我们交换P和S的颜色，让S的右子节点变黑色。该子树的根目录仍然具有相同的颜色，所以属性4（每个红色节点的子节点都是黑色的）和5（从任何给定节点到它的叶节点的所有路径都包含相同数量的黑色节点）不被违反。然而，N现在又增加了一个黑色的祖先：P变成了黑色，或者是黑色的，S被加入了黑色的祖父母。因此，通过N的路径通过一个附加的黑色节点。然而，如果一条路径不经过N，那么有两种可能性：它通过N的新兄弟节点。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
- 它通过N的新叔父节点，S的右子节点。那么它以前通过S、S的父亲和S的右节点，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右子节点，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。
  无论哪种方式，这些路径上的黑色节点的数量不会改变。因此，我们已经恢复属性4（每个红色节点的孩子都是黑色的）和5（从给定节点到其叶节点的所有路径包含相同数量的黑色节点）。图中的白色节点可以是红色或黑色，但在转换之前和之后必须指向相同的颜色。
哈夫曼树：(Huffman Tree)哈(霍)夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（高度），树的路径长度是从树根到每一结点的路径长度之和。（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn，N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。哈夫曼树是从低到上去创建的，不是从根节点，到叶子节点去创建的。最早哈夫曼树，使用来做压缩编码的，也就是哈(霍)夫曼编码，它根据出现的频率来规定编码的长度。出现频率越高的使用的编码长度越短，使用频率越低编码长度越长。是一种用于无损数据压缩的熵编码（权编码）算法。

哈夫曼树的构造（哈夫曼算法的实现）

1、将每个元素依照出权重（出现频率）由小排到大；

2、将最小的两个元素权重（频率）相加合成一个新的节点（新节点的权重等于之前两个节点权重之和）；

3、比较新节点和其他节点权重，仍然找出权重最小的2个点合并；

4、重复上面2个步骤，直到没有可以比较的对象；

5、最后产生的树状图就是哈(霍)夫曼树。

哈夫曼树的特点

1、满二叉树不一定是哈夫曼树；

2、哈夫曼树中权越大的叶子离根越近（很好理解，WPL最小的二叉树）

3、具有相同带权结点的哈夫曼树不惟一

4、哈夫曼树的任何结点的度数为 0 或 2，没有度为 1 的结点。（都是两个相加之后形成的节点，子节点所以不会有存在1个）

5、包含 n 个叶子结点的哈夫曼树中共有$2n – 1$ 个结点（包括根节点）。

6、包含 n 棵树的森林要经过 n–1 次合并才能形成哈夫曼树，共产生 n–1 个新结点

**哈夫曼树的构建过程 **

权重{2,3,4,4,5,7} 节点演算过程

1、根据节点权重排序{2,3,4,4,5,7}

2、将最小的两个节点也就是节点1，和节点2相加得到新节点，新节点权重是5，现在节点权重是{4,4,5,5,7}（循环）

3、将小的两个节点也就是节点1，和节点2相加得到新的节点，新节点的权重是8，现在的节点重{5,5,7,8}（循环）

4、将小的两个节点也就是节点1，和节点2相加得到新的节点，新节点的权重是8，现在的节点权重{7,8,10}（循环）

5、将小的两个节点也就是节点1，和节点2相加得到新的节点，新节点的权重是8，现在的节点权重{10,15}（循环）

6、将小的两个节点也就是节点1，和节点2相加得到新的节点，新节点的权重是8，现在的节点权重{25}（循环）

7、构建哈夫曼树结束
B-树：B树(B-Tree)是一种自我平衡的树型数据结构，它保持数据的排序并允许在对数时间内进行搜索，顺序访问，插入和删除操作。B树是一个二叉搜索树的泛化，一个节点可以有两个以上的孩子。与自平衡二叉搜索树不同，B-树针对读取和写入大块数据的系统进行了优化。B树是外部存储器(硬盘)数据结构的一个很好的例子。它通常用于数据库和文件系统。(Rudolf Bayer和Ed McCreight于1971年在波音研究实验室工作时发明了B-树)，这两个没有解释B是什么意思，有人说是B代表波音，也有人说这是拜尔的意思。不过区分一下二叉树（Binary Tree）就可以。个人感觉叫拜尔树好一点。插入，删除，搜索复杂度平均$O(logn)$，最坏是$O(logn)$。空间是$O(n)$

在B树中，内部（非叶）节点可以在一些预定义的范围内具有可变数目的子节点。当数据插入或从一个节点中删除时，其子节点的数量会发生变化。为了保持预定义的范围，内部节点可以被连接或拆分(根据关键字)。由于许多子节点空是允许的，所以B树不需要像其他自平衡搜索树一样频繁地重新平衡，但是由于节点并不是完全满的，所以可能会浪费一些空间(空间换时间)。子节点数量的下限和上限对于特定的实现通常是固定的，一般是$d+1$到$2d+1$之间，但是也有固定的例如2-3树(也是最小的B-树)。这里d指的是关键字。

键：键(keys)也有人说这个是关键字的，B树的每个内部节点都包含一些键。这些键（分离值）用来分割它们的子树。例如，如果一个内部节点具有3个的子节点（或子树），则它必须有2个键：A1和A2，A1<A2。在最左边的子树的所有值将小于A1，在中间子树的所有值将是之间A1和A2，并且在最右边的子树的所有值将大于A2。

B树中每一个内部节点会包含一定数量的键值。通常，键值的数量被选定在d和2d之间。在实际中，键值占用了节点中大部分的空间，所以一般节点都会要被填满一半以上。而因数2(也就是2d的2)是保证该节点(内部节点，分支节点，非终端节点)可以被拆分或者组合。如果一个内部节点有 2d个键，添加一个键给此节点的过程（整个是$2d+1$键），将会把2d键拆分为2个有d个键的节点，并把中间的键添（因为是从小到大排序的，把$d+1$的键为中间键）加给父节点。每一个拆分的节点都拥有最小数目的键d个。相似地，如果一个内部节点和他的邻居两者都有d个键，将通过它与邻居的合并来删除一个键。删除此键值将导致此节点拥有d-1个键;与邻居的合并则加上 d个键（此时当前节点是$2d-1$个键），再加上从邻居节点的父节点移来的一个键(填充在中间一半是d-1，或者d+1的位置)。结果为完全填充的2d个键。

B树通过要求所有叶节点处于相同深度而保持平衡。随着元素被添加到树中，该深度将会缓慢增加，但整体深度的增加并不频繁，结果导致所有叶子节点与根节点距离加1（分支节点多一个键或者关键字）。

B-树又叫平衡多路查找树。一棵N阶的B-树 (切勿简单的认为一棵N阶的B树是N叉树)的特性如下：
1. 树中每个结点最多含有m个孩子（m>=2）；
2. 除根结点和叶子结点外，其它每个结点至少有$ceil(m / 2)$个子节点或子树（其中$ceil(x)$是一个取上限的函数）；
3. 根结点至少有2个孩子（除非B树只包含一个结点：根结点）；
4. 所有叶子结点都出现在同一层，叶子结点不包含任何键信息(可以看做是外部结点或查询失败的结点，指向这些结点的指针都为null)；（注：叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。类似红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。
5. k个子节点的非叶节点包含k -1个键， (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
  
  a) Ki (i=1…n)为键，且键按顺序升序排序K(i-1)< Ki。
  b) Pi为指向子树根的结点，且指针P(i-1)指向子树种所有结点的键均小于Ki，但都大于K(i-1)。
  c) 键的个数n必须满足：$ (ceil(m / 2)-1)<= n <= m-1$。比如有j个孩子的非叶结点恰好有j-1个键(m为子节点或者子树个数)。
B-树的高度

设h是经典B树的高度。设n > 0是树中节点的数量。让m是孩子的节点可以具有的最大数量。每个节点最多可以有m -1个键。

可以证明（通过上面的例子），该高度的B树ħ以其所有节点完全填充具有**$n= m^{h+1} -1$的条目。因此，B树的最佳情况高度是：$h>=log_m(n+1)-1$**，满二叉树的m=2。相同数量节点，高度最低，查询效率最高，插入会导致树变动。

让d内部（非根）节点可以拥有的最小子数，也就是拥有$ceil(m / 2)$子节点或子树**,$d=(m/2)。n=2(d^{h+1})-1$，因子2代表只有一办的值中有子节点或者子树，其他的没有被填满。所以要在原来的基础上乘2才能实现满B-树中n的数量，让等式成立。所以$h<=log_d(\frac{(n+1)}{2})-1$**，也就是所有内部节点，都只有一半子节点或者子树。这样会导致整个树的高度增高，降低查询效率，但增加了插入的效率。

B树用于数据库优点：保持按键顺序遍历排序；使用分层索引来减少磁盘读取次数；使用部分满块来加速插入和删除；用递归算法保持索引平衡；此外，通过确保内部节点至少满一半，B树可以最大限度地减少浪费。B树可以处理任意数量的插入和删除操作。

已排序文件的查找时间：通常，排序和查找算法会被通过大O符号，刻画为比较级别的数值。对一个有N笔记录的已排序表进行二叉查找，打个比方说，可以在**$O（log_2N）$比较级**完成。如果表有1,000,000笔记录,那么定位其中一笔记录，将在20 个比较级内完成。 $log_21,000,000 = 19.931…$

大数据库一直以来被存储在磁盘。从磁盘上读取一笔记录，与之后的比较键值操作相比，在花费的运行时间上前者处于支配地位。从磁盘读取记录的时间涉及到一个寻道时间和旋转延迟。寻道时间可能是从0到20或者更多毫秒，旋转延迟平均下来约是旋转周期的一半。对于一个7200 转每分钟的磁盘，旋转周期大约是8.33毫秒。像希捷ST3500320NS这样的磁盘,磁道至磁道的寻道时间为 0.8毫秒，平均读取寻道时间为8.5毫秒。为了简化，假设从磁盘读取花费10毫秒。乐观来说，如此，在一百万中定位一笔记录将会话花费20次磁盘读取乘上10毫秒每次读取时间，总共是0.2秒。时间花费没有那么糟糕的原因是，独立的记录被成组地记录在磁盘块上。一个磁盘块可能为16 千字节。如果每笔记录大小为160 字节，那么一个块可以存储100 笔记录。上面假设的磁盘读取时间确切地说是读取一个完整块的时间。一旦磁头到达位置，一个或者更多的磁盘块可以以较小的延迟来完成读取。对于100笔记录每块，最后差不多6个比较级是不需要任何磁盘读取的都在上次读取操作中完成了。

B树总结：B树就是，有序数组+平衡多叉树(每个非叶子节点都是一个数组)；顺便说一句，由于根或者树的上面几层被反复查询，所以这几块可以存在内存中，换言之，B树的根结点和部分顶层数据在内存中，大部分下层数据在磁盘上。保持键值有序，以顺序遍历使用层次化的索引来最小化磁盘读取，使用不完全填充的块来加速插入和删除，通过优雅的遍历算法来保持索引平衡。另外，B树通过保证内部节点至少半满来最小化空间浪费。一棵B树可以处理任意数目的插入和删除。

伸展树（Splay Tree）：是一种二叉查找树，它能在$O(log n)$内完成插入、查找和删除操作。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。它的优势在于不需要记录用于平衡树的冗余信息。

优点：可靠的性能，它的平均效率不输于其他平衡树；存储所需的内存少，伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小；查找和更新算法概念简单，易于实现。

缺点：伸展树最显著的缺点是它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级$O(log n)$；它们需要更多的局部调整，尤其是在查找期间。（那些有明确限制的数据结构仅需在更新期间进行调整，查找期间则不用）；一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。
树堆（Treap）：是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 $O(logn)$。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还满足堆的性质。Treap维护堆性质的方法用到了旋转，只需要两种旋转，编程复杂度比Splay要小一些。

插入节点：给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。由于旋转是 $O(1)$的，最多进行h次（h是树的高度），插入的复杂度是 O(h)的，在期望情况下 $h=O(log n)$，所以它的期望复杂度是 $O(logn)$，最坏的情况下$O(n)$。

删除节点：因为Treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。删除最多进行$ O(h)$次旋转，期望复杂度是 $O(logn)$，最坏的情况下$O(n)$。

查找：和一般的二叉搜索树一样，但是由于Treap的随机化结构，Treap中查找的期望复杂度是 $O(logn)$，最坏的情况下$O(n)$。
堆(heap)：堆是被称为优先级队列的抽象数据类型的最高效实现，事实上，优先级队列通常被称为“堆”，而不管它们如何实现。堆的常见实现是二进制堆，其中树是二叉树（父节点的优先级大于子节点的优先级）。堆数据结构，特别是二进制堆，由Williams于1964年引入，作为堆排序算法的数据结构

跳表（和树差不多的性能的数据结构）

跳跃链表：（SkipList）是一种数据结构，允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要$O(log n)$平均时间）。

跳跃链表是允许在有序元素列表内快速搜索的数据结构。通过子链表保持链接的层次结构，可以快速搜索，每个连续的子序列链表少于前一个的元素列表。搜索从最稀疏的子链表开始，通过小于，大于或等于搜索的元素，直到找到两个连续的元素。通过链接的层次结构，这两个元素链接到下一个稀疏的子链表的元素，在那里继续搜索直到最后我们搜索完整个链表。

跳跃链表数据结构的示意图。每个带有箭头的框表示一个指针，一行是一个给出稀疏子序列的链表 ; 底部的数字框（黄色）表示有序的数据链表。搜索从最上面的子子链表向下进行，直到找到包含搜索元素的连续元素。

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，这里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起来，每个元素都在$\frac{1}{1-p}$ 个列表中出现，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在$ O(log_{1/p}n)$ 个列表中出现。

跳过列表是一种概率数据结构，似乎可能取代平衡树作为许多应用程序的实现方法。跳过列表算法具有与平衡树相同的渐近期望时间界限，并且更简单，更快速并且使用更少的空间。

总结

树是一种非常常用的数据结构，它在很多地方可以用到上，一般情况下，树都是有序的，因为有序才有意义。例如二叉搜索树，大多数树都是这种树的变种，可以自动平衡（因为平衡之后效率才高），自平衡二叉树是折半查找算法的一种实现方式，包括跳表也可以实现，所以对于查找很快，比如红黑树，AVL树。但是同样的因为查找很快，因为有序所以就要去维护，所以插入和查找就会变得很复杂。每次都要对树进行旋转，特别树的高度越高数据量越多维护成本就越高。所以这个时候就出现了B树，B+，B*树。他们通过冗余（留出一些空的空间等待插入值）键（关键字）的空间。来解决大数据量下的高度问题增长问题，这这中一般在文件系统和数据库系统中比较常用，mysql的索引默认就是B+树。这些归根到底也就是空间换时间。所以恰当的数据结构就可以提升算法效率，减少存储空间。