非线性结构算法

第一章：集合与字典

一、集合 / 哈希表 / 散列表

认识哈希表

1. 是什么

哈希表（Hash table），也叫散列表。

哈希表是根据关键码而直接进行访问的数据结构。

#### 2. 哈希函数

哈希化：将大数字转化成数组范围内下标的过程，就称之为哈希化。

哈希函数：通常会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数称为哈希函数。

哈希表：最终将数据插入到的这个数组，对整个结构的封装，就称之为是一个哈希表。

1）数字相加

假设我们要把字符串（比如单词）存入哈希表。最直观的想法是把每个字母的 ASCII 码相加。

例子：cats = 99 + 97 + 116 + 115 = 427

致命缺点：这种加法完全忽略了字母的顺序。比如 cats、cast、tacs 加起来总和全都是 427。遇到这些词时，它们会完全冲突（映射到同一个哈希槽中）。

2）幂的连乘

也叫多项式哈希。

为了使得连字母顺序交换也能得到不同的哈希值，给每个位置的字符赋予一个权重。这个权重，就是某个数字（底数，一般用一个质数比如 31、37、131）的连续幂次方。

假设我们选择底数为 $P$（读作底数或基数），对于一个长度为 $n$ 的字符串 $S$，它的转化公式就是多项式展开：

$$Hash=(S_0\times P^{n-1})+(S_1\times P^{n-2})+\cdots +(S_{n-2}\times P^1)+(S_{n-1}\times P^0)$$

举个例子

将单词 cats 进行哈希，选择常数 $P=37$：

• c = 99
• a = 97
• t = 116
• s = 115

代入公式（这里就是所谓的“幂的连乘”）：

$$Hash=99\times {37}^3+97\times {37}^2+116\times {37}^1+115\times {37}^0$$

显然，因为带上了 ${37}^3$、${37}^2$ 这样的次幂权重，一旦字符换了位置（比如 c 放到了末尾），乘的次幂就变了，最终算出来的值就截然不同了。

3）霍纳法则

在实际写代码的时候，不可能真的去算 ${37}^3$、${37}^4$，甚至是 ${37}^{100}$（字符串长了极容易溢出且计算量大）。

所以利用初中数学里的提取公因式，上面的式子可以化简为嵌套的乘法（多项式求值优化）：

$$Hash=(((99\times 37)+97)\times 37+116)\times 37+115$$

代码实现

function hashString(str) {
  let hashCode = 0;
  // 选一个质数作为底数，Java 的 String.hashCode() 就使用的是 31
  let prime = 31; 

  for (let i = 0; i < str.length; i++) {
    // 霍纳法则：上一次的哈希值乘以质数，加上当前的字符编码
    hashCode = prime * hashCode + str.charCodeAt(i);
  }
  return hashCode;
}

通过这种每一步都 乘以一个常数 + 加上新字符 的方式，就高效地用代码实现了理论上的幂的连乘。

数学奥秘

hashCode = prime * hashCode + str.charCodeAt(i)

假设我们要对一个长度为 4 的字符串进行哈希，字符分别是 $C_0,C_1,C_2,C_3$，底数是 $P$ (也就是 prime)。

按照标准的“幂的连乘”公式，应该是这样的：

$$Hash=C_0\times P^3+C_1\times P^2+C_2\times P^1+C_3$$

这看起来需要算 3 次方、2 次方。但是，我们从左往右不断把 $P$ 当作公因式提取出来，公式就会变成这样：

1. 提取最外层的 $P$：

$$Hash=(C_0\times P^2+C_1\times P^1+C_2)\times P+C_3$$

2. 再提取里面的 $P$：

$$Hash=\mathbf{(}\mathbf{(}{\mathbf{C}}_{\mathbf{0}}\times \mathbf{P}\mathbf{+}{\mathbf{C}}_{\mathbf{1}}\mathbf{)}\times \mathbf{P}\mathbf{+}{\mathbf{C}}_{\mathbf{2}}\mathbf{)}\times \mathbf{P}\mathbf{+}{\mathbf{C}}_{\mathbf{3}}$$

注意看最后这个式子，它里面完全没有任何幂乘运算了，只有形式一致的嵌套式：“括号里的结果 $\times P$ + 新项”。

3. 哈希碰撞

若哈希函数计算出的索引一致，会出现哈希碰撞。

1）拉链法 / 链地址法

##### 2）开放地址法

寻找空白的单元格来添加重复的数据。

• 线性探测

  挨着往下找（步长为 1）。

• 二次探测

  跳跃着往下找（步长为平方数：1, 4, 9, 16 ...）。

• 再哈希法

  用第二套公式（第二个哈希函数）来决定每个数据专属的步长。

二、代码实现

第二章：树

一、简介

1. 是什么

树是计算机编程中最重要、最核心的一种数据结构。

在日常生活中，树状结构也是广泛存在的，例如家族的族谱、公司部门结构图等。在计算机编程中，树更是无处不在，你平时接触到的二叉查找树、红黑树、堆、并查集、线段树、树状数组、前缀树，这些都是属于树这种数据结构的一种。

应用场景：数据库索引 B+ 树、编译器的 AST 语法树、操作系统的文件系统、Vue 中的虚拟 DOM ……

注意：树可以是一颗空树，也就是 n = 0。

2. 术语与度量

**术语**

1. 节点：树的基本单位，一棵树就是由一个一个节点组成的。
2. 边：两个节点之间的连接或链接。如果节点 A 和节点 B 之间存在一条边，A 可能是父节点，B 可能是子节点，反之亦然。
3. 根节点：整颗树的顶端节点，它上面没有父节点。
4. 父（双亲）节点：一个节点的上一级节点。
5. 子节点：一个节点派生出来的节点，只计算下一层。例如 A 节点的子节点就是 B、C、C 节点的子节点就是 E、F。
6. 兄弟节点：具备相同父节点的节点互称为兄弟节点。
7. 叶子节点（终端节点）：没有子节点的节点，称之为叶子节点，位于树的末端。
8. 内部节点：除根节点外，任何至少有一个子节点的节点。
9. 子树：树的一部分，由一个节点及其所有后代组成。它本身也是一棵以该节点为根的有效树。由此可知树是一种递归定义的数据结构。
10. 森林：由 m（$m\ge 0$）棵互不相交的树的集合称为森林。

树的度量

1. 节点的层：也就是节点的深度。从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推。

2. 节点的深度（从上往下数）：该节点所在的层次。<== 以这个为准

   维基百科：对于任意节点 n，n 的深度为从根到 n 的唯一路径长。其中根的深度为 0。

3. 节点的高度（从下往上数）：以该节点为根的子树的层数。<== 以这个为准

   维基百科：对于任意节点 n，n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0。

4. 节点的度：一个节点的子节点的个数称之为度。例如 A 节点的度就为 2、D 节点的度为 3，C 节点的度也为 2。

5. 树的高度、树的深度、树的层数：总共多少层。

6. 树的度：取各节点度的最大值。

3. 性质

4. 树的表示法

• 图形表示法。

• 符号表示法：用小括号先将根节点放入到括号里面，然后将子节点从左往右放入括号，对子节点的子节点也采用相同的方式。同层的子节点使用逗号隔开。

  (A(B(D(G, H, I)), C(E(J), F)))

5. 树的分类

二叉树

• 定义：每个节点最多有 2 个子节点（左、右子节点）。

• 变种：

  • 二叉搜索树 (Binary Search Tree) ：左子树所有节点值 < 根节点值 < 右子树所有节点值。用于快速查找、插入、删除。

  • 平衡二叉搜索树：通过旋转操作保持树高平衡，确保操作效率稳定在 $O(logn)$。

    常见类型：

    • AVL 树：严格平衡（左右子树高度差 ≤ 1），适合读密集型场景。
    • 红黑树：弱平衡（通过颜色标记规则），插入删除效率更高，广泛应用于系统级代码。
    • Treap：结合 BST (二叉搜索树) 和堆特性，随机优先级保证平衡。
    • 伸展树 (Splay Tree) ：通过“伸展”操作将最近访问节点移至根，适合局部性访问。

多叉树

多叉树也存在多种类型：

• B 树 (B-Tree) ：每个节点可包含多个键和子节点，所有叶子在同一层。常用于数据库索引、文件系统。
• B+ 树：针对 B 树的一种优化，非叶子节点仅存键，数据全存储在叶子节点，叶子节点通过指针链接。
• 字典树 (Trie) ： 每个节点存储字符，路径构成字符串，叶子节点标记单词结束。前缀匹配高效，常用于自动补全、拼写检查、IP 路由表。

特殊用途树

• 堆 (Heap) ：一种完全二叉树，满足堆性质（最大堆/最小堆）。
• 线段树 (Segment Tree) ：每个节点代表一个区间，支持区间查询与更新。常用于动态范围统计，例如区间最值、区间和。
• 哈夫曼树 (Huffman Tree) ：构造带权路径最短的二叉树，用于无损数据压缩。常用于 zip 压缩、jpeg 编码。
• 并查集 (Union-Find) ：森林表示集合，支持合并与查找操作。常用于连通性问题，例如社交网络好友关系。
• KD 树 (K-Dimensional Tree) ：二叉树，交替按不同维度划分空间。常用于多维数据近邻搜索，例如地理坐标查询的场景。

其他变种

• 二叉线索树 (Threaded Binary Tree) ： 利用空指针记录前驱/后继，加速遍历（中序、先序、后序）。
• 后缀树 (Suffix Tree) ：压缩字典树，存储字符串所有后缀。常用于模式匹配、生物信息学中 DNA 序列分析等场景。
• 决策树 (Decision Tree) ：机器学习中的分类与回归模型，通过树结构划分特征空间。

二、二叉树

1. 常见的二叉树

满二叉树：所有非叶子节点均有 2 个子节点，且所有叶子在同一层。

完全二叉树：除最后一层外，其他层均满，且最后一层节点左对齐。

