遍历

• 前序遍历——中，左，右

  ABDGHCEIF

• 中序遍历——左，中，右

  GDHBAEICF

• 后序遍历——左，右，中

  GHDBIEFCA

• 层序遍历

  ABCDEFGHI

完全二叉树

• 具有n个结点的完全二叉树的深度为 $\left \lfloor log_2(n)+1 \right \rfloor $

• 数组存储

  • 一般的树存储用链表居多，完全二叉树当然也可以用链表存储。
  • 但是由于完全二叉树的性质，用数组存储，更方便，也更节省空间。

  

• 编号

  • 若 i=1,则结点i为根结点，若i>1，则其双亲结点是$ \left \lfloor i/2 \right \rfloor$
  • 如果2i>n,则结点i无左孩子，否则，其左孩子是结点2i
  • 如果2i+1>n,则结点i无右孩子，否则，其右孩子是结点2i+1

二叉查找树

​ 二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。

• 要求

  

  ​ 二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

• 插入、删除、查找

  ==略==

• 支持重复数据的二叉查找树

  • 同值扩容法

    ​ 二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

  • 相同取大法

    • 插入

      ​ 每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

      

    • 查找

      ​ 当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

      

    • 删除

      ​ 对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

      

• 与散列表的对比

  • 二叉查找树的劣势

    ​ 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。

    而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)。

  • 二叉查找树的优势

    1. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。

       而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

    2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定。

       但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。

    3. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，**但因为哈希冲突的存在，这个常量不一定比 logn 小，**所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

    4. **散列表的构造比二叉查找树要复杂，需要考虑的东西很多。**比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

    5. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

AVL树

• 高度平衡的二叉查找树
• 左子树和右子树的高度相参不会超过1，最大是1

==红黑树==

• 基础

  ​ 红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。

  ​ 红黑树中的节点，一类被标记为黑色，一类被标记为红色。

  • ==红黑树的要求==

    1. 根节点是黑色的；

    2. 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

    3. 任何相邻(这里值得是父亲和孩子)的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的(上下分隔)；

    4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

    

• 近似平衡特性

  ​ 平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化得太严重。

  ​ **红黑树的高度稳定地趋近 log2n **

  • 首先，将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？

    ​ 红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

    ​ 因为从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点

    ​ 我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

    ​ ==即黑树高度不超过log~2~n==

  

  • 把红色节点加回去，高度会变成多少呢？

    ​ 在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。

    ​ 红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

    ​ 这样推导出来的结果不够精确，实际上红黑树的性能更好。

• 为什么喜欢红黑树

  ​ AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。

  ​ **红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。**所以，红黑树的插入、删除、查找各种操作性能都比较稳定。

• 红黑树和2-3树的关系 (opens new window)

  • 颜色表示

    ​ 因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们将链接的颜色保存在表示结点的Node数据类型的布尔变量color中（若指向它的链接是红色的，那么该变量为true，黑色则为false）。

    ​ 当我们提到一个结点颜色时，我们指的是指向该结点的链接的颜色

  • 关系

    ​ 红黑树是从2-3树上演变而来的，具体请了解网址内容。

    ​ ==红黑树就是用红链接表示3-结点的2-3树==

    ​ 如果我们将一颗红黑树中的红链接画平，那么所有的空链接到根结点的距离都将是相同的。如果我们将由红链接相连的结点合并，得到的就是一颗2-3树。

    

• 红黑树实现 (opens new window)

  ​ 红黑树实现，其实近似于魔方还原，都有固定步骤，具体实现不要求掌握，能看懂过程就行。

• ==关于红黑树==

  ​ **红黑树是一种平衡二叉查找树。**它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。

  ​ **红黑树的高度近似 log2n，**所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。

  ​ 因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。

  ​ 不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用==跳表==来替代它。

递归树

借助递归树来分析递归算法的时间复杂度

还可以借助递推公式来分析时间复杂度 (opens new window)

• 归并排序分析

  

  ​ 归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。

  ​ 我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 O(n∗h)。

  ​ 归并排序递归树是一棵满二叉树。我们前两节中讲到，满二叉树的高度大约是 log2n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)。

• 快速排序分析

  ​ 快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 T(n)=2T(2n)+n，很容易就能推导出时间复杂度是 O(nlogn),就跟归并排序相当。

  ​ 我们假设平均情况下，每次分区之后，两个分区的大小比例为 1:k。递归树图绘制如下：

  

  ​ 快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是 h∗n ，也就是说，时间复杂度就是 O(h∗n)。

  ​ 因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。这样一个递归树的高度是多少呢？

  ​ 我们知道，快速排序结束的条件就是待排序的小区间，大小为 1，也就是说叶子节点里的数据规模是 1。从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 1/10，最长的一个路径每次都乘以 9/10。通过计算，我们可以得到，从根节点到叶子节点的最短路径是 log~10~n，最长的路径是 log~10/9~n。

  

  ​ 所以，遍历数据的个数总和就介于 nlog10n 和 nlog910n 之间。根据复杂度的大 O 表示法，对数复杂度的底数不管是多少，我们统一写成 logn，所以，当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 O(nlogn)。

• 斐波那契数列分析

  

  ​ f(n) 分解为 f(n−1) 和 f(n−2)，每次数据规模都是 −1 或者 −2，叶子节点的数据规模是 1 或者 2。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 n/2。

  ​ 每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 1。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 22。**依次类推，第 k 层的时间消耗就是 2k−1，**那整个算法的总的时间消耗就是每一层时间消耗之和。

  ​ 如果路径长度都为 n，那这个总和就是 2^n^-1

  ​ 如果路径长度都是 n/2 ，那整个算法的总的时间消耗就是 2^n/2^−1。

  ​ 这个算法的时间复杂度就介于 O(2^n^) 和 O(2^n/2^) 之间。虽然这样得到的结果还不够精确，只是一个范围，但是我们也基本上知道了上面算法的时间复杂度是指数级的，非常高。