# Tree

## 概念

**线性表结构**：栈、队列\
**非线性表结构**：树、图

树（Tree）每个元素叫做**节点**，连线节点之间叫做**父子关系**。父节点指向子节点。拥有相同父节点的叫做**兄弟节点**。没有父节点的叫做**根节点**，没有子节点的叫做**叶子节点**或者**叶节点**。

**节点的高度**（Height）：节点到叶子节点的最长路径（边数）。\
**节点的深度**（depth）：根节点到这个节点所经历的边的个数。\
**节点的层数**（Level）：节点的深度+1。\
**树的高度**：根节点的高度。

**二叉树**：每个节点最多有两个子节点，分别为左子节点和右子节点。\
**满二叉树**：叶子节点都在最底层，除了叶子节点，每个节点都有左右两个子节点。\
**完全二叉树**：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，除了最后一层，其它层的节点个数都达到最大。完全二叉树用数组存储最节省内存。

**链式存储法**：每个节点有三个字段，数据和两个指针。\
**顺序存储法**：数组存储，根节点存在下标`1`的位置，如果节点 X 存在下标为`i`的位置，则左子节点存在`2 * i`的位置，右子节点存在`2 * i + 1`的位置，父节点存储在`i / 2`的位置。完全二叉树仅仅浪费下标为 0 的位置，如果是非完全二叉树，则会浪费很多空间。

二叉树的遍历，时间复杂度`O(n)`：

* 前序遍历，节点 -> 左子树 -> 右子树
* 中序遍历，左子树 -> 节点 -> 右子树
* 后序遍历，右子树 -> 左子树 -> 节点

## 二叉查找树

**二叉查找树**（binary search tree）：任意节点，左子树的每个节点都小于这个节点，右子树的每个节点都大于这个节点。

* **查找：**先去根节点，若等于则返回，若比根节点小，则在左子树递归查找，若比根节点大则在右子树递归查找。
* **插入：**插入的数据都在叶子节点，从根节点开始，若插入的数据比较大，且右子树为空，则插入到右子节点，若不为空，则递归遍历右子树，找到插入位置。插入数据比较小，类似往左子树插。
* **删除：**若删除的节点没有子节点，则将删除节点的父节点指向 null；若删除的节点只有一个子节点，则将删除节点的父节点指向删除节点的子节点；若删除的节点有两个子节点，找到删除节点右子树的最小节点，与删除节点替换，再应用上两条规则删除原来最小节点的位置。也可以直接标记为已删除，但是不真正删除，只是浪费内存。
* 查找最大节点。
* 查找最小节点。
* 查找前驱结点。
* 查找后继结点。
* 输出有序的数据序列，中序遍历即可，时间复杂度 O(n)，所以二叉查找树也叫二叉排序树。

实际中，在二叉查找树中存储的事对象，利用对象的某个字段作为键值来构建二叉查找树，对象的其它字段叫做**卫星数据**。

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

* 通过链表或者支持动态扩容的数据等数据结构作为节点，把值相同的数据都存储在同一节点上。
* 每个节点仍存储一个数据，插入数据时，若相同，则插入这个节点的右子树，即当做大于这个节点来处理；查找时，遇到值相同时，并不停止，继续在右子树查找，直到遇到叶子节点，把所有等于这个值得节点都查找出来；删除时，也是找到每个要删除的节点，依次删除。

二叉查找树的**时间复杂度**：最坏`O(n)`，最好`O(height) = O(logn)`，平均`O(logn)`。

**散列表与二叉查找树**：

* 散列表数据无序，若要输出有序数据，比较困难；二叉查找树中序遍历即可。
* 散列表扩容时耗时很多，性能不稳定；平衡的二叉查找树性能稳定。
* 尽管散列表查找为 O(1)，但因为有散列冲突的情况，不一定比 O(logn) 好。
* 散列表的实现较复杂，要考虑散列函数的设计、冲突解决、扩容、缩容等。
* 散列表表会浪费一定的空间。

### 例题

* [LeetCode 98：判断一颗树是否为二叉查找树。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT98.java)
* [LeetCode 235：二叉查找树的公共祖先。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT235.java)
* [LeetCode 236：二叉树的公共祖先。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT236.java)

## 平衡二叉查找树

为什么需要**平衡二叉查找树**？二叉查找树在理想情况下，插入、删除、查找操作的时间复杂度都是`O(logn)`，但是二叉查找树在频繁的动态跟新过程中，会出现退化情况，最差情况时，退化为链表。为了解决这个复杂度退化问题，所以需要平衡二叉查找树。

**平衡二叉树**：二叉树中任意一个节点的左右子树的高度相差不能大于 1，完全二叉树、满二叉树都是平衡二叉树。