备注：后面学习的二叉搜索树、AVL 等树，都是基于满二叉树或完全二叉树的。

2. 性质

3. 常见操作

1）遍历操作

[1] 先序遍历

先序遍历或前序遍历：根节点 ==> 左子树 ==> 右子树

遍历出来的顺序如下：A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> M -> G -> N -> O

// 先序遍历
preOrderTraverse() {
  this.preOrderTraverseNode(this.root)
}

private preOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    console.log(node.value)
    this.preOrderTraverseNode(node.left)
    this.preOrderTraverseNode(node.right)
  }
}

[2] 中序遍历

中序遍历：左子树 ==> 根节点 ==> 右子树

中序遍历的具体顺序可以看节点投影，投影出来的线性顺序就是遍历出来的顺序。

遍历出来的顺序如下：H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> M -> C -> N -> G -> O

// 中序遍历
inOrderTraverse() {
  this.inOrderTraverseNode(this.root)
}

private inOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    this.inOrderTraverseNode(node.left)
    console.log(node.value)
    this.inOrderTraverseNode(node.right)
  }
}

[3] 后序遍历

中序遍历：左子树 ==> 右子树 ==> 根节点

遍历出来的顺序如下：H -> I -> D -> J -> K -> E -> B -> L -> M -> F -> N -> O -> G -> C -> A

// 后序遍历
postOrderTraverse() {
  this.postOrderTraverseNode(this.root)
}

private postOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    this.postOrderTraverseNode(node.left)
    this.postOrderTraverseNode(node.right)
    console.log(node.value)
  }
}

[4] 层序遍历

// 层序遍历
levelOrderTraverse() {
  // 1.如果没有根节点, 那么不需要遍历
  if (!this.root) return

  // 2.创建队列结构
  const queue: TreeNode<T>[] = []
  // 第一个节点时根节点
  queue.push(this.root)

  // 3.遍历队列中所有的节点(依次出队)
  while (queue.length) {
    // 3.1.访问节点的过程
    const current = queue.shift()!
    console.log(current.value)

    // 3.2.将左子节点放入到队列
    if (current.left) {
      queue.push(current.left)
    }

    // 3.3.将右子节点放入到队列
    if (current.right) {
      queue.push(current.right)
    }
  }
}

三、二叉搜索树

1. 是什么

二叉搜索树（BST, Binary Search Tree），也称二叉排序树或二叉查找树。

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

• 非空左子树的所有键值小于其根结点的键值。
• 非空右子树的所有键值大于其根结点的键值。
• 左、右子树都是二叉搜索树。

由于上述性质，对 BST 进行中序遍历可以得到一个有序的序列。

2. 代码实现

1）基本结构

import Node from "../types/Node"

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null

  // 当前节点的父节点
  parent: TreeNode<T> | null = null

  // 判断当前节点是父节点的左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this)
  }

  // 判断当前节点是父节点的右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this)
  }
}

class BSTree<T> {
  private root: TreeNode<T> | null = null

  constructor(value: TreeNode<T>){
    this.root = value
  }
}

export {
  TreeNode,
  BSTree
}

2）用数组构建 BST

/**
 * arr - 要构建的二叉搜索树的序列
 */
static buildSearchTree(arr: number[]): BSTree<number> {
  if(arr === null || arr.length === 0) return null

  const root = new TreeNode(arr[0]) // 最上层的根节点
  const bst = new BSTree<number>(root)

  // 注意这里 i 是从 1 开始的，因为第一个元素已经根节点了
  for(let i = 1; i < arr.length; i++){
    this.insertNode(root, arr[i])
  }

  return bst
}

// 真正的插入操作
private insertNode(node: TreeNode<T>, value: T): void {
  const newNode = new TreeNode(value) // 根据传入value创建Node(TreeNode)节点

  if (newNode.value < node.value) { // 去左边继续查找空白位置
    if (node.left === null) { // node节点的左边已经是空白
      node.left = newNode
    } else {
      this.insertNode(node.left, newNode)
    }
  } else { // 去右边继续查找空白位置
    if (node.right === null) {
      node.right = newNode
    } else {
      this.insertNode(node.right, newNode)
    }
  }
}

3）插入操作

/* 插入数据的操作 */
insert(value: T): void {
  // 判断当前是否已经有了根节点
  if (!this.root) { // 当前树为空
    this.root = new TreeNode(value)
  } else { // 树中已经有其他值
    this.insertNode(this.root, value)
  }
}

4）搜索

[1] 最值

/* 获取最值操作: 最大值/最小值 */
getMaxValue(): T | null {
  let current = this.root
  while (current && current.right) {
    current = current.right
  }

  return current?.value ?? null
}

getMinValue(): T | null {
  let current = this.root
  while (current && current.left) {
    current = current.left
  }

  return current?.value ?? null
}

[2] 是否找到了指定值

重构前

/* 在二叉搜索树中搜索特定的值, 返回 boolean */
search(value: T): boolean {
  let current = this.root
  while (current) {
    // 找到了节点
    if (current.value === value) return true

    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }
  }

  return false
}

重构后

search(value: T): boolean {
  return !!this.searchNode(value)
}

[3] 查找节点

这里跟是否找到了指定值操作一样，无非就是返回节点。不过这里多了一步操作，就是在查找指定值节点的时候，设置父节点。

/* 在二叉搜索树中搜索特定的值, 并返回找到的节点 */
private searchNode(value: T): TreeNode<T> | null {
  let current = this.root
  let parent: TreeNode<T> | null = null

  while (current) {
    // 1.如果找到current, 直接返回即可
    if (current.value === value) {
      return current
    }

    // 2.继续向下找
    parent = current
    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }

    // 如果current有值, 那么current保存自己的父节点
    if (current) current.parent = parent
  }

  return null
}

5）查找前驱后驱节点

查找前驱节点

    10
   /  \
  5    15
 / \   / \
3   7 12  20
   / \
  6   8

就是查找当前节点在中序遍历中的前一个节点。例如上面的二叉搜索树，按照中序遍历出来的序列：

3 5 6 7 8 10 12 15 20

假设要查找 12 的前驱节点，就是 10。

function preNode(root, target){
  let current = root; // 缓存当前的节点
  let predecessor = null; // 存储前驱节点

  // 在 while 循环中查找前驱节点
  while(current !== null){
    if(current.value < target){
      // 因为当前节点的值小于目标值，它可能是一个前驱节点
      // 先暂时缓存起来
      // 这里之所以缓存，是为了应对目标节点的左子树为null的情况
      predecessor = current;
      current = current.right;
    } else if(current.value > target){
      current = current.left;
    } else {
      // 进入此分支，说明找到了当前的目标节点
      if(current.left !== null){
        // 如果有左子树，前驱就应该是左子树的最大值
        predecessor = getMaxValue(current.left);
      }
      break;
    }
  }

  // 出了 while 之后，那么前驱节点就应该找到了
  return predecessor;
}


preNode(bst, 15);

查找后驱节点

就是查找当前节点在中序遍历中的后一个节点。例如上面的二叉搜索树，查找 7 的后驱那就是 8。

function postNode(root, target){
  let current = root; // 缓存当前的节点
  let successor = null; // 存储后驱节点

  // 在 while 循环中查找后驱节点
  while(current !== null){
    if(current.value > target){
      // 因为当前节点的值大于目标值，它可能是一个后驱节点
      // 先暂时缓存起来
      // 这里之所以缓存，是为了应对目标节点的右子树为null的情况
      successor = current;
      current = current.left;
    } else if(current.value < target){
      current = current.right;
    } else {
      // 进入此分支，说明找到了当前的目标节点
      if(current.right !== null){
        // 如果有右子树，后驱就应该是右子树的最小值
        successor = getMinValue(current.right);
      }
      break;
    }
  }

  // 出了 while 之后，那么后驱节点就应该找到了
  return successor;
}

6）删除节点

删除节点，有三种情况：

1. 没有子树（叶子节点）的情况

   直接删除即可。

2. 只有一个子树的情况

   • 如果左子树为空，直接返回右子树，这样，当前节点被删除后，右子树接替它的位置。
   • 如果是右子树为空，和上面同理，返回左子树。

3. 有两个子树的情况

   这个情况，需要保证树的有序性。常用的方法就是中序后继法（中序后继替换）。

   中序后继替换指找到当前节点在中序遍历中的后一个节点来替换它。

[1] 重构前

remove (value: T): boolean {
  // 1.搜索: 当前是否有这个value
  const current = this.searchNode(value)
  if (!current) return false

  // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
  // 2.如果删除的是叶子节点
  if (current.left === null && current.right === null) {
    if (current === this.root) { // 根节点
      this.root = null
    } else if (current.isLeft) { // 父节点的左子节点
      current.parent!.left = null
    } else {
      current.parent!.right = null
    }
  }

  // 3.只有一个子节点: 只有左子节点
  else if (current.right === null) {
    if (current === this.root) {
      this.root = current.left
    } else if (current.isLeft) {
      current.parent!.left = current.left
    } else {
      current.parent!.right = current.left
    }
  }

  // 4.只有一个子节点: 只有右子节点
  else if (current.left === null) {
    if (current === this.root) {
      this.root = current.right
    } else if (current.isLeft) {
      current.parent!.left = current.right
    } else {
      current.parent!.right = current.right
    }
  }

  // 5.有两个子节点
  else {
    const successor = this.getSuccessor(current)
    if (current === this.root) {
      this.root = successor
    } else if (current.isLeft) {
      current.parent!.left = successor
    } else {
      current.parent!.right = successor
    }
  }

  return true
}

要删除的节点的子节点有两个，需要从子节点中找到比要删除节点的值要么小一点或大一点的节点。而这两个节点有特殊的名字。

• 前驱：比要删除节点的值要么小一点的节点叫前驱。
• 后继：比要删除节点的值要么大一点的节点叫后驱。

