Problem#

• 问题是从输入到正确输出的二元关系
• 通常通过可验证的谓词(性质)来判定正确输出
• 本课程的研究对象是在大规模通用输入空间上的问题
  • 非通用特例：教室内是否有同一生日的学生?
  • 通用：任意 n 个学生中是否有同一生日的学生?

Algorithm#

• 定义：将每个输入映射到单一输出的确定性过程
• 正确性：对每个问题输入都返回正确输出
• 示例：生日匹配算法
  1. 维护名字和生日的记录(初始为空)
  2. 按序访问每个学生:
     • 如记录中存在相同生日则返回配对
     • 否则将该生日添加到记录
  3. 若未找到匹配则返回None

Correctness#

• 小规模输入：使用情况分析
• 大规模输入：必须使用递归或循环
• 通常需要归纳法(induction)证明
• 生日匹配算法正确性证明示例：
  • 对记录中的学生数 $k$ 进行归纳
  • 基础情况：$k=0$，无匹配，成立
  • 归纳假设：$k$ 的情况成立
  • 归纳步骤：证明 $k+1$ 的情况

Efficiency#

• 衡量标准：算法执行的固定时间操作数
• 输入规模通常用 n 表示
• 渐进(Asymptotic)符号表示：
  • $O$ (上界), $\Omega$ (下界), $\Theta$ (紧界)
• 常见时间复杂度：
  • 常数时间：$\Theta(1)$
  • 对数时间：$\Theta(\log n)$
  • 线性时间：$\Theta(n)$
  • 线性对数时间：$\Theta(n \log n)$
  • 平方时间：$\Theta(n^2)$
  • 多项式时间：$\Theta(n^c)$
  • 指数时间：$2^{\Theta(n^c)}$

Model of Computation#

• 在 $O(1)$ 时间内可执行的基本操作
  • 整数运算和逻辑运算
  • 位运算
  • 内存地址读写
• Word-RAM 模型特定
  • 以地址为索引的数组结构
• 内存寻址要求
  • 字长 $w \geq \log_2 n$
  • 因为内存地址必须能访问内存中的任意位置

Data Structure#

• 定义：存储非常量数据并支持一组操作的方式
• 操作的集合称为接口(Interface)
  • 序列(Sequence)：基于外在顺序（第一个、最后一个等）
  • 集合(Set)：基于内在顺序（基于元素键的查询）
• 一个接口可以有多种实现
• 典型示例：静态数组
  • 初始化：$\Theta(n)$ 时间
  • 读取和写入：$\Theta(1)$ 时间

How to Solve an Algorithm Problem#

1. 规约到已知问题（使用现有数据结构或算法）
   • 搜索问题
   • 排序算法
   • 最短路径算法
2. 设计新的递归算法
   • 暴力解法
   • 分治策略
   • 动态规划
   • 贪心算法
   • 增量方法

Data Structure Interfaces#

• 数据结构是存储数据的方式，并提供支持数据操作的算法
• 接口(Interface)是对支持操作的集合(collection)，也称为API或ADT
• 接口是规范(specification)：说明支持什么操作（问题）
• 数据结构是表现(representation)：实现如何支持操作（解决方案）

Sequence Interface#

维护项目的外在顺序

Set Interface#

维护项目的内在顺序(基于键)

Array Sequence#

• 静态操作高效：get_at(i) 和 set_at(i, x) 是 $\Theta(1)$
• 动态操作低效，为 $\Theta(n)$
  • 需要重新分配空间和移动元素

Linked List Sequence#

• 头部动态操作高效：insert_first 和 delete_first 是 $\Theta(1)$
• 随机访问低效：get_at(i) 和 set_at(i, x) 是 $O(n)$

Dynamic Array Sequence#

• 综合了数组和链表的优点
• 关键思想：预分配额外空间
• 填充率($r$)：$0 \leq r \leq 1$
  • 当数组填满时，分配 $\Theta(n)$ 的额外空间到末尾使填充率降至给定的 $r_i$(如0.5)
  • 下次分配前需要插入 $\Theta(n)$ 个项目
• 平摊分析：单次操作可能是 $\Theta(n)$，但平均是 $\Theta(1)$
• Python列表就是动态数组的实现

Time Complexity Table#

$^*$: 平摊时间

Set Interface#

Sorting#