**平衡二叉查找树**：满足平衡二叉树的二叉查找树。AVL 树、Treap（树堆）、Splay Tree（伸展树） 是严格的平衡二叉查找树。红黑树是不严格的。

## **红黑树**

Read-Black Tree，简称 R-B Tree。**定义**：·

* 根节点是黑色；
* 每个叶子节点都是黑色的空节点 NULL，不存储数据；
* 任何相邻节点不能同时为红色；
* 每个节点，从该节点到达其可达的叶子节点的所有路径，都包含相同数目的黑色节点。

如下图两个红黑树的例子（图中省略了黑色的空叶子节点）：

![](/files/-LzWvEdQShAODgCaQOFO)

红黑树的**时间性能分析**：

* 二叉查找树的很多操作的时间复杂度都有树的高度成正比，所以只需要分析红黑树的高度。
* 将红黑树的红色节点去掉，变成一颗四叉树。
* 根据第四点定义，这颗四叉树高度比相同节点数的完全二叉树还小，即小于 log2n。
* 把红色节点加回去，根据第 3 点定义，红黑树高度小于 2log2n。

{% hint style="info" %}
红黑树来源于 2-3 树，可以通过 2-3 来理解红黑树的插入、删除操作。
{% endhint %}

## 递归树

### 递归

可以用递归解决的问题满足三个条件：

1. 一个问题可以分解为几个子问题
2. 这个问题与分解后的子问题，除了数据规模不一样，求解思路完全一样
3. 存在递归终止条件

写递归代码的关键是写出递归公式，找到终止条件。

人思维递归不应该试图想清楚整个递和归的过程。应该的做法：若问题 A 可分解为子问题 B、C、D，假设 B、C、D 已经解决，在此基础上思考如何解决 A，仅需思考 A 与 B、C、D 两层的关系即可，不需要一层一层往下思考。

* 递归代码要警惕堆栈溢出，可限制递归最大深度来解决。
* 递归要警惕重复计算，可以缓存已经计算的结果。
* 递归会造成过多的函数调用，可以改成非递归来解决。

**案例**：假如 n 个台阶，每次可以跨 1 或 2 个台阶，清楚 n 个台阶有多少种走法。递归公式：`f(n) = f(n-1) + f(n-2)`。终止条件：`f(1) = 1, f(2) = 2`

```
// 递归
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

// 非递归
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  int ret = 0;
  int pre = 2;
  int prepre = 1;
  for (int i = 3; i <= n; ++i) {
    ret = pre + prepre;
    prepre = pre;
    pre = ret;
  }
  return ret;
}
```

把递归的过程画成图，其实就是一颗树，叫做**递归树**。递归树可以用来求解时间复杂度。

### 归并排序的时间复杂度

![](/files/-M-nowLnG8Ev4LRUcPqX)

归并排序主要有分解操作和合并操作。分解操作代价很低，合并操作耗时与数据规模有关，但是递归树中每一层的数据规模总和是一样的。设每一层耗时为 n，时间复杂度为 O(h \* n)，h 为树的高度。归并排序的递归树为满二叉树，高度为 log2n，所以归并排序的时间复杂度为 O(nlogn)。

### 快排的时间复杂度

![](/files/-M-nq-Z0zIMO_50GOiaH)

快速排序并不能保证每次分割都能等分，假设每次分割都是 1:9。每一层的分区操作所遍历的数据个数之和就是 n，所以只需要求出这颗递归树的高度，但是这棵树不是满二叉树。

从根节点 n 到叶子节点 1，最短路径每次都乘以 1/10，最长路径每次乘以 9/10，所以最短路径为 nlog10(n)，最长路径为 nlog10/9(n)，所以快排的时间复杂度为 O(nlogn)。

### 斐波拉契数列的时间复杂度

![](/files/-M-ns9vIw54QLHl0Pyp4)

同理，根节点 n 到叶子节点的最长路径为 n，最短路径为 n/2。每一层的耗时为这一层节点的加法操作，所以第一层为 1，第二层为 2，第 n 层为 2^(n-1)。然后乘以路径，所以耗时为 O(2^n)。

### 全排列的时间复杂度

一个数列的全排列，如果我们确定了最后一位，那么就剩下了 n - 1 个数据的全排列问题。代码为：

```java
// int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
public void printPermutations(int[] data, int n, int k) {
  if (k == 1) {
    for (int i = 0; i < n; ++i) {
      System.out.print(data[i] + " ");
    }
    System.out.println();
  }

  for (int i = 0; i < k; ++i) {
    int tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;

    printPermutations(data, n, k - 1);

    tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;
  }
}
```

如下递归树，第一层有 n 次交换操作，第二层有 n 个节点，每个节点有 n - 1 次交换，依次类推，时间复杂度为 O(n!)：

```
n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1 ≈ n!
```

![](/files/-M-nuNmKhlVVeWqCcPBd)