/* 实现删除操作 */
private getSuccessor (delNode: TreeNode<T>): TreeNode<T> {
  // 获取右子树
  let current = delNode.right
  let successor: TreeNode<T> | null = null
  while (current) {
    successor = current
    current = current.left
    if (current) { // 用于第 16 行代码的操作
      current.parent = successor
    }
  }

  // 拿到了后继节点
  if (successor !== delNode.right) { // 例如: 假设没有 8 节点, 删除 7, 后继节点为 9, 这时候不需要操作后继节点的 right
    successor!.parent!.left = successor!.right // 例如: 删除 15, 后继节点为 18, 需要把 19 节点给 20 节点的 left
    successor!.right = delNode.right
  }

  // 一定要进行的操作: 将删除节点的 left, 赋值给后继节点的 left
  successor!.left = delNode.left // 例如: 删除 7, 后继节点为 8, 需要把 5 节点给 8 的 left

  return successor!
}

[2] 重构后

remove(value: T): boolean {
  // 1.搜索: 当前是否有这个value
  const current = this.searchNode(value)
  if (!current) return false

  // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
  let replaceNode: TreeNode<T> | null = null
  if (current.left === null && current.right === null) {
    replaceNode = null
  } else if (current.right === null) {
    replaceNode = current.left
  } else if (current.left === null) {
    replaceNode = current.right
  } else {
    const successor = this.getSuccessor(current)
    replaceNode = successor
  }

  if (current === this.root) {
    this.root = replaceNode
  } else if (current.isLeft) {
    current.parent!.left = replaceNode
  } else {
    current.parent!.right = replaceNode
  }

  return true
}

四、平衡二叉树

1. 简介

1）为什么要有 AVL

例如这么一个序列：

[3, 5, 1, 6, 7, 2, 9, 8]

最终构建出来的二叉树为：

在使用二叉搜索树进行搜索的时候，搜索的次数取决二叉搜索树的层数。层数越少，那么搜索的次数自然就越少。

2）是什么

在树的任何一个结点处，其左子树和右子树的高度差（有时也称为“深度差”）不会超过一定的限制（通常是 1）。这种限制保证了树的整体“平衡性”，从而使得在最坏情况下进行搜索、插入、删除等操作时，都能保持接近 $O(logn)$ 的时间复杂度。

结论

• 结点的平衡因子 = 左子树高 - 右子树高。
• 平衡二叉树结点的平衡因子的值只可能是 −1、0 或 1。

示例

下面是一些非平衡二叉树的示例：

A
 \
  B
   \
    C
     \
      D

    A
   / \
  B   C
 / \
D   E
   /
  F
 /
G

下面就是一个平衡的二叉树

    A
   / \
  B   C
 / \
D   E

3）左旋与右旋

保持树平衡的法宝是什么？

• 右旋（LL）：找到失衡节点（root），以失衡节点的左孩子为轴心向右旋转失衡节点（root）。之后将冲突的右孩变左孩。
• 左旋（RR）：找到失衡节点（root），以失衡节点的右孩子为轴心向左旋转失衡节点（root）。之后将冲突的左孩变右孩。

备注：上图中 root 节点也可以叫 grand；Pivot 也可以叫 parent；还有一个节点可以叫 current。

什么时候左旋或右旋

• 插入操作：在 AVL 树中插入一个节点后，沿着新节点向根节点回溯寻找失衡节点，一旦找到第一个失衡节点并对其进行旋转修复后，整棵树就重新平衡了，不需要再去检查更上层的祖先节点。

  • 为什么要沿着新节点向根节点回溯（计算哪个祖先节点失衡了）？

    因为当插入一个新节点时，这个新节点所在的子树高度可能会增加 1。这个高度的增加会向上传递，导致祖先节点的左子树或右子树高度差发生变化。

  • 为什么找到失衡节点后对其进行平衡，就不在往上在找了？

    在 AVL 树的插入操作中，引发失衡的原因是某个子树的高度增加了 1。而当我们通过旋转操作重新平衡这棵子树后，这棵子树的总高度会减 1，刚好恢复到插入新节点之前的高度！

• 删除操作：在 AVL 树中删除节点时，如果删除导致某节点失衡，进行旋转修复后，这棵局部子树的整体高度可能会降低。这个高度的降低会继续向上传递，可能导致更上层的祖先发生失衡。所以，删除操作最多可能需要一路旋转到根节点。

总结：插入操作只需局部修复一次（包含双旋）。删除操作必须挨个检查每一个祖先节点。

树失衡后，到底是左旋还是右旋？

2. 平衡树节点封装

1）结构搭建

class AVLTreeNode<T> extends TreeNode<T> {
  // 重新覆盖下面属性是保证获取到的 left/right 节点的类型是 AVLTreeNode
  left: AVLTreeNode<T> | null = null
  right: AVLTreeNode<T> | null = null
  parent: AVLTreeNode<T> | null = null

  // 这个属性可以不要, 因为可以封装方法递归动态获取实时高度
  // height: number = 1
}

2）公共方法

判断是否平衡

/* 获取每个节点的高度 */
private getHeight(): number {
  const leftHeight = this.left ? this.left.getHeight(): 0
  const rightHeight = this.right ? this.right.getHeight(): 0

  return Math.max(leftHeight, rightHeight) + 1
}

/* 权重: 平衡因子(左边height - 右边height) */
private getBalanceFactor(): number {
  const leftHeight = this.left ? this.left.getHeight(): 0
  const rightHeight = this.right ? this.right.getHeight(): 0

  return leftHeight - rightHeight
}

/* 直接判断当前节点是否平衡 */
get isBalanced(): boolean {
  const factor = this.getBalanceFactor()
  return factor >= -1 && factor <= 1 // -1 0 1
}

给一个节点，需要获取到高度最高的那个子树的根节点。

/* 获取更高子节点 */
public get higherChild(): AVLTreeNode<T> | null {
  const leftHeight = this.left ? this.left.getHeight(): 0
  const rightHeight = this.right ? this.right.getHeight(): 0

  if (leftHeight > rightHeight) return this.left
  if (leftHeight < rightHeight) return this.right
  return this.isLeft ? this.left: this.right
}

3）旋转方法

[1] 右旋 LL

思路

1. 找到轴心节点 (处理轴心节点)
   const pivot = root.left
   pivot.parent = root.parent

2. 处理 pivot 的右子节点
   root.left = pivot.right
   if (pivot.right) {
     pivot.right.parent = root
   }

3. 处理 root 根节点
   pivot.right = root
   root.parent = pivot

4. 最后一步: pivot 应该挂载在哪里?
   pivot.parent
     情况一: pivot.parent 为 undefined/null
            avltree.root = pivot
     情况二: pivot 是父节点的左子节点
            pivot.parent.left = pivot
     情况三: pivot 是父节点的右子节点
            pivot.parent.right = pivot

实现代码

/* 旋转操作: 右旋转 */
rightRotation() {
  const isLeft = this.isLeft
  const isRight = this.isRight

  // 1.处理pivot节点
  const pivot = this.left!
  pivot.parent = this.parent

  // 2.处理pivot的right
  this.left = pivot.right
  if (pivot.right) {
    pivot.right.parent = this
  }

  // 3.处理this
  pivot.right = this
  this.parent = pivot

  // 4.挂载pivot
  if (!pivot.parent) { // pivot直接作为tree的根
    return pivot
  } else if (isLeft) { // pivot作为父节点的左子节点
    pivot.parent.left = pivot
  } else if (isRight) { // pivot作为父节点的右子节点
    pivot.parent.right = pivot
  }

  return pivot
}

[2] 左旋

leftRotation() {
  const isLeft = this.isLeft
  const isRight = this.isRight

  // 1.处理pivot
  const pivot = this.right!
  pivot.parent = this.parent

  // 2.处理pivot的left
  this.right = pivot.left
  if (pivot.left) {
    pivot.left.parent = this
  }

  // 3.处理root(this)
  pivot.left = this
  this.parent = pivot

  // 4.挂载整颗子树pivot
  if (!pivot.parent) {
    return pivot
  } else if (isLeft) {
    pivot.parent.left = pivot
  } else if (isRight) {
    pivot.parent.right = pivot
  }

  return pivot
}

3. 平衡树封装

1）结构搭建

class AVLTree<T> extends BSTree<T> {
}

2）代码实现

[1] 树的再平衡

假设找到了让树不平衡的节点，那如何让树恢复平衡？

class AVLTree<T> extends BSTree<T> {
  // 如何去找到不平衡的节点??? 先不管


  // 假设已经找到了, 那么我们如何让这个节点变的平衡
  /**
   * 根据不平衡的节点的情况(LL/RR/LR/RL)让子树平衡
   * @param root 找到的不平衡的节点
   */
  rebalance(root: AVLTreeNode<T>) {
    const pivot = root.higherChild
    const current = pivot?.higherChild

    let resultNode: AVLTreeNode<T> | null = null
    if (pivot?.isLeft) { // L: left
      if (current?.isLeft) { // LL: left left
        resultNode = root.rightRotation()
      } else { // LR: left right
        pivot.leftRotation()
        resultNode = root.rightRotation()
      }
    } else { // R: right
      if (current?.isLeft) { // RL: right left
        pivot?.rightRotation()
        resultNode = root.leftRotation()
      } else { // RR: right right
        resultNode = root.leftRotation()
      }
    }

    // 判断返回的pivot是否有父节点
    if (!resultNode.parent) {
      this.root = resultNode
    }
  }
}

[2] 插入的调整

平衡二叉树不需要从零在实现插入方法，继承自 BSTree 即可。但是需要在插入节点的时候调整平衡，怎么办？使用设计模式中的模板模式。

修改 BSTree 中的插入节点的方法：

export class BSTree<T> {
  protected createNode(value: T): TreeNode<T> {
    return new TreeNode(value)
  }

  protected checkBalance(node: TreeNode<T>, isAdd = true) {}