1. 排序问题定义

   • 输入：$n$ 个数字的静态数组 $A$
   • 输出：$A$ 的一个有序排列 $B$
   • 要求：
     • B是A的置换(permutation)（相同元素不同顺序）
     • B有序(sorted)：对所有 $i \in \{1,...,n\}$，有 $B[i-1] \leq B[i]$
   • 示例：[8, 2, 4, 9, 3] → [2, 3, 4, 8, 9]

2. 排序方法分类

   • 破坏性(destructive) 排序：直接覆盖原数组 $A$
   • 原地(in place) 排序：使用 $O(1)$ 额外空间（隐含是破坏性的）

Permutation Sort#

1. 算法思想

   • 尝试所有可能的排列（$n!$种）
   • 检查每个排列是否有序（$\Theta(n)$时间）

2. 实现示例

def permutation_sort(A):
    for B in permutations(A):    # O(n!)
        if is_sorted(B):         # O(n)
            return B             # O(1)

3. 分析
   • 正确性：通过穷举所有可能性（暴力解法）
   • 时间复杂度：$\Omega(n! \cdot n)$（指数级，效率很低）:(

Solving Recurrences#

1. 代入法(Substitution)：

   • 猜测一个解
   • 用代表函数替换
   • 验证递归式是否成立

2. 递归树法(Recurrence Tree)：

   • 绘制表示递归调用的树
   • 对节点的计算量求和

3. 主定理(Master Theorem)：

   • 用于解决多种递归式的公式

Selection Sort#

def selection_sort(A, i = None):      # T(i)
    '''Sort A[:i+1]'''
    if i is None: i = len(A) - 1      # O(1)
    if i > 0:                         # O(1)
        j = prefix_max(A, i)          # S(i)
        A[i], A[j] = A[j], A[i]       # O(1)
        selection_sort(A, i - 1)      # T(i-1)

def prefix_max(A, i):                 # S(i)
    '''Return index of maximum in A[:i+1]'''
    if i > 0:                         # O(1)
        j = prefix_max(A, i - 1)      # S(i-1)
        if A[i] < A[j]:               # O(1)
            return j                  # O(1)
    return i                          # O(1)

Insertion Sort#

def insertion_sort(A, i = None):      # T(i)
    '''Sort A[:i+1]'''
    if i is None: i = len(A) - 1      # O(1)
    if i > 0:                         # O(1)
        insertion_sort(A, i - 1)      # T(i-1)
        insert_last(A, i)             # S(i)

def insert_last(A, i):                # S(i)
    '''Sort A[:i+1] assuming sorted A[:i]'''
    if i > 0 and A[i] < A[i-1]:       # O(1)
        A[i], A[i-1] = A[i-1], A[i]   # O(1)
        insert_last(A, i-1)           # S(i-1)

Merge Sort#

def merge_sort(A, a=0, b=None):       # T(b-a=n)
    '''Sort A[a:b]'''
    if b is None: b = len(A)          # O(1)
    if 1 < b - a:                     # O(1)
        c = (a + b + 1) // 2          # O(1)
        merge_sort(A, a, c)           # T(n/2)
        merge_sort(A, c, b)           # T(n/2)
        L, R = A[a:c], A[c:b]         # O(n)
        merge(L, R, A, len(L), len(R), a, b)  # S(n)

def merge(L, R, A, i, j, a, b):       # S(b-a=n)
    '''Merge sorted L[:i] and R[:j] into A[a:b]'''
    if a < b:                         # O(1)
        if (j <= 0) or (i > 0 and L[i-1] > R[j-1]):  # O(1)
            A[b-1] = L[i-1]           # O(1)
            i = i - 1                 # O(1)
        else:
            A[b-1] = R[j-1]           # O(1)
            j = j - 1                 # O(1)
        merge(L, R, A, i, j, a, b-1)  # S(n-1)

Introduction#

• 思考：能否比 $\Theta(\log n)$ 更快地实现Set接口的 find(k)？
• 理论上不能（下界定理），但实际上…可以！？

Comparison Model#

1. 基本假设：

   • 算法只能通过比较来区分项目
   • 可比较的项目(Comparable items)是一种黑盒对象
     • 只支持成对比较
     • 无法直接访问项目的内部结构
   • 比较运算：$\lt, \leq, \gt, \geq, =, \neq$，返回True或False

2. 目标：

   • 存储 $n$ 个可比较项目
   • 支持 find(k) 操作
   • 运行时间下界由比较次数决定

Decision Tree#

• 任何算法都可以看作操作的决策树(decision tree)
• 内部节点表示二元比较(binary comparison)，分支为True或False
• 叶节点表示算法终止，得到输出结果
• 根到叶的路径(root-to-leaf path)代表算法在特定输入上的执行(execution)
• 每个搜索结果至少需要对应一个叶节点，除 $n$ 个元素外还需要一种未找到的结果，因此搜索需要$\geq n+1$个叶节点

Direct Access Array#

1. 想法

   • 利用Word-RAM的 $O(1)$ 时间随机访问
   • 为每个项目分配唯一整数键 $k$，范围为 $\{0,...,u-1\}$，存储在数组对应位置

2. 优点：

   • 如果键能放入机器字（$u \leq 2^w$），则最坏情况下find/动态操作都是 $O(1)$

3. 缺点：

   • 空间复杂度 $O(u)$，当 $n \ll u$ 时非常浪费
   • 示例：10字母名字作为键，每个名字1位，需要 $26^{10} \approx 17.6 \text{TB}$ 空间

Hashing#

• 当 $n \ll u$ 时，将键映射到更小的范围 $m = \Theta(n)$，使用更小的直接访问数组
• 哈希函数：$h(k): \{0,...,u-1\} \rightarrow \{0,...,m-1\}$
• 直接访问数组称为哈希表(hash table)，$h(k)$ 称为键 $k$ 的哈希值

冲突(Collision)：

• 当 $m \ll u$ 时，由抽屉原理，任何哈希函数都不是单射
• 必然存在键 $a, b$ 使得 $h(a) = h(b) \rightarrow$ 发生冲突！:(
• 解决方案：
  1. 存储在数组的其他位置（开放寻址，open addressing）
     • 分析复杂，但普遍实用
  2. 存储在支持动态集合接口的其他数据结构中（链接，chaining）

Chaining#

• 核心思想：将碰撞的元素存储在另一个数据结构（链）中

• 性能分析：

  • 理想情况：键均匀分布，链长度为 $n/m = n/\Omega(n) = O(1)$
  • 最佳情况：链长度为 $O(1)$ 时，所有操作为 $O(1)$ 时间
  • 最差情况：多个项目映射到同一位置，如 $h(k)=constant$，链长度为 $\Theta(n)$

• 需要一个好的哈希函数！什么是好的哈希函数？

Hash Functions#

Dynamic#

• 当 $n/m \gg 1$ 时，使用新的大小 $n$ 和新的随机选择的哈希函数重建表
• 分析类似动态数组，成本可以分摊到多个动态操作上
• 所以哈希表可以在期望平摊的 $O(1)$ 时间完成动态集合操作！:)

Complexity Table#

$^*$: 平摊时间
$^\dagger$: 期望时间

Review#

• 比较搜索的下界：任何有 $n$ 个节点的决策树的高度 $\geq \lceil \log(n+1) \rceil - 1$
• 使用随机访问索引(random access indexing)可以更快：具有线性分支因子（出度）的操作！
• 直接访问数组速度快，但可能使用大量空间 $\Theta(u)$
• 通过将键空间 $u$ 映射(哈希)到 $m = \Theta(n)$ 来解决空间问题
• 哈希表提供期望 $O(1)$ 时间操作，如果是动态操作则是期望均摊时间
• 期望与输入无关：从通用哈希族中随机选择哈希函数

Complexity Table

Comparison Sort Lower Bound#

• 比较模型意味着算法决策树是二进制的(常数分支因子)
• 要求叶子数 $L \geq$ 可能输出数
• 树高度下界为 $\Omega(\log L)$，所以最坏情况运行时间是 $\Omega(\log L)$
• 对于 $n$ 个元素的数组排序，输出总数是 $n!$ 种排列
• $\log(n!) = \Theta(n \log n)$ (证明)
• 所以归并排序在比较模型中是最优的

Direct Access Array Sort#

• 假设所有键都是唯一的非负整数，范围在 $\{0,...,u-1\}$ 中，故 $n \leq u$
• 将每个项插入大小为 $u$ 的直接访问数组，时间 $\Theta(n)$
• 按照它们在直接访问数组中出现的顺序返回项，时间 $\Theta(u)$
• 如果 $u = \Theta(n)$，运行时间为 $\Theta(n)$ :)