## 堆

### 概念

堆（Heap）的**定义**：

* 一颗完全二叉树。
* 堆中的每个节点的值都必须大于等于（或小于等于）其左右子节点的值。大于等于的叫做**大顶堆**，小于等于的叫做**小顶堆**。

**堆的存储**：由于堆是完全二叉树，所以用数组存储是最适合的，非常节约内存。

### 插入

先把插入的元素放到堆的最后，此时就不满足堆的定义了。我们就要进行调整，这个过程叫做**堆化**（heapify）。

插入后，我们需要做**从下往上**堆化。就是让插入节点与父节点对比，若不满足大小关系，则交换，一直重复这个过程。

![](/files/-M-r8kxEPK3VgiAH-13J)

```java
public class Heap {
  private int[] a; // 数组，从下标1开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数

  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }

  public void insert(int data) {
    if (count >= n) return; // 堆满了
    a[++count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
      swap(a, i, i/2); // swap()函数作用：交换下标为i和i/2的两个元素
      i = i/2;
    }
  }
 }
```

### 删除堆顶元素

删除堆顶元素后，把最后一个元素挪到堆顶，然后再进行从上往下堆化。

![](/files/-M-r9KyQSTHCr7Nc3DrZ)

```java
public void removeMax() {
  if (count == 0) return -1; // 堆中没有数据
  a[1] = a[count--];
  heapify(a, count, 1);
}

private void heapify(int[] a, int n, int i) { // 自上往下堆化
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}
```

{% hint style="info" %}
完全二叉树的高度不会超过 log2n，所以插入数据和删除堆顶元素的时间复杂度为 O(logn)。
{% endhint %}

### 堆排序

堆排序时间复杂度为 O(nlogn)，原地排序。有建堆和排序两个步骤。

#### 建堆

建堆就是将数组原地建成一个堆。有两种思路。

**思路一**：类似插入排序，将数组分成两个部分，前半部分已经组成堆，然后依次把后半部分的数据插入堆中。是从前往后处理数据，从下往上堆化的过程。

**思路二**：是从后往前处理数据，从上往下的堆化的过程。叶子节点往下没有数据，所以直接从非叶子节点开始处理。

![](/files/-M-rxjvewtw8mjflrFMK)

![](/files/-M-rxddzvURC3kIslWdB)

```java
private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}
```

思路二建堆的时间复杂度为 O(n)。如下图，右边的每一项求和即可。

![](/files/-M-rMF3RbRXwIRhYhgwV)

#### 排序

以大顶堆为例，依次做上节的删除堆顶元素操作，得到的结果就是从小到大的排序数组。

![](/files/-M-rOxL9ZSFvCtxf9kAC)

```java
// n表示数据的个数，数组a中的数据从下标1到n的位置。
public static void sort(int[] a, int n) {
  buildHeap(a, n);
  int k = n;
  while (k > 1) {
    swap(a, 1, k);
    --k;
    heapify(a, k, 1);
  }
}
```

建堆为 O(n)，排序为 O(nlogn)，所以堆排序时间复杂度为 O(nlogn)。是原地排序，不是稳定排序，因为将最后一个元素与堆顶元素互换。

{% hint style="warning" %}
为什么快排比堆排序性能好？

* 快排访问数组是连续的，堆排序是跳着访问的，所以快排堆 CPU 缓存更加友好。
* 堆排序的交换次数大于快排。快排交换次数不会大于逆序度，但是堆排序建堆过程会打乱原有顺序，增加逆序度。
  {% endhint %}

### 堆的应用

#### 优先级队列

优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的最先出队。

用堆实现优先级队列最直接，往优先级队列插入一个元素即往堆中插入一个元素。从队列中取出优先级最高的元素即从堆中取出堆顶元素。

优先级队列的应用非常广泛，这里举两个例子。

**合并有序小文件**

假设有 100 个小文件，每个 100MB，每个文件都是有序的，要求把这 100 个小文件合并成一个大文件。

思路类似归并排序的归并操作，从 100 个文件中都取出第一个元素组成大小为 100 的优先级队列，也就是堆。然后从堆中取出堆顶元素放入大文件中，再从堆顶元素对应的小文件中取出下一个元素插入堆中。循环这个过程，就合并成了一个大文件。

**高性能定时器**

假设有一个定时器，维护了很多定时任务，每个任务都有一个时间触发点。

* 简单的实现：定时器每隔一段小时间就扫描一遍任务，如果有任务到达了时间就执行。此方法有两点低效：每次要扫描所有任务；如果下个任务还要很久，那么就要做很多次无用的扫描。
* 高效的实现：用优先级队列来解决，任务都放入优先级队列中，拿到堆顶的任务与当前时间比较，得到时间间隔 T，所以只需要直接 T 以后来执行堆顶任务就行；然后删除堆顶元素，与新的堆顶元素比较得到新的时间间隔。