  /* 插入数据的操作 */
  insert(value: T) {
    // 1.根据传入value创建Node(TreeNode)节点
    const newNode = this.createNode(value)

    // 2.插入新节点到树中
    // …… 省略代码
    
    // 3.检测树是否平衡
    this.checkBalance(newNode)
  }

在平衡二叉树的类中重写 createNode 和 checkBalance 方法。

// 重写调用的createNode方法
protected createNode(value: T): TreeNode<T> {
  return new AVLTreeNode(value)
}

// 如何去找到不平衡的节点
checkBalance(node: AVLTreeNode<T>) {
  let current = node.parent
  while (current) {
    if (!current.isBalanced) {
      this.rebalance(current)
    }
    current = current.parent
  }
}

[3] 删除的调整

修改 BSTree 中的删除节点的方法。

remove(value: T): boolean {
  // 1.搜索: 当前是否有这个value
  const current = this.searchNode(value)
  if (!current) return false

  let delNode: TreeNode<T> = current // 要删除的节点

  // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
  let replaceNode: TreeNode<T> | null = null
  if (current.left === null && current.right === null) {
    // 删除的元素是叶子节点
    replaceNode = null
  } else if (current.right === null) {
    // 删除的元素只有左节点
    replaceNode = current.left
  } else if (current.left === null) {
    // 删除的元素只有右节点
    replaceNode = current.right
  } else {
    // 删除的元素有左子树和右子树
    const successor = this.getSuccessor(current) // 获取到后驱节点
    current.value = successor.value // 用后驱节点的值替换掉要删除节点的值
    delNode = successor // 要删除的节点变为了后驱节点
    this.checkBalance(delNode, false) // 平衡树
    return true
  }

  if (current === this.root) {
    this.root = replaceNode
  } else if (current.isLeft) {
    current.parent!.left = replaceNode
  } else {
    current.parent!.right = replaceNode
  }

  // 判断replaceNode
  if (replaceNode && current.parent) {
    replaceNode.parent = current.parent
  }

  // 删除完成后, 检测树是否平衡(传入的节点是那个真正从二叉树中被移除的节点)
  this.checkBalance(delNode, false)

  return true
}

优化平衡树的操作。

// 如何去找到不平衡的节点
checkBalance(node: AVLTreeNode<T>, isAdd = true) {
  let current = node.parent
  while (current) {
    if (!current.isBalanced) {
      this.rebalance(current)
      // 这个位置时旋转完成后的操作
      // break决定不会进一步去查找父节点有没有平衡的情况了
      // 添加的情况是不需要进一步向上查找的, 直接break
      // 删除的情况是需要进一步向上查找的, 不能break
      if (isAdd) break
    }
    current = current.parent
  }
}

📚任务，就是书写一个方法，来判断一颗树是否是平衡二叉树。

/**
 * 计算以 node 节点为根的子树的高度
 * 在计算的过程中会判断子树是否平衡
 * 如果子树不平衡，返回 - 1
 * 如果子树平衡，返回该子树的高度
 */
function checkHeight(node){
  // 如果节点为空，子树高度为 0
  if(node === null) return 0;
  
  // 接下来需要递归的去计算左子树和右子树的高度
  const leftHeight = checkHeight(node.left);
  // 如果左子树不平衡，直接返回 -1
  if(leftHeight === -1) return -1;
  
  const rightHeight = checkHeight(node.right);
  // 如果右子树不平衡，直接返回 -1
  if(rightHeight === -1) return -1;
  
  // 现在得到了左右子树各自的高度
  // 接下来计算左右子树高度差
  // 如果左右子树的高度差大于 1，说明当前的树不平衡，返回 -1
  if(Math.abs(leftHeight - rightHeight) > 1) return -1;
  
  // 返回以当前 node 节点为根节点，子树的高度
  // 这里看 node 节点的左右子树谁更大就取谁的值
  return Math.max(leftHeight, rightHeight) + 1
}

function isBalanced(root){
  return checkHeight(root) !== -1;
}

序列为 [4, 2, 7, 1, 3, 6, 5]，形成的二叉搜索树为：

      4
    /   \
   2     7
 /  \    /
1    3  6
       /
      5

序列为[10, 5, 15, 3, 7, 12, 20, 6, 8] ，形成的二叉搜索树为：

    10
   /  \
  5    15
 / \   / \
3   7 12  20
   / \
  6   8

五、红黑树

六、哈夫曼树

1. 基础知识

1）为什么需要

等长编码不会出现解码时出现歧义，但改为变长编码，若编码的前缀有重复部分，就会解码失败。

例如：使用变长编码，来编码 ABAACDC 数据。

• A: 0
• B: 1
• C: 10
• D: 11

0100101110

解码会遇到很大的问题。以前三位 010 为例：

• AC
• ABA

究其原因是因为一个字符的编码成为了另一个字符编码的前缀。

• B：1，但是 C 和 D 它们的编码都是 1 开头的。

BC --> 110 --> DA

因此，在进行编码的时候，不能让一个字符的编码成为另外一个字符的前缀。

使用哈夫曼树形成的哈夫曼编码：

1. 不会有歧义（不会有任何一个字符的编码是另外一个字符的前缀）。
2. 编出来的码是最短的。

2）术语

• 节点之间的路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

• 节点之间的路径长度：路径上的分支数目称作路径长度。

• 树的路径长度：从树的根节点到树中每一节点的路径长度之和。在节点数目相同的二叉树中，完全二叉树的路径长度最短。

• 树的带权路径长度 (Weighted Path Length of Tree，简记为 WPL)

  • 节点的权：在一些应用中，赋予树中节点的一个有某种意义的实数。

  • 节点的带权路径长度：节点到树根之间的路径长度与该节点上权的乘积。

  • 树的带权路径长度 (Weighted Path Length of Tree) ：树中所有叶子结点的带权路径长度之和。通常记为：WPL = (W1L1 + W2L2 + W3L3 + ... + WnLn)