def direct_access_sort(A):
	"对具有非负互异键的项进行排序"
	u = 1 + max([x.key for x in A])       # O(n) 找到最大键
	D = [None] * u                        # O(u) 直接访问数组
	for x in A:                           # O(n) 插入项
		D[x.key] = x
	i = 0
	for key in range(u):                  # O(u) 按顺序读出项
		if D[key] is not None:
			A[i] = D[key]
			i += 1

• 当键在更大范围时（如 $u = \Omega(n^2) < n^2$）
• 思路：将每个键 $k$ 表示为元组 $(a,b)$，其中 $k = an + b$ 且 $0 \leq b < n$
• 这实际上是一个以 $n$ 为基数的2位数
• 例如：$[17,3,24,22,12] \Rightarrow [(3,2),(0,3),(4,4),(4,2),(2,2)] \Rightarrow [32,03,44,42,22]_{(n=5)}$

Tuple Sort#

• 项的键是相等长度的元组，即 $\text{item } x.key = (x.k_1, x.k_2, x.k_3, ...)$

• 要按字典序(lexicographically)对所有条目进行排序，第一个键 $k_1$ 最重要

• 排序思路：使用其他辅助排序算法分别对每个键进行排序

• 类似于在电子表格中按多个列排序

• 排序顺序：从最不重要到最重要的键进行排序