#### 求 Top K

求 Top K 有两种类型，静态数据（数据集合不会再变）和动态数据（有数据动态加入集合中）。

* 静态数据：维护一个大小为 K 的小顶堆，遍历数据，往堆中插入元素，若比堆顶元素大，则删除堆顶元素，把这个元素插入堆中，遍历完成后，堆中的元素就是 Top K。
* 动态数据：同样也是维护一个大小为 K 的小顶堆，当有数据添加进集合时，也对堆做比较操作。这样无论何时想要 Top K，只要返回堆中的数据即可。

#### 求中位数

求动态数据中的中位数（处在中间位置的那个数）。

维护两个堆，一个大顶堆，一个小顶堆。大顶堆存储前半部分数据，小顶堆存储后半部分数据，两个堆的堆顶就是中位数。

关键是插入数据时怎么调整两个堆。如果小于大顶堆堆顶，则插入到大顶堆中；如果大于小顶堆堆顶，则插入小顶堆中。然后通过将一个堆的堆顶元素移至另一个堆来保持两个堆的大小均衡。

{% hint style="info" %}
拓展一下，不仅可以求中位数，还能求任意百分位数据。比如接口 99% 响应时间。
{% endhint %}

## 并查集

Union-find Algorithm 是一种树形的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。定义了两个操作：

* **Union**：合并两个子集。**优化**：低 rank 合并到高 rank；但是需要记录 rank，一般用下面的优化就可以了。
* **Find**：确定元素属于哪一个子集，可用于确认两个元素是否属于同一子集。**优化**：路径压缩，在 find 时，把路径上所有的节点都直接指向 root。

例题：

* LeetCode 200：岛屿数量。
* LeetCode 547：朋友圈个数。

## B 树

二叉树的搜索效率最高，但是高度较高，并且索引不止在内存中，还要写到磁盘上，每次读取节点都是一次磁盘操作，因此很多数据库不使用二叉树。为了减少磁盘的读取次数，所以应该使用 N 叉树，以 InnoDB 为例，N 大约为 1200。

B 树英文叫做 Balance Tree，也叫平衡多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中常采用 B 树实现索引结构。

![](/files/-LtPRaVkSKow4EqFxEi7)

一个 M(M > 2) 阶的 B 树每个节点最多可以包含 M 个子节点，有如下特性：

* 根节点的儿子数为 \[2, M]。
* 中间节点有 k - 1 个关键字和 k 个孩子，k 的范围 \[ceil(M / 2), M]。
* 叶子节点有 k - 1 个关键字，k 的范围 \[ceil(M / 2), M]。
* 中间节点的 k - 1 关键字按照顺序存放，k 个孩子指向关键字分割的 k 个范围。
* 所有叶子节点位于同一层。

## B+ 树

B+(B more) 树是基于 B 树做的改进，主流的 DBMS 都支持 B+ 树，如 [MySQL](/notes/database/mysql/indexing.md#2-mysql-suo-yin)。B+ 树的改进点如下：

* 关键字树 = 孩子树。
* 非叶子节点的关键字也会存于子节点中，并且在子节点关键字中最大（或最小）。
* 非叶子节点仅保存关键字，不保存数据，数据存放在叶子节点中。
* 叶子节点有所有关键字，并且叶子节点之间构成一个有序链表，叶子节点内部也有序。

![](/files/-LtPW3cWLgTEP9tZFcXr)

有了上述改进点，B+ 树有如下好处：

* B+ 树查询效率更加稳定，因为每次都必须访问到叶子节点才能找到数据；而 B 树非叶子节点也存储数据，所以可能很快就找到。
* B+ 树非叶子节点不存储数据，同样大小的磁盘页可以存储更多的关键字，所以更加矮胖，磁盘 IO 次数更少。
* B+ 树的范围查询效率要高很多。

假设有如下表和数据，则 InnoDB 的索引结构为下图：

```sql
mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

(100,1) (200,2) (300,3) (500,5) (600,6)
```

![](/files/-LeGbgMAa_mM-l14RLEC)

* **主键索引**：又叫聚簇索引（clustered index），叶子节点存整行数据。
* **非主键索引**：又叫耳机索引（secondary index），叶子节点存主键的值。

若使用`select * from T where k=5`，则先搜索 k 索引树，得到 ID 再去主键索引树搜索，这称为**回表**。

#### 页分裂

当插入数据时，比如插入 700，则只需在后面追加一条记录。若插入 400，需要逻辑上移动后面的数据。若插入的页已经满了，B+ 树会申请一个新的页，然后挪动部分数据过去。

#### 页合并

若相邻两个页由于删除数据，空间利用率很低，则会把数据页合并。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.