    其中：W1 和 L1 分别表示叶节点的权值和到根节点之间的路径长度。

2. 哈夫曼树

1）简介

[1] 是什么

哈夫曼树定义：假设有 n 个权值 [W1, W2, .... WN]，构造有 n 个叶子的二叉树，每个叶子的权值是 n 个权值之一，这样的二叉树可以构造很多个，其中必有一个是树的带权路径长度最小的，这棵二叉树就称为最优二叉树（最优树）或哈夫曼树。

第一棵：WPL=7x2+5x2+2x2+4x2=36

第二棵：WPL=7x3+5x3+2x1+4x2=46

第三棵：WPL=7x1+5x2+2x3+4x3=35

其中第三棵树的 WPL 最小，它就是哈夫曼树。

[2] 为什么哈夫曼树是带权路径长度最小的

逻辑层面证明：每次只挑出当前森林里【权重最小】的两个节点，把它们合并成一个新节点。始终遵循最小的权重，被合并的次数最多。最大的权重，被合并的次数最少。

数学层面：

一棵哈夫曼树的 WPL 还刚好等于【这棵树里所有非叶子节点 (包含根节点) 的权重之和】。

为什么？因为一个叶子节点每向下走一层，它的权重就会被加进它父节点的总权重里传递上去。叶子由于深度为 L，它的权重在向上合并的过程中，实际上被重复加了 L 次。

因此，所有内节点（每次合并产生的新节点）的总和，刚好就是带权路径长度 WPL！

既然 WPL = 所有“合并产生的新节点”之和，那我们想要 WPL 最小，就要让每一次合并产生的新节点尽量小！

总结：哈夫曼树通过每次让【两个最小的权重】合并（也就是让最小的数字滚雪球滚得最多圈），完美保证了所有滚雪球形成的新节点总和永远是全宇宙最小的，全宇宙所有的合并方式里，总和最小的那个。这就是 WPL = 全体内节点权重之和 的美！

2）性质

① 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。

② 哈夫曼树的结点总数为 2n−1。

③ 哈夫曼树中不存在度为 1 的结点。

④ 哈夫曼树并不唯一，但 WPL 必然相同且为最优。

⑤ 高度最多 n-1。

3）构造哈夫曼树

1.构造森林全是根

2.选用两小造新树

3.删除两小添新人

4.重复二三剩单根

4）代码实现

/**
 * 哈夫曼节点类
 */
class HuffmanNode{
  constructor(char, freq, left = null, right = null){
    this.char = char; // 字符
    this.freq = freq; // 频率
    this.left = left; // 左子节点
    this.right = right; // 右子节点
  }
}

/**
 * str - 待编码的字符串
 * return - 返回一个对象，对象的键是对应的字符，对象的值是该字符所出现的次数
 * { 'a': 5, 'b': 2, ...}
 */
function getFrequencyMap(str){
  const freq = {};
  
  // 遍历字符串的每一个字符
  for(const ch of str){
    freq[ch] = (freq[ch] || 0) + 1;
  }
 
  return freq;
}

/**
 * str - 待编码的字符串
 * return - 构建的哈夫曼树所对应的根节点
 */
function buildHuffmanTree(str){
  // 1. 先得到字符串里面每一个字符出现的频率
  const freqMap = getFrequencyMap(str);
  
  // 这里得到的就是键所构成的数组，例如 ['A', 'B', 'C', ...]
  const uniqueChars = Object.keys(freqMap);
  // 做一下边界处理
  if(uniqueChars.length === 0) return null;
  if(uniqueChars.length === 1) {
    // 说明整个字符串里面只有一种字符，类似于 'AAAAAAAAAA...'
    // 那么这里我们就可以直接指定编码为 0
    return new HuffmanNode(uniqueChars[0], freqMap[uniqueChars[0]]);
  }
  
  // 代码来到这里，说明有多个字符
  // 首先将所有出现了的字符生成哈夫曼节点对象
  // 注意这里是一种字符就会生成一个哈夫曼节点对象
  let nodes = uniqueChars.map((ch)=>new HuffmanNode(ch, freqMap[ch]));
  
  // 接下来就是哈夫曼节点两两进行合并
  while(nodes.length > 1){
    nodes.sort((a, b) => a.freq - b.freq); // 首先按照频率进行排序
    const left = nodes.shift(); // 取出一个频率最小的作为左子节点
    const right = nodes.shift(); // 再取出一个频率最小的作为右子节点
    
    // 合并出新的子节点
    const newNode = new HuffmanNode(null, left.freq + right.freq, left, right);
    
    // 放回到数组里面
    nodes.push(newNode);
  }
  
  // 跳出上面的while循环，说明node数组的长度没有大于1，整个数组只剩1个节点
  // 这个节点就是整颗哈夫曼树的根节点
  return nodes[0];
}

3. 哈夫曼编码

1）性质

为什么哈夫曼编码能够保证是前缀编码？因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀。

为什么哈夫曼编码能够保证字符编码总长最短？因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。

因此得出以下性质：

性质1：哈夫曼编码是前缀编码。

性质2：哈夫曼编码是最优前缀编码。

2）原理

核心思想：出现频率高的字符用较短的编码，频率低的用较长编码。这种变长编码方式比固定长度编码（如 ASCII）能显著减少数据量。

构建哈夫曼树的关键步骤：统计字符频率，将每个字符视为一棵单节点树，每次选择频率最小的两棵树合并重复直到只剩一棵树。

生成每个字符编码：所要编码的每一个字符对应一个权重，根据权重构造出哈夫曼树，左边为 0，右边为 1。

3）代码实现

/**
 * 哈夫曼节点类
 */
class HuffmanNode{
  constructor(char, freq, left = null, right = null){
    this.char = char; // 字符
    this.freq = freq; // 频率
    this.left = left; // 左子节点
    this.right = right; // 右子节点
  }
}

/**
 * str - 待编码的字符串
 * return - 返回一个对象，对象的键是对应的字符，对象的值是该字符所出现的次数
 * { 'a': 5, 'b': 2, ...}
 */
function getFrequencyMap(str){
  const freq = {};
  
  // 遍历字符串的每一个字符
  for(const ch of str){
    freq[ch] = (freq[ch] || 0) + 1;
  }
 
  return freq;
}

/**
 * str - 待编码的字符串
 * return - 构建的哈夫曼树所对应的根节点
 */
function buildHuffmanTree(str){
  // 1. 先得到字符串里面每一个字符出现的频率
  const freqMap = getFrequencyMap(str);
  
  // 这里得到的就是键所构成的数组，例如 ['A', 'B', 'C', ...]
  const uniqueChars = Object.keys(freqMap);
  // 做一下边界处理
  if(uniqueChars.length === 0) return null;
  if(uniqueChars.length === 1) {
    // 说明整个字符串里面只有一种字符，类似于 'AAAAAAAAAA...'
    // 那么这里我们就可以直接指定编码为 0
    return new HuffmanNode(uniqueChars[0], freqMap[uniqueChars[0]]);
  }
  
  // 代码来到这里，说明有多个字符
  // 首先将所有出现了的字符生成哈夫曼节点对象
  // 注意这里是一种字符就会生成一个哈夫曼节点对象
  let nodes = uniqueChars.map((ch)=>new HuffmanNode(ch, freqMap[ch]));
  
  // 接下来就是哈夫曼节点两两进行合并
  while(nodes.length > 1){
    nodes.sort((a, b) => a.freq - b.freq); // 首先按照频率进行排序
    const left = nodes.shift(); // 取出一个频率最小的作为左子节点
    const right = nodes.shift(); // 再取出一个频率最小的作为右子节点
    
    // 合并出新的子节点
    const newNode = new HuffmanNode(null, left.freq + right.freq, left, right);
    
    // 放回到数组里面
    nodes.push(newNode);
  }
  
  // 跳出上面的while循环，说明node数组的长度没有大于1，整个数组只剩1个节点
  // 这个节点就是整颗哈夫曼树的根节点
  return nodes[0];
}

/**
 * root - 哈夫曼树的根节点
 * return - 返回对应的哈夫曼编码表 { a: '00', b : '11'}
 */
function buildHuffmanCodes(root){
  const codes = {}; // 存储生成的哈夫曼编码表
  
  // 用于深度遍历哈夫曼树的辅助方法
  function traverse(node, prefix){
    if(!node) return;
    
    if(node.char !== null){
      // 说明是叶子节点，需要保存对应的编码
      codes[node.char] = prefix;
      return
    }
    
    // 代码来到这儿，说明不是叶子节点
    // 继续深度遍历
    traverse(node.left, prefix + "0"); // 深度遍历左分支，并且因为是左分支，前缀加0
    traverse(node.right, prefix + "1"); // 深度遍历右分支，并且因为是右分支，前缀加1
  }
  traverse(root, "");
  return codes;
}

/**
 * str - 待编码的字符串
 * codes - 对应的哈夫曼编码表，例如 { A: '0', C: '10', B: '110', D: '111' }
 */
function huffmanEncode(str, codes){
  let encodedResult = ""; // 存储编码后的结果
  
  for(const ch of str){
    encodedResult += codes[ch];
  }
  
  return encodedResult;
}

/**
 * encodedStr - 编码后的字符串，例如 0110001011110
 * root - 哈夫曼树的根节点
 */
function huffmanDecode(encodedStr, root){
  let decodedResult = ""; // 存储解码后的结果
  
  let currentNode = root; // 暂存树的根节点
  
  // 遍历编码后的字符串的每一位
  for(const bit of encodedStr){
    if(bit === "0"){
      // 根据哈夫曼的核心思想，0 处于左分支
      currentNode = currentNode.left;
    } else {
      // 1 处于右分支
      currentNode = currentNode.right;
    }
    
    if(currentNode.char !== null){
      // 进入此分支，说明进入到了叶子节点，叶子节点代表具体的字符
      decodedResult += currentNode.char;
      currentNode = root; // 重新回到根节点，每一次解析出来一个字符，都需要重新回到根节点
    }
  }
  
  return decodedResult;
}

第三章：堆

这里的堆指的是二叉堆，也属于二叉树（完全二叉树）中的一个类型，跟二叉搜索树、AVL 等一样。

一、简介

二叉堆在计算机科学中是一种非常著名的数据结构，由于它能高效、快速的找出最大值、最小值，常常被用于优先队列。它也被用于著名的排序算法中。

二叉堆分为两种：

1. 最小堆：每个子节点都大于等于父节点，因此在最小堆中可以快速找出最小值。
2. 最大堆：每个子节点都小于等于父节点，因此在最大堆中可以快速找出最大值。

二叉堆本质上是一颗完全二叉树，但是和前面介绍过的二叉搜索树又有一定的区别：

• 二叉搜索树：左侧子节点总是比父节点小，右侧子节点总是比父节点大。
• 二叉堆：不需要遵循二叉搜索树的原则。

[4, 2, 7, 1, 3, 6, 5]

二叉堆的存储

使用数组来存储二叉堆。

已知一个节点的索引下标值 index，可以求出：

1. 左子节点的下标值：2 * index + 1

2. 右子节点的下标值：2 * index + 2

3. 父节点的下标值：

   根据左子节点计算出父节点的下标：Math.floor((index - 1) / 2)

   根据右子节点下标 $C$ 计算出父节点的下标：$P=\lfloor \frac{C-2}{2}\rfloor =\lfloor \frac{C}{2}\rfloor -1$

二、最大堆实现

1. 堆结构搭建

export default class Heap<T> {
  // 属性
  private data: T[] = []
  private length: number = 0

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  // 辅助方法
  peek(): T | undefined {
    return this.data[0]
  }

  size() {
    return this.length
  }

  isEmpty() {
    return this.length === 0
  }
}

2. 常见操作

1）插入

insert(value: T) {
  // 1.将元素放到数组的尾部
  this.data.push(value)
  this.length++

  // 2.维护最大堆的特性 (最后位置的元素需要进行上滤操作)
  this.heapify_up()
}

插入后维护最大堆（上滤）。

heapify_up() {
  let index = this.length - 1
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2)
    if (this.data[index] <= this.data[parentIndex]) {
      break
    }
    this.swap(index, parentIndex)
    index = parentIndex
  }
}

2）删除

extract(): T | undefined {
  // 1.判断元素的个数为0或者1的情况
  if (this.length === 0) return undefined
  if (this.length === 1) {
    this.length--
    return this.data.pop()!
  }

  // 2.提取并且需要返回的最大值
  const topValue = this.data[0]
  this.data[0] = this.data.pop()!
  this.length--

  // 3.维护最大堆的特性: 下滤操作
  this.heapify_down()

  return topValue
}

删除后维护最大堆（下滤）。

private heapify_down() {
  // 3.1.定义索引位置
  let index = 0

  while (2 * index + 1 < this.length) {
    // 3.2.找到左右子节点
    let leftChildIndex = 2 * index + 1
    let rightChildIndex = leftChildIndex + 1

    // 3.3.找到左右子节点较大的值
    let largerIndex = leftChildIndex
    if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
      largerIndex = rightChildIndex
    }

    // 3.4.较大的值和index位置进行比较
    if (this.data[index] >= this.data[largerIndex]) {
      break
    }

    // 3.5.交换位置
    this.swap(index, largerIndex)
    index = largerIndex
  }
}

3）原地建堆

buildHeap(arr: T[]) {
  // 1.使用arr的值: 数组/长度
  this.data = arr
  this.length = arr.length

  // 2.从第一个非叶子节点, 开始进行下滤操作
  const start = Math.floor(this.length / 2 - 1)
  for (let i = start; i >= 0; i--) {
    this.heapify_down(i)
  }
}

三、最小堆实现

1. 代码实现

// utils.js
const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
}

function defaultCompare(a, b){
  if(a === b) return Compare.EQUALS
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}

export {
  defaultCompare
}