• 例如：$[32,03,44,42,22] \Rightarrow [42,22,32,03,44] \Rightarrow [03,22,32,42,44]_{(n=5)}$

• 想法：使用带辅助直接访问数组排序来对元组 $(a,b)$ 排序

• 问题：即使输入键是唯一的，许多整数可能具有相同的 $a$ 或 $b$ 值

• 需要能够处理重复键并保持输入顺序的排序

• 要求排序是稳定的(stable)：重复键在输出中的顺序与输入相同

• 直接访问数组排序甚至无法对具有重复键的数组进行排序

Counting Sort#

• 不是在每个数组索引存储单个项，而是存储一个链，类似哈希！
• 为了稳定性，链数据结构应该记住项被添加的顺序
• 使用维护插入顺序的**序列(sequence)**数据结构
• 插入项 $x$ 时，用 insert_last 将其插入到索引 $x.key$ 处的链末尾
• 排序时，按序列顺序读取所有链，逐个返回项

def counting_sort(A):
    "对具有非负键的项进行排序"
    u = 1 + max([x.key for x in A])      # O(n) 找到最大键
    D = [[] for i in range(u)]           # O(u) 直接访问链数组
    for x in A:                          # O(n) 插入到x.key的链中
        D[x.key].append(x)
    i = 0
    for chain in D:                      # O(u) 按顺序读出项
        for x in chain:
            A[i] = x
            i += 1

Radix Sort#

• 当 $u < n^2$ 时，使用带辅助计数排序的元组排序来对元组 $(a,b)$ 进行排序

• 先对最低有效位 $b$ 排序，然后对最高有效位 $a$ 排序

• 稳定性确保之前的排序结果保持有序

• 运行时间为 $O(2n) = O(n)$ :)

• 如果每个键 $< n^c$（$c = \log_n u$ 为某个正数），则每个键最多有 $c$ 个以 $n$ 为基数的数位

• 一个 $c$ 位数可以在 $O(c)$ 时间内写成 $c$ 元组

• 我们在 $O(n)$ 时间内对每个以 $n$ 为基的 $c$ 个数位进行排序

• 带辅助计数排序的元组排序总共运行时间为 $O(cn)$

• 如果 $c$ 是常数，即每个键 $\leq n^c$，则这种排序是线性的 $O(n)$