import { defaultCompare } = from "./utils"

// 最小堆类
class MinHeap{
  /**
   * compareFn - 比较方法
   */
  constructor(compareFn = defaultCompare){
    this.compareFn = compareFn;
    this.heap = []; // 用于存储最小堆所有元素
  }
  // 获取左子节点下标
  getLeftIndex(index){
    return 2 * index + 1;
  }
  // 获取右子节点下标
  getRightIndex(index){
    return 2 * index + 2;
  }
  // 获取父节点
  getParentIndex(index){
    if(index === 0) return undefined;
    return Math.floor((index - 1) / 2);
  }
  // 获取当前最小堆的最小值
  // 最小堆中，堆顶的元素就是最小的，是数组的第一个元素
  findMini(){
    return this.isEmpty() ? undefined : this.heap[0];
  }
  // 还有一些工具方法
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.size() <= 0;
  }
  clear() {
    this.heap = [];
  }
}

第四章：图

一、简介

图是网络结构的抽象模型，由一组顶点和边组成。下图就是一个典型的图结构：

2. 相关术语

1. 顶点：图里面一个一个数据元素被称之为顶点。之前在线性表中称之为元素，树里面称之为节点。

   另外，线性表可以没有元素（空表），树里面可以没有节点（空树），但是在图结构中不能够没有顶点。

2. 相邻顶点：由一条边连接在一起的两个顶点，称之为相邻顶点。

3. 度：一个顶点的相邻顶点的数量。

   出度：指向其他相邻顶点的边。

   入度：指向我自己的边。

4. 路径：指的是一连串顶点序列。其中有一个概念称之为简单路径，指的就是不包含重复顶点的路径。

5. 回路 / 环：从某一个顶点出发，最后回到该顶点，形成了一个闭环。环也会算作是一个简单路径。

3. 分类

1）无向图和有向图

1. 无向图：顾名思义就是顶点之间是没有方向的

由于是无方向的，因此连接 A 和 D 的边，可以表示为 (A, D)，也可以写成(D, A)。对于无向图来讲，G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {(A,B), (B,C), (C,D), (D,A), (A,C)}

在无向图中，如果每一个顶点都和其他所有顶点相连，则称该无向图为无向完全图。如下图所示：

一个含有 n 个顶点的无向完全图拥有 $\frac{n\ast (n-1)}{2}$ 条边。例如上面的无向完全图有 4 个顶点，根据公式计算出最多拥有 6 条边。

2. 有向图：顶点之间有明确的方向

有向图是有方向的，使用尖括号来表示，尖括号中的第一个节点表示 tail，第二个节点表示 head。例如上图为 G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {<A,D>, <B,A>, <C,A>, <B,C>}。

在有向图中，如果任意两个顶点之间都存在方向相反的指向，称之为有向完全图。例如下图就是一个有向完全图：

一个含有 n 个顶点的无向完全图拥有 $n\ast (n-1)$ 条边。例如上面的有向完全图有 4 个顶点，根据公式计算出最多拥有 12 条边。

2）无权图和加权图

图还可以是加权的。如下图所示，加权图的边被赋予了权值。

3）子图

假设有两个图，一个图是 G = (V, {E})，另一个图是 G' = (V', {E'})，如果

$$\begin{array}{rl}{V}^{\prime }& \subseteq V\\ E^{\prime }& \subseteq E\end{array}$$

那么我们称 G' 为 G 的子图。

举个例子：

4）联通图

通常指的是无向图。如果一个无向图中的任意两个顶点都存在一条可以相互到达的路径，那么这个图称为“联通图”。反之则成为“非联通图”。也就是说：

• 联通图：整张图只构成一个联通块，任意两顶点之间都能到达。
• 非联通图：图中出现“孤立”或“分块”的情况。

那么有向图中存不存在联通的概念呢？其实也存在，分为强联通和弱联通：

• 强联通：对于图中的任意两个顶点 V1 和 V2，都有从 V1 到 V2 的有向路径，并且也有从 V2 到 V1 的有向路径。这样的图被称之为强联通图。
• 弱联通：如果将有向图的所有有向边都看作无向边，能形成一幅联通图，则称该有向图是弱连通的。也就是说，忽略了方向后，任意两点间还是能连通，但不一定存在相互可达的有向路径。

4. 图的表示

顶点：数组或集合 set 存放数据。不过实际代码中也可以不定义存放顶点的变量，因为顶点的数据包含在了边的 Map 映射里的 key 中。

边：使用邻接矩阵或邻接表存放数据。

1）邻接矩阵

[1] 是什么

本质上就是使用一个二维数组来存储图。举个例子，假设有如下的有向图：

那么使用一个二维数组存储的结构如下：

$$\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}\right]$$

每一行代表一个顶点，每一列也代表一个顶点。例如上面的图有 5 个顶点，那么这个二维数组就是 $5\times 5$ 的二维数组。如果是 n 个顶点，那么这个二维数组就是 $n\times n$。

其中 1 表示顶点之间是有连接关系的。如 V1 顶点连接 V2，因此第一行第二列就是 1、V1 顶点连接 V4，因此第一行第四列就是 1。

接下来是无向图，如下：

使用邻接矩阵的表示法来表示的话，如下：

$$\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 1& 1\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\end{array}\right]$$

因为无向路是没有方向的，因此 V1 顶点连接 V2 顶点的同时，V2 顶点也连接 V1 顶点。

带边权的图

另外，我们知道图可以是带边权的，此时在二维数组中存储的就是具体的边权值，而非简单的记入 1。

下面是具体的例子。首先是带边权的有向图：

表示出来就是：

$$\left[\begin{array}{ccccc}\mathrm{\infty }& 5& \mathrm{\infty }& 4& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4\\ \mathrm{\infty }& 1& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$$

注意，现在没有相连的两个顶点，不能用 0 来表示，因为 0 会存在歧义，被误解为边权值。JS 里面就可以使用 Infinity。

下面是带边权的无向图示例：

表示出来就是：

$$\left[\begin{array}{ccccc}\mathrm{\infty }& 5& \mathrm{\infty }& 4& \mathrm{\infty }\\ 5& \mathrm{\infty }& 1& \mathrm{\infty }& 4\\ \mathrm{\infty }& 1& \mathrm{\infty }& 2& 2\\ 4& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 4& 2& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$$

[2] 优缺点

优点

（1）容易判断两个顶点是否有边，例如要判断 V1 和 V2 这两个顶点是否有边，只需要看二维数组 arr[0][1] 和 arr[1][0] 是否有值即可。

（2）容易计算顶点的度。例如 V2 顶点的出度，指的是 V2 顶点指向其他边的数量，下图中 V2 顶点的出度就是 1，入度指的是指向当前顶点的边的数量，V2 的入度就为 2。

上图使用邻接矩阵表示出来：

$$\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}\right]$$

该顶点对应的行的 1 的数量就是该顶点出度的数量，该顶点对应的列的 1 的数量就是入度的数量。

缺点

（1）统计边的数量的效率较低，需要去遍历二维数组，时间复杂度为 O(n²)。

（2）空间复杂度高，因为是二维数组来存储，因此空间复杂度也是 O(n²)。

2）邻接表

例如下面的图：

上面的图虽然有 5 个顶点，但是仅仅有顶点 2 连接顶点 1，如果用上面我们介绍过的邻接矩阵的方式来存储的话，就是：

$$\left[\begin{array}{ccccc}\mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ 9& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$$

上面的二维数组，仅仅只存储了一个 9，其他空间都浪费掉了。因此这里可以考虑使用邻接表的方式来存储。

邻接表核心思想

邻接表的核心思想是使用一个一维数组来存储所有的顶点，因此有多少个顶点，这个一维数组的长度就是多少。数组里面的每一项是一

个链表，链表会存储和该顶点连接的所有其他顶点。(tips: 实际代码中会使用 JS 内置的 Map 数据类型来实现邻接表)

我们还是来看一个具体的例子，假设还是下面的有向图：

那么使用数组存储的结构如下：

数组的每一项，是一个链表。这里以 V1 顶点为例。V1 指向了 V2 和 V4，V2 和 V4 这两个顶点在数组中的下标分别为 1 和 3，因此整个链表如蓝色部分所示。

注意这里 V2 和 V4 并不存在具体的顺序，因此在链表中的表现也可以是下标为 3 的顶点在前面，下标为 1 的顶点在后面。

因此，上面的有向图使用邻接表来存储的话，完整的邻接表为：

搞清楚了有向图后，无向图基本也是相同的道理，仅仅是链表的长度会更长一些，因为会包含出度和入度。例如下面的无向图：

使用邻接表的方式来存储的话，完整的数组结构如下图：

二、图的代码实现

1. 基本结构

class Graph<V, E> {
  // 顶点 (可以不定义, 使用 map 类型的 adjList 变量中的 key 代替, 这样就能少维护一个变量)
  private verteces: V[] = []
  // 通过 map 来存储所有顶点以及所有出边的信息, 最终 map 所存储的信息大致如下
  // Map {
  //   'A' => [{node: 'B', weight: 2}, {node: 'C', weight: 1}],
  //   'B' => [{node: 'C', weight: 3}],
  //   'C' => [],
  // }
  private adjList: Map<V, E[]> = new Map() // 存储边的, 使用邻接表

  constructor(isDirected = false){
    this.isDirected = isDirected;
  }
}

export {
  Graph
}

接下来实现一些辅助方法。

// 获取图中所有的顶点列表
getVertices(): V[] {
  return [...this.adjList.keys()];
}

// 获取图中所有的边
getEdges(): [V, V][] {
  let edges = []; // 这个数组就存储所有的边
  for(let [vertex, neighbors] of this.adjList){
    for(let {node} of neighbors){
      edges.push([vertex, node]); // 数组的每一项是 [起点节点，终点节点]
    }
  }
  return edges;
}

// 统计图中所有边的数量
edgeCount(): number {
  let count = 0; // 计数器，对边进行计数
  for(let [_, neighbors] of this.adjList){
    count += neighbors.length;
  }

  // 如果是无向图，每条边在两个顶点的邻接表中会出现两次，需要除以2
  return this.isDirected ? count : count / 2;
}

// 判断图中是否存在某一条边
// src - 起点
// dest - 终点
hasEdge(src: V, dest: V): boolean {
  if(!this.adjList.has(src)) return false;
  return this.adjList.get(src).some(nodeObj => nodeObj.node === dest);
}

2. 添加操作

添加操作分为两个：

1. 添加顶点

   g.addVertex('A');

2. 添加边

   g.addEdge('A', 'B', 5);

代码如下：

/**
 * 添加一个顶点到图中。
 * @param {*} vertex - 新顶点的名称或标识
 */
addVertex(vertex: V): void {
  // 将顶点添加到set中
  if(!this.verteces.has(vertex)){
    this.verteces.add(vertex)
  }
  // 创建一个邻接表中的数组
  if(!this.adjList.has(vertex)){ // 先判断主要是防止现有数据被覆盖
    this.adjList.set(vertex, []);
  }
}

/**
 * 添加一条边 (支持有向/无向、支持权重)
 * @param {*} src - 边的起点
 * @param {*} dest - 边的终点
 * @param {number} [weight=1] - 该边的权重 (可选, 默认1)
 */
addEdge(src: V, dest: V, weight? = 1): void {
  // 首先需要判断一下，起点和终点是否存在于 map 中
  // 如果没有，需要先添加对应的顶点
  if(!this.adjList.has(src)) this.addVertex(src);
  if(!this.adjList.has(dest)) this.addVertex(dest);

  // 添加边
  const srcNeighbors = this.adjList.get(src); // 先获取起点对应的连接顶点数组
  // 接下来需要检查一下，看是否已经有了这条边
  let hasExist = srcNeighbors.some(nodeObj => nodeObj.node === dest);
  if(!hasExist){ // 不存在才添加
    srcNeighbors.push({node : dest, weight})
  }

  // 如果是无向图，还需要添加 dest --> src
  if(!this.isDirected){
    const destNeighbors = this.adjList.get(dest); // 先获取起点对应的连接顶点数组
    // 接下来需要检查一下，看是否已经有了这条边
    let hasExist = destNeighbors.some(nodeObj => nodeObj.node === src);
    if(!hasExist){
      destNeighbors.push({node : src, weight})
    }
  }
}

3. 删除操作

同样分为删除顶点和删除边

g.removeVertex("B");
g.removeEdge("A", "C");

实现代码：

/**
 * 移除一个顶点, 以及与它相关的所有边 (出边和入边)
 * @param {*} vertex - 要移除的顶点
 */
removeVertex(vertex: V): void {
  if(!this.verteces.has(vertex) && !this.adjList.has(vertex)) return;

  // 开始进行删除操作

  // 这里只是删除了对应的顶点以及顶点对应的边的集合
  this.verteces.delete(vertex);
  this.adjList.delete(vertex);

  // 还有一个很重要的步骤, 删除其他顶点对该顶点的指向
  for(let [key, edgeArr] of this.adjList.entries()){
    this.adjList.set(key, edgeArr.filter(nodeObj => nodeObj.node !== vertex))
  }
}

/**
 * 移除一条边
 * @param {*} src - 边的起点 A
 * @param {*} dest - 边的终点 B
 */
removeEdge(src: V, dest: V): void {
  if(!this.adjList.has(src)) return;

  // 接下来进行过滤操作，假设删除 AB 这条边
  this.adjList.set(
    src,
    this.adjList.get(src).filter(nodeObj => nodeObj.node !== dest)
  )

  // 注意：如果是无向图，也需要移除 dest --> src 这条边
  if(!this.isDirected && this.adjList.has(dest)){
    this.adjList.set(
      dest,
      this.adjList.get(dest).filter(nodeObj => nodeObj.node !== src)
    )
  }
}

4. 遍历

1）广度优先搜索 BFS

广度优先遍历，用一句话来概括其核心思路就是层层扩散。这里我们还是先以一个有向图为例：

首先我们选择 V1 作为起始顶点，那么：

第一层：V1
第二层：V2 V4
第三层：V5 V3

当 V1 作为顶点时，它的下一层就是 V2 和 V4 这两个顶点，然后取 V2 找它的下一层，就是 V5，取 V4 找它的下一层就是 V3。注意在寻找下一层顶点的时候，要按照上一层顶点的顺序来找。例如，在第二层的时候，V2 在 V4 前面，因此在开始第三层的时候，先找 V2 的下一层顶点，然后再找 V4 的下一层顶点。最终，按照广度优先遍历出来的顺序为：V1 → V2 → V4 → V5 → V3。

另外，广度优先遍历的顺序，同样不是唯一的。例如在上面的例子中，第二层我们把 V4 放在前面，V2 放在后面，导致第三层也会受到影响。倘若第二层将 V4 放在 V2 前面，那么遍历出来的顺序就是 V1 → V4 → V2 → V3 → V5。

对于一个无向图，广度优先遍历的思路也是一样的。例如下面的无向图：

其遍历的路径有（括号表示层数）：

(V1) → (V2 → V4) → (V3 → V5)
(V1) → (V2 → V4) → (V5 → V3)
(V1) → (V4 → V2) → (V3 → V5)

代码实现

/**
 * 广度优先搜索 (BFS), 从指定顶点开始遍历。
 * @param {*} startVertex - 起始顶点
 * @returns {Array} 返回按访问顺序得到的顶点列表
 */
bfs(startVertex: V): V[] {
  if(!this.adjList.has(startVertex)) return [];

  const result = []; // 存储最终的结果
  const visited = new Set(); // 创建Set结构, 记录某一个顶点是否被访问过
  visited.add(startVertex);
  const queue = []; // 需要将每一层的顶点加入到队列里面
  queue.push(startVertex);

  // 遍历队列中每一个顶点
  while(queue.length > 0){
    const current = queue.shift()!; // 先拿到这个顶点
    result.push(current);

    // 接下来就需要寻找该顶点对应的下一层
    for(let nodeObj of this.adjList.get(current)){
      const v = nodeObj.node;
      if(!visited.has(v)){
        visited.add(v);
        queue.push(v);
      }
    }
  }

  return result;
}

2）深度优先搜索 DFS

图的深度优先搜索，其实就是深度优先遍历，如果用一句话来概括，那就是不撞南墙不回头。举个例子，假设有如下的有向图：

然后我们从 V1 出发，那就可以是这样的顺序：

V1 → V2 → V5 → V3

首先从 V1 出发，下一个顶点到 V2，然后再下一个顶点到 V5，，然后再下一个顶点到 V3。到了 V3 后发现后面没有顶点了，则回退到 V5，发现 V5 也没有其他的路，接着在回退到 V2，发现 V2 也没有其他的路，于是回退到 V1，然后访问 V4。因此整个遍历出来的顺序为：

V2，V2 也没有其他的路，于是回退到 V1，然后访问 V4 和 V3。因此整个遍历出来的顺序为：

V1 → V2 → V5 → V3 → V4

回到 V1 后，到下一个顶点 V4，从而完成了一整个图的遍历。

需要注意的是，深度优先遍历的路径不是唯一的，哪怕是从 V1 出发，也可以有如下不同的遍历路径：

V1 → V4 → V3 → V2 → V5
V1 → V4 → V3 → V5 → V2

在上面的例子中，我们选择了 V1 作为我们的起始顶点。那能不能选择其他顶点作为起始顶点呢？

其实也是可以的，例如这里我们选择 V2 作为起始顶点，那么 V2 能够走的路径就是：

V2 → V5

此时你会发现并没有遍历完整张图，所以就还需要再选择一个未遍历的顶点作为起始顶点来进行遍历。

一般来讲，我们可以选择一个入度为 0 的顶点来作为起始顶点，因此在上面的示例中，选择 V1 作为起始顶点是最合适的。

对于无向图的深度优先遍历，道理是一样的，不过相对于有向图，无向图能够走的边会更多一些。例如下面的无向图：

采用深度优先遍历能够走的路径有：

V1 → V2 → V3 → V4 (回退) → V5
V1 → V2 → V3 → V5 (回退) → V4
V1 → V2 → V5 → V3 → V4
V1 → V4 → V3 → V2 → V5
V1 → V4 → V3 → V5 → V2

一共有 5 条路径。

代码实现

dfs(startVertex: V): V[] {
  if(!this.adjList.has(startVertex)) return [];

  const visited = new Set(); // 创建Set结构, 记录某一个顶点是否被访问过
  const result = []; // 存储遍历的结果

  const dfsHelper = (vertex)=>{
    visited.add(vertex);
    result.push(vertex);

    for(let nodeObj of this.adjList.get(vertex)){
      const v = nodeObj.node;
      if(!visited.has(v)){
        // 进入该分支，说明当前这个节点还没有遍历到
        dfsHelper(v);
      }
    }
  }
  dfsHelper(startVertex);

  return result;
}

三、最小生成树

最小生成树（Minimum Spanning Tree, MST）：图结构转为树结构，且边权和最小。

树本身就是一种无环图。

1. 普里姆算法

1）核心思想

普里姆算法（Prim's Algorithm），是一种用于在加权无向联通图中寻找最小生成树的经典算法，其核心思想为：从一个顶点开始，逐步“扩张”树，把与当前树相连的最小权重边加入进来，直到包含图中所有顶点为止。

先确定一个起始顶点，之后把与点亮的点最近的那个点加进来，一直循环这个步骤，直到顶点全被加进来结束。

因此普里姆算法又被称之为加点法。假设现在要针对这个图寻找最小生成树：(tips: 以 A 为起始)

再看一个例子。(tips: 以 V1 为起始)

虽然一个图的最小生成树会根据起始顶点的不同，最终生成的结果不同。但是不管最终生成整样的最小生成树，边权值的总和一定是相等的。另外还有一个规律：针对 $n$ 个顶点的图，最终的最小生成树的边为 $n-1$。

普里姆算法是加节点的，跟边多边少没关系，更适合稠密图。

2）代码实现

对应的 this.adjList 的 Map 结构如下：

Map(5) {
  'A' => [ { node: 'B', weight: 4 }, { node: 'C', weight: 7 } ],
  'B' => [
    { node: 'A', weight: 4 },
    { node: 'D', weight: 6 },
    { node: 'C', weight: 8 }
  ],
  'D' => [
    { node: 'B', weight: 6 },
    { node: 'E', weight: 7 },
    { node: 'C', weight: 5 }
  ],
  'E' => [ { node: 'D', weight: 7 } ],
  'C' => [
    { node: 'A', weight: 7 },
    { node: 'B', weight: 8 },
    { node: 'D', weight: 5 }
  ]
}

/**
 * startVertex - 指定的起始顶点
 * returns - 一个对象 { edges: [], totalWeight: 0}
 * edges 记录有哪些边，totalWeight 记录最小生成树的总权重
 */
primMST(startVertex){
  if(this.isDirected){
    // 进入此分支，说明当前是有向图
    // 有向图一般不太适用
    throw new Error("普里姆算法一般适用于无向图");
  }

  // 接下来判断一下图中是否存在这个起始顶点
  if(!this.adjList.has(startVertex)) return { edges: [], totalWeight: 0}

  // 获取所有的顶点
  const vertices = this.getVertices(); // ['A', 'B', 'C', 'D', 'E']

  const mstSet = new Set(); // 用来存储已经加入到了 MST 的顶点
  const dist = new Map(); // 记录一个顶点连接到已经生成的 MST 的最小权重
  const parent = new Map(); // 记录一个顶点连接到 MST 最优的那条边的“父顶点”

  // 接下来初始化 dist 和 parent
  for(let v of vertices){
    dist.set(v, Infinity);
    parent.set(v, null);
  }
  dist.set(startVertex, 0);
  	// dist = {
    //   A: 0,
    //   B: Infinity,
    //   C: Infinity,
    //   D: Infinity,
    //   E: Infinity
    // }
    // parent = {
    //   A: null,
    //   B: null,
    //   C: null,
    //   D: null,
    //   E: null
    // }
    // mstSet = { } (空)
  
  // 遍历所有的顶点，每一次遍历都会将一个顶点加入到 MST 里面
  for(let i = 0; i < vertices.length; i++){
    // 1. 首先需要找到还没有加入到 MST 并且 dist 是最小的顶点
    let current = null;
    let minDist = Infinity;

    for(let v of vertices){
      if(!mstSet.has(v) && dist.get(v) < minDist){
        minDist = dist.get(v);
        current = v;
      }
    }

    // 如果没有找到这样的顶点（可能图不联通之类的），提前结束
    if(current === null) break;

    // 代码来到这里，说明找到了，将选定的顶点加入到 MST 集合里面
    mstSet.add(current);

    // 现在 current（顶点）已经找到了，需要根据 current 顶点来更新 dist 以及 parent
    for(let neighborObj of this.adjList.get(current)){
      const neighbor = neighborObj.node; // 拿到该顶点（current）对应的邻居顶点
      const weight = neighborObj.weight; // 拿到该顶点（current）到邻居顶点的加权值

      // 接下来更新那些还没有加入 MST，并且存在最小边权的顶点
      if(!mstSet.has(neighbor) && weight < dist.get(neighbor)){
        dist.set(neighbor, weight);
        parent.set(neighbor, current);
      }
    }
  }
  	// i = 0, current = A
  	// mstSet = { 'A' }
  	// 找到 A 的邻居 B(weight = 4)，C(weight = 7)
  	// dist = { A:0, B:4, C:7, D:Infinity, E:Infinity }
  	// parent = { A:null, B:'A', C:'A', D:null, E:null }
  
  	// i = 1, current = B
  	// mstSet = { 'A', 'B' }
  	// 找到 B 的邻居 A(weight = 4) D(weight=6) C(weight=8)
  	// dist = { A:0, B:4, C:7, D:6, E:Infinity }
  	// parent = { A:null, B:'A', C:'A', D:'B', E:null }

  // 生成 MST 的边信息
  const mstEdges = [];
  let totalWeight = 0;

  for(let v of vertices){
    const p = parent.get(v);
    if(p !== null){
      const w = dist.get(v); // 获取到当前这个顶点加入到 MST 时的最小边权值
      mstEdges.push([p, v, w]);
      totalWeight += w;
    }
  }

  return {
    mstEdges,
    totalWeight
  }
}

2. 克鲁斯卡尔算法

1）核心思想

又被称之为加边法。

找图结构中权重最小的边，若找到的边在联通分量里，就丢弃，否则加入，直到所有点都在联通分量里结束。

例一：

例二：

2）代码实现

/**
 * Kruskal（克鲁斯卡尔）最小生成树算法，适用于无向图。
 * 返回生成树的所有边及其总权重。
 * @returns
 *   例如 { edges: [[ 'A', 'B', 4 ], [ 'C', 'D', 5 ], [ 'B', 'D', 6 ], [ 'D', 'E', 7 ]], totalWeight: 22 }
 */
kruskalMST() {
  // 如果是有向图，Kruskal 算法一般不适用，这里直接抛出异常
  if (this.isDirected) {
    throw new Error("克鲁斯卡尔算法一般用于无向图");
  }

  // 1. 需要收集所有的边 [src, dest, weight]
  // 除了简单收集以外，还需要去重，因为是无向图，每条边会出现两次 A-->B,B-->A
  // A < B 的情况才保留
  const edges = [];
  for(let [vertex, neighbors] of this.adjList){
    for(let {node, weight} of neighbors){
      // 比较顶点，避免重复的边
      if(vertex < node){
        edges.push([vertex, node, weight])
      }
    }
  }

  // 上面的代码执行完成后，edges 就会存储所有的边信息，并且没有重复的
  // edges = [
  //   ['A','B',4],  // A <-> B
  //   ['A','C',7],  // A <-> C
  //   ['B','D',6],  // B <-> D
  //   ['B','C',8],  // B <-> C
  //   ['D','E',7],  // D <-> E
  //   ['C','D',5],  // C <-> D
  // ]

  // 接下来就对 edges 按照边权值进行排序
  edges.sort((a, b) => a[2] - b[2]);
  // edges = [
  //   ['A','B',4], // 权重 4
  //   ['C','D',5], // 权重 5
  //   ['B','D',6], // 权重 6
  //   ['A','C',7], // 权重 7
  //   ['D','E',7], // 权重 7
  //   ['B','C',8], // 权重 8
  // ]

  const parent = new Map(); // 用于记录每个顶点的父节点
  const rank = new Map(); // 用于近似表示树的高度，从而在合并两颗树的时候，可以让矮的树挂到高的树下面。

  // 接下来对这两个 Map 进行初始化
  const vertices = this.getVertices(); // 获取所有的顶点 [ 'A', 'B', 'C', 'D', 'E' ]
  for(let v of vertices){
    parent.set(v, v);
    rank.set(v, 0);
  }
  // parent = {
  //   A: 'A',
  //   B: 'B',
  //   C: 'C',
  //   D: 'D',
  //   E: 'E'
  // }
  // rank = {
  //   A: 0,
  //   B: 0,
  //   C: 0,
  //   D: 0,
  //   E: 0
  // }

  // 接下来需要写一个辅助方法
  /**
   * x - 要查找根节点的元素
   * returns x 的根节点
   */
  // parent(A) = B  parent(B) = C  parent(C) = C
  // find(A)-->find(B)-->find(C)
  // 最终 find(A) 的返回值就是 C
  // 这里不仅仅是返回一个顶点的根，而且还做了路径压缩
  // parent.set(B, C)，递归回到外层后还执行了 parent.set(A, C)
  // 最终 A、B、C 的父节点都指向 C，并且以后再 find(A) 或者 find(B) 的时候，直接就得到根节点 C
  const find = (x) => {
    if(parent.get(x) !== x){
      // 如果 x 的父节点不是自己，说明 x 还没有到达根节点
      // 那么就递归的向上查找
      parent.set(x, find(parent.get(x)));
    }
    return parent.get(x);
  }

  // 接收两个顶点
  // 合并两个顶点的联通分量
  const union = (x, y)=>{
    const rootX = find(x); // 找到 x 的根节点
    const rootY = find(y); // 找到 y 的根节点

    // 如果已经在同一个联通分量
    if(rootX === rootY) return false;

    // 接下来是不等的情况，我们就需要合并
    if(rank.get(rootX) > rank.get(rootY)){
      // 说明 X 的树更高
      parent.set(rootY, rootX);
    } else if(rank.get(rootX) < rank.get(rootY)){
      // 说明 Y 树更高
      parent.set(rootX, rootY);
    } else {
      // rank 相等的时候，那么就随便选择一个来作为根
      parent.set(rootY, rootX)
      rank.set(rootX, rank.get(rootX) + 1);
    }
    return true;
  }
  // parent(A) = A, rank(A) = 1, 表示 A 是一颗独立的树，树高为 1
  // parent(B) = B, rank(B) = 0, 表示 B 也是一颗独立的树，但是这颗树要更矮一些
  // union(A, B)
  // rootX = A	rootY = B
  // parent.set(rootY, rootX); --> parent.set(B, A) 表示 B 现在是挂在 A 下面的

  // 最后就是生成返回的 MST 对应的信息
  let mstEdges = [];
  let totalWeight = 0;

  for(let [src, dest, weight] of edges){
    if(union(src, dest)){
      mstEdges.push([src, dest, weight]);
      totalWeight += weight;
    }
  }

  return {
    mstEdges,
    totalWeight
  }
}