def radix_sort(A):
    "对具有非负键的项进行排序"
    n = len(A)
    u = 1 + max([x.key for x in A])         # O(n) 找到最大键
    c = 1 + (u.bit_length() // n.bit_length())
	
    class Obj: pass
    D = [Obj() for a in A]
    for i in range(n):                      # O(nc) 创建数字元组
	    D[i].digits = []
        D[i].item = A[i]
        high = A[i].key
        for j in range(c):                  # O(c) 创建数字元组
            high, low = divmod(high, n)
            D[i].digits.append(low)
	
    for i in range(c):                      # O(nc) 排序每个数位
        for j in range(n):                  # O(n) 对数位i进行排序
	        D[j].key = D[j].digits[i]
	    counting_sort(D)
	for i in range(n):
		A[i] = D[i].item

Sorting Algorithms Comparison#

注：$k$-近似序列（$k$-proximate sequence）是指数组中的每个元素与其最终排序位置的距离不超过 $k$ 个位置的序列。换句话说，每个元素最多需要移动 $k$ 个位置就能到达它在排序后的正确位置。

Binary Trees#

我们想实现序列(Sequence)/集合(Set)接口并且所有的静态、动态和查找操作的时间复杂度为 $O(\log n)$

• 二叉树是一种基于指针的数据结构，每个节点包含三个指针
• 每个节点包含四个基本属性：
  • item: 存储的数据
  • parent: 父节点指针
  • left: 左子节点指针
  • right: 右子节点指针
• node.{item, parent, left, right}
• 示例：

       ________<A>_____
    __<B>_____       <C>
 __<D>      <E>
<F>

1. root(根节点): 没有父节点的节点
2. leaf(叶节点): 没有子节点的节点
3. depth(深度): 从该节点到根节点的路径长度
4. height(高度): 从该节点到其最深叶节点的路径长度，或该节点子树中所有节点的最大深度

Idea：设计操作以在根高度 $h$ 的情况下以 $O(h)$ 的时间运行，并保持 $h = O(\log n)$

Traversal Order#

• 二叉树具有固有的遍历顺序：
  • 左子树中的所有节点在当前节点之前
  • 右子树中的所有节点在当前节点之后
• 遍历算法：
  1. 递归遍历左子树
  2. 访问当前节点
  3. 递归遍历右子树
• 时间复杂度：$O(n)$，因为每个节点只访问一次
• 示例：(<F>, <D>, <B>, <E>, <A>, <C>)
• 目前，遍历顺序相对于存储的项目而言没有意义
• 随后，将为遍历顺序赋予语义意义，以实现序列/集合接口

Tree Navigation#

Dynamic Operations#

更改树的单个项目（仅添加或删除叶子节点），其余部分遍历顺序不变：

• 在遍历顺序中在另一个节点之后添加一个节点（之前是对称的）
• 从树中删除一个项目

       ______<A>___               ________<A>___
    __<B>___     <C>    =>     __<B>_____     <C>
 __<D>    <E>               __<D>    __<E>
<F>                        <F>      <G>

       ______<A>___                ________<A>_____
    __<B>_____   <C>     =>     __<B>_____     __<C>
 __<D>    __<E>              __<D>    __<E>   <H>
<F>      <G>                <F>      <G>

       ________<A>_____             ________<A>_____
    __<B>_____     __<C>    =>   __<B>_____     __<C>
 __<D>    __<E>   <H>           <D>    __<E>   <H>
<F>      <G>                          <G>

     ________<A>_____           ________<E>_____           _____<E>_____
  __<B>_____     __<C>   =>  __<B>_____     __<C>   =>  __<B>__     __<C>
<D>     __<E>   <H>         <D>    __<G>   <H>         <D>   <G>   <H>
       <G>                        <A>

Application: Set#

• Idea! Set Binary Tree (a.k.a. Binary Search Tree / BST):

  • 遍历顺序就是键值的升序排列
  • BST性质：对每个节点，其左子树的所有键值 $\leq$ 节点键值 $\leq$ 右子树的所有键值

• 在 $O(h)$ 时间内查找具有特定键值的节点：

  1. 如果目标值小于当前节点，在左子树中递归（或返回 None）
  2. 如果目标值大于当前节点，在右子树中递归（或返回 None）
  3. 相等则返回当前节点

• 其他集合操作略

Application: Sequence#

• Idea! Sequence Binary Tree: 遍历顺序表示序列顺序
• 如何访问一个子树的遍历顺序中的第 $i$ 个节点，称为 subtree_at(i)
• 迭代整个遍历顺序可以实现，但是为 $O(n)$
• 但是，如果我们可以计算子树的大小在 $O(1)$ 时间，就可以在 $O(h)$ 时间实现
  1. 比较左子树大小 $n_L$ 与 $i$
  2. 如果 $i < n_L$，在左子树中递归
  3. 如果 $i > n_L$，在右子树中递归并调整索引 $i' = i - n_L - 1$
  4. 如果 $i = n_L$，返回当前节点
• 每个节点额外维护子树大小
  • 每个节点 node 添加 node.size 字段
  • 插入叶节点时：所有祖先节点 a 的 a.size 加1
  • 删除叶节点时：所有祖先节点 a 的 a.size 减1
  • 维护成本：$O(h)$
• 序列操作直接源自快速的 subtree_at(i) 操作
• 初步看来，build(X)需要 $O(nh)$ 的时间，但实际上可以在 $O(n)$ 的时间内完成
  • 将数组的中间元素作为根节点，递归构建左右子树

So Far#

Set Data Structure：

Sequence Data Structure：

Goal#

Set Data Structure：

Sequence Data Structure：

Height Balance#

• 能在动态操作下维持 $O(\log n)$ 高度的二叉树被称为平衡树

  • 有多种平衡方案(红黑树、伸展树、2-3树等)
  • AVL树是第一个被提出的平衡方案(Adelson-Velsky和Landis, 1962年)

• AVL树通过维持高度平衡来确保 $O(\log n)$ 的性能

Rotations#

• 需要在不改变遍历顺序的情况下减少树的高度，以保持相同的元素序列
• 通过旋转在保持遍历顺序的同时改变树的结构

     _____<D>__      rotate_right(<D>)      __<B>_____
  __<B>__    <E>            =>             <A>    __<D>__
 <A>   <C>   / \                           / \   <C>   <E>
 / \   / \  /___\           <=            /___\  / \   / \
/___\ /___\          rotate_left(<B>)           /___\ /___\

• 旋转操作重新连接$O(1)$个指针来修改树结构，同时保持遍历顺序

Rotations Suffice#

• 结论：$O(n)$ 次旋转可以将一个二叉树转换为具有相同遍历顺序的任意其他二叉树
• 证明：按遍历顺序，重复执行最后一个可能的右旋转，最终得到一个规范链。每次旋转使最后一个节点的深度增加1。最终链中最后一个节点的深度是 $n-1$，所以最多执行 $n-1$ 次旋转。反向执行规范旋转即可到达目标树
• 在这里，规范链(canonical chain)是一种特殊的二叉树形态。所有节点都只有右子节点（或都只有左子节点），形成一个类似于链表的结构，每个节点都只连接到一侧
• 可以通过使用 $O(n)$ 次旋转来完全地平衡树，但这样太慢了 :(
• 我们将在每个操作中都用 $O(\log n)$ 的时间保持树的平衡

AVL Trees: Height Balance#

1. AVL树维持高度平衡(height-balance)（也称为AVL Property）

   • 如果一个节点的左右子树高度差最多为1，则称该节点是高度平衡的
   • 定义节点的偏斜度(skew)为其右子树高度减去左子树高度
   • 当节点的偏斜度为-1、0或1时，该节点是高度平衡的

2. 结论：具有高度平衡节点的二叉树高度 $h = O(\log n)$（即 $n = 2^{\Omega(h)}$）

• 证明：只需证明任何高度为 $h$ 的树中最少节点数 $F(h)$ 满足 $F(h) = 2^{\Omega(h)}$（斐波那契树）

  $F(0) = 1, F(1) = 2, F(h) = 1 + F(h-1) + F(h-2) \geq 2F(h-2) \Longrightarrow F(h) \geq 2^{h/2}$

3. 假设在高度平衡树中添加或删除叶子节点导致不平衡：
   • 只有受影响叶子节点的祖先的子树在高度或偏斜度上发生改变
   • 高度的变化只有 $\pm 1$，所以偏斜度的绝对值最大为2
   • 处理方法：从叶子节点开始向上到根节点，修复祖先的高度平衡
   • 重复平衡最低的未平衡祖先节点，由对称性假设偏斜度为2

  __<B>______                     ______<F>____
 <A>    ___<F>___              __<B>___      <G>
 / \   <D>     <G>     =>     <A>    <D>     / \
/___\  / \     / \            / \    / \    /   \
      /___\   /   \          /___\  /___\  /_____\
     /_____\ /_____\               /_____\

  __<B>___________                   _____<D>______
 <A>       _____<F>__             __<B>__      __<F>__
 / \    __<D>__    <G>    =>     <A>   <C>    <E>   <G>
/___\  <C>   <E>   / \           / \   /_\    /_\   / \
       /_\   /_\  /___\         /___\ /___\  /___\ /___\
      /___\ /___\

Computing Height#

• 如何判断节点 <X> 是否高度平衡？需要计算子树的高度！

• 如何计算节点 <X> 的高度？朴素算法：

  • 递归计算 <X> 的左右子树的高度
  • 取两个高度的最大值加1
  • 运行时间为 $\Omega(n)$，因为需要递归访问每个节点 :(

• Idea：用子树高度来增强每个节点

• 可以通过 <X> 的子节点在 $O(1)$ 时间内计算 <X> 的高度：

  • 在 $O(1)$ 时间内查找左右子树的存储高度
  • 取两个高度的最大值加1

Application: Sequence#

• 对于序列二叉树，我们需要知道子树大小，原因
• 仅仅插入/删除叶子节点时这很容易，但现在需要处理旋转
• 子树大小是一个子树属性，所以可以通过增强来维护
  • 可以通过把子节点的大小相加再加1来计算大小

Application: Sorting#

• 任何支持顺序访问集合数据结构都定义了一个排序算法：build（或重复 insert）然后 iter
• 例如，lec 5中的直接访问数组排序
• AVL排序是一个新的 $O(n \log n)$ 时间排序算法

Conclusion#

• 集合AVL树实现所有集合操作的 $O(\log n)$ 时间复杂度
  • 除了 build 需要 $O(n \log n)$ 时间
  • iter 需要 $O(n)$ 时间
• 序列AVL树实现所有序列操作的 $O(\log n)$ 时间复杂度
  • 除了 build 和 iter 需要 $O(n)$ 时间

Priority Queue Interface#

• 主要功能是跟踪多个项目，快速访问/删除最重要的项目
• 根据 key = priority 排序项目，所以是集合接口
• 针对集合操作的特定子集优化
  • build(X): 从可迭代对象 X 构建优先队列
  • insert(x): 添加项目 $x$ 到数据结构
  • delete_max(): 移除并返回最大键值的项目
  • find_max(): 返回最大键值的项目
• 通常针对 $max$ 或 $min$ 优化，而不是同时优化两者
• 我们关注 insert 和 delete_max 操作
  • build 等价于重复 insert
  • find_max 等价于 insert(delete_max())

Priority Queue Sort#

• 可以将任何优先队列数据结构转换为排序算法
  1. build(A) - 按输入顺序 insert 项目
  2. 重复 delete_min() 或 delete_max() 确定排序顺序
• 运行时间：$T_{build} + n \cdot T_{delete\_max} \leq n \cdot T_{insert} + n \cdot T_{delete\_max}$
• 部分先前提到的的排序算法可以看作是优先队列排序

$^*$: 平摊时间

Array as a Complete Binary Tree#

• Idea：将数组解释为完全二叉树，本质还是数组
  • 完全二叉树：
  1. 每一层 $i$ 最多有 $2^i$ 个节点（除最后一层外）
  2. 最后一层的节点都靠左对齐(left-aligned)
  3. 按照从上到下、从左到右的阅读顺序填充

d0          ______O____
d1      ____O____   __O__
d2    __O__   __O   O   O
d3    O   O   O

• 数组和完全二叉树之间存在一一对应(bijection)的关系

Q = [0,1,2,3,4,5,6,7,8,9]
d0   0                      ->          ______0____
d1     1 2                  ->      ____1____   __2__
d2         3 4 5 6          ->    __3__   __4   5   6
d3                 7 8 9    ->    7   8   9

• 从完全二叉树的视角来看，包含 $n$ 个元素的数组的高度为 $\lfloor \log_2 n \rfloor$，因此它是一个平衡二叉树

Binary Heaps#

• Idea：在树中保持较大元素在上方，但只需要局部维护这个性质
• 最大堆性质(Max-Heap Property)：对于节点 $i$，$Q[i] \geq Q[j]$，其中 $j \in \{ \text{left}(i), \text{right}(i) \}$
• 最大堆(Max-Heap)定义：满足所有节点都具有最大堆性质的数组
• 性质：在最大堆中，对每个节点 $i$ 和 subtree(i) 的任意节点 $j$，都有 $Q[i] \geq Q[j]$
• 特别地，最大值总是位于最大堆的根节点