12. 二叉搜索树

二叉搜索树支持许多动态集合的操作，包括Search，Insert，Delete，Minimum，Maximum，Successor，Predecessor。所有操作的时间复杂度为$\Omicron(h)$，h为树的高度。

二叉搜索树

二叉搜索树是一个链式存储的二叉树，且具有如下特性：
设x为二叉搜索树中的一个结点。

• 如果y是x左子树中的一个结点，那么y.key<=x.key。
• 如果y是x右子树中的一个结点，那么y.key>=x.key。

Search

从根节点开始查找，如果查询的k小于根节点的key，则递归查找左子树；如果查询的k大于根节点的key，则递归查找右子树；如果查询的k等于根节点的key，done。

Minimum

从根节点开始沿着left child方向一直找到低。

Maximum

从根节点开始沿着right child方向一直找到低。

Successor & Predecessor

查询x的下一个节点：

• 如果x有右孩子，那么x的下一个节点就是右子树的最小值。

  1 2 3 4 5 6 7

  ○ / \ ● / \ ○ / \ [○]

• 若果x没有右孩子，那么x的下一个节点是x的第n个parent，这个parent是第一个符合下图的情况，第n-1个parent 是第n个parent得 left child。

  1 2 3 4 5 6

  [○] / \ ○ / \ ● /

• 如果没有符合这样情况的parent，那么说明x是最大数，没有下一个节点。

Insert

上图描述了插入key为13的数据。
从根节点x开始查找。如果待插入数据小于该节点数据，到左子树继续查找，否则到右子树查找，直到找到一个空位置，将数据放入。

Delete

删除操作的情况较为复杂，有如下几种情况

1. 待删除节点没有孩子
2. 待删除节点只有一个孩子，如下图(a) (b)情况
3. 待删除节点有两个孩子，并且右孩子没有左孩子时，如下图©情况
4. 待删除节点有两个孩子，并且右孩子有左孩子时，如下图(d)情况

1. 当待删除节点没有孩子时：
   • 可以直接删除该节点，并且修改他的父节点，用nil代替他
2. 当待删除节点只有一个孩子时，如图中 (a) (b) 情况：
   • 可以直接用子节点替换该节点
3. 当待删除节点有两个孩子时，如图中 © (d) 情况：
   • 思路：用待删除节点z的Successor节点y替代它的位置
   • 情况c，右孩子没有左孩子（y是z的子节点）
     • y替换z，并且接管z的左孩子
   • 情况d，右孩子有左孩子
     • y的右孩子x替换y，并且y接管z的右孩子
     • y替换z，并且接管z的左孩子

Tips：当待删除节点有两个孩子时，用待删除节点的Predecessor节点替代它也可以。

涉及数据结构

点击查看实现

• 二叉搜索树

留言與分享

11. 散列表（哈希表）

许多应用都需要一种动态集合，至少支持Insert，Search和Delete的字典操作。
散列表（Hash Table）是实现字典操作的一种有效数据结构。尽管最坏情况下散列表查询一个元素的时间和链表的查询时间相同，为Θ(n)。但是在实际应用中，散列表的查询性能是极好的。在一些合理的假设下，散列表中扎寻一个元素的平均时间能为Ο(1)。

假设某应用需要用到一个动态集合，其中每个元素的KEY都是取自全域U={0, 1, …, m-1}。本章讨论方法都是基于这样的动态集合。

直接寻址表

当KEY的全域U较小时，直接寻址表是一种简单而有效的技术。
为了表示这个动态集合，我们用一个数组作为直接寻址表，记为T[0…m-1]，其中数组的每个位置称为槽，与全域U中的KEY一一对应。
K集合表示实际存在的元素的KEY集合。
槽k指向KEY为k的元素，如果K集合中没有k，那么T[k] = nil。

散列表

直接寻址表的缺点很明显：

1. 如果全域U非常大，则计算机无法存储
2. 如果K集合相对于全域U非常小，那么将非常浪费空间

如果直接寻址表占用的存储空间为$\Theta(|U|)$，那么散列表能将存储需求降至$\Theta(|K|)$，同时散列表中查找一个元素的时间为$\Omicron(1)$，不过是平均时间。

散列方式不同于直接寻址表的地方是，元素存储在散列表中的位置由散列函数决定，即k元素存储在散列表的h(k)位置。h(k)叫做k的散列值。

散列表T的大小比|U|小很多，所以肯定会有冲突的情况。

冲突最简单的解决方式是使用链接法，后面还介绍一种开放寻址法。
下图是链接法的图示，当有两个k值映射到了同一个散列值时，将它们保存在一个链表内。

链接法散列分析

如果要将n个数据存储在m大小的散列表中，我们称α = n/m为装载因子，即散列表的每个槽平均存放的数据。
假设散列函数能等可能的把数据散列到m个槽中，我们称这个假设为简单均匀散列。
这时每个槽存放元素个数的期望值为α。

所以，一次不成功查找的平均时间为$\Theta(1+\alpha)$。（1 表示散列函数消耗的时间）

1

因为每个槽的期望为α，而不成功的情况下，查找的期望时间就是从槽链表的头遍历到链表尾，所以期望时间就是槽链表的长度α。

一次成功查找的平均时间为$\Theta(1+\alpha)$。

1
2

具体证明参考公开课中老师的推理，或者书中推理。
自我理解：一个元素在槽中的位置是等概率随机的(1/α)，而且期望时间为元素在槽中位置的期望。期望位置为(1+2+..+α)*(1/α) = (α+1)/2

散列函数

最好的散列函数便是能达到简单均匀散列。
下面介绍一些的散列函数。其中全域散列能够达到这样的要求。

除法散列

1

h(k) = k mod m

m最好是一个素数，并且不能太接近2或者10的乘方。

乘法散列

1

h(k) = [(a * k) mod 2^w] >> (w − r)

k是w bits的数
m = 2^r
a最好是一个奇数，并且不能太接近2或者10的乘方。

全域散列

随机的选择散列函数，称为全域散列
Example：

1
2

h(k) = [(ak+b) mod p] mod m 
where a and b are random ∈ {0, 1, . . . p−1}, and p is a large prime (> |U|).

证明全域散列为简单均匀散列的过程，参考公开课中老师的推理，或者书中推理。

开放寻址法

• 无链表，所有的元素都保存在table中
• 每个槽存储一个元素，m>=n
• 散列函数为h(k, i)，i从0开始，当有冲突后i++，直到找到一个空的位置，所以散列函数需要有如下性质：

1
2
3
4
5

对同一个KEY做m次探查，能把散列表填满

h : U × {0, 1,...,m − 1} → {0, 1,...,m − 1}

{h(k, 0), h(k, 1), . . . , h(k, m − 1)} == {0, 1,...,m − 1}

删除时，不能直接删除！删除后需要标记此位为删除位。

线性探查

1

h(k, i) = (h1(k) +i) mod m

双重探查

1
2
3
4

h(k, i) =(h1(k) + i·h2(k)) mod m

h2(k) 需要和 m 互为质数
e.g. m = 2^r, h2(k) 永远为奇数

开放寻址法分析

给定一个装载因子α = n/m < 1的开放寻址散列表，并假设是均匀散列的：
对于一次不成功的查找，期望的探查次数至多为1/(1-α)
对于一次成功的查找，期望的探查次数至多为\frac{1}{α}\ln(1/(1-α))

完全散列

基于全域散列，完全没看。。。

涉及数据结构

点击查看实现

• 使用链接法的散列表

留言與分享

10. 基本数据结构

动态集合的基本数据结构。

栈

栈，后进先出，用数组存储，并用top保存栈顶位置。支持压入（Push）和弹出（Pop）操作。
a->b产生了两次Push操作，压入了17和3。
b->c产生了一次Pop操作，弹出了3。

队列

队列，先进先出，用数组存储，用head和tail保存队列的头和尾的位置。支持入队（Enqueue）和出队（Dequeue）操作。
a->b产生了三次Enqueue操作，加入了17 3 5。
b->c产生了一次Dequeue操作，去除了15。
当head或者tail超出数组范围时，转移到数组头部。
当tail等于head时，表示队列已满，不能再加入数据。

链表

链表是一种对象按照线性排序的数据结构，不同于数组的是链表的顺序由各个对象里的指针表示。
下图表示一个双向链表。每个对象包含prev指针，next指针，key值，或者附加一些卫星数据。
prev指针指向上一个对象
next指针指向下一个对象
用一个head指针指向头结点，头结点的prev指针为null
尾结点的next指针为null

单向链表为双向链表去除prev指针。

下图是一个带有哨兵的双向循环链表，说实话没看出这个哨兵的必要性。

数组存储链表

不是所有的语言都支持指针，所以只能间接实现链表。
下图给出一种用多个数组存储链表的方式，next数组和prev数组中存储next元素或prev元素的数组下标，从而间接的实现了双向链表。

为了更方便快捷的在分配和释放数组中的元素，在数组中存储一个free单向连边。
当需要分配元素时，分配free链表的头结点，并使free指向下一元素。
当需要释放元素时，使该元素的next指向free指向的元素，并使得free指向该元素。

二叉树

前面我们讨论过一种特殊二叉树——堆的存储，我们将堆存储在数组中。
但对于一般的二叉树，我们将用链式数据结构表示。

每个元素包含三个指针——p、left、right分别指向父节点、左孩子、右孩子。
根节点的p指向null，叶子节点的left和right指向null。

当我们需要存储一个N叉树时，按照上面的方法，每个元素则需要child1、child2…childN来存储，会占用很多额外空间，如果孩子个数是未知的这种方式则无法实现。
下图展示了一种分支无限制的有限树的存储方式——左孩子右兄弟表示法。left指向第一个孩子，right指向兄弟节点。

涉及数据结构

点击查看实现

• 双向链表

留言與分享

9. 中位数和顺序统计量

顺序统计量，第i个顺序统计量指n个元素集合中第i小的元素。
最小值，第1个顺序统计量。
最大值，第n个顺序统计量。
中位数，第n/2个顺序统计量。（若n为偶数，取n/2-1）

我们可以通过一次遍历数组，取得最大值或者最小值。
但是若要取得中位数或者其他顺序统计量，则没办法通过一次遍历数组得到。
如果将数组排序，将可以直接得到中位数或者任意顺序统计量。由之前所学的排序算法可知，时间复杂度最好为$\Theta(n\lg n)$
本章讨论如何在线性时间找到中位数或者其他顺序统计量。

期望为线性时间的选择算法

利用随机快速排序的思想，随机的挑选一个元素作为主元，并把数组分为两侧，一侧比主元小，一侧比主元大，如果主元的位置q就是想找的顺序统计量的位置i，则返回主元，否则继续递归的查找左侧数组或者右侧数组。伪代码如下：

最坏情况为线性时间的选择算法

这个算法由几个大牛共同完成，发布在论文Time bounds for selection中。

中文描述如下：
https://www.jianshu.com/p/1c021beb5e72

涉及算法

点击查看实现

• 随机选择算法（RANDOMIZED_SELECT）

习题答案

练习

9.3-6

1
2
3

1. 如果k为1时，返回空数组
2. 如果k为偶数，找到数组的中位数,并把数组分为两组（比中位数大的一组，比中位数小的一组），递归解决这两个子问题，并把中位数以及两个字问题的解合并返回
3. 如果k为奇数，找到数组中间的两个分位数left和right，并把数组分出两组（比left小的一组，比right大的一组），递归解决这两个子问题，并把left right以及两个字问题的解合并返回

9.3-7

1
2
3
4

1. 线性时间找到中位数
2. 线性时间算出每个元素和中位数的距离（|x-middle|）
3. 线性时间找到第k小的距离
4. 线性时间找出比k小的距离对应的元素

9.3-8

1
2
3

1. 选择X Y两数组的中位数作为主元Xk和Yk
2. 比较Xk和Yk，如果Xk大于Yk，则取Xk左侧的元素作为新的X数组（包括X），取Yk右侧的元素作为新的Y数组（包括Y）
3. 重复1 2 两部，直到每个数组只剩两个元素，剩下的四个元素中第二小的便是两数组的中位数

留言與分享

8. 线性时间排序

前边介绍了很多排序算法，他们有一个共同点：元素的排序依赖于对他们之间的比较，这类排序我们称其为比较排序。本章节讨论比较排序的下界以及一些线性时间的排序方法。

比较排序的下界

将比较排序抽象为一颗决策树。
下图为三个元素排序的一颗决策树，叶子节点表示比较结果，其他节点表示某两个元素$(a,b)$作比较，节点的左子节点表示$a<=b$，节点的右子节点表示$a>b$。可以发现叶子节点包含了三个元素比较的所有可能情况，而且从根节点到叶子节点用了最少的比较次数。

接下来我们考虑n个元素排序的情况，因为n个元素排序可能会有n!种情况，所以叶子节点树小于等于n!，而这个树高度表示需要最坏情况的比较次数。

$h >= \lg(n!) = \Omega(n\lg n)$

所以在最坏情况下，任何比较排序算法都需要做$\Omega(n\lg n)$次比较。

计数排序

假设n个元素都是0~k之间的整数，而且$k=\Omicron(n)$时，计数排序的运行时间为$\Theta(n)$。

计数排序的基本思想为，首先得到0~k每一个值对应多少个元素，然后推算出每一个值对应元素在输出数组上的位置范围，最后将各个元素放到应该的位置。
计数排序的伪代码和处理过程如下图所示：

基数排序

基数排序的思想为，将带排序的数看做d位数，每一位的取值有K个可能，然后把待排数组从最低位开始做稳定排序（当有相同的数值时，排序后他们的顺序不变），一位接着一位直到最高位。伪代码，以及一个三位十进制数的排序过程如下：

如果基数排序使用的稳定排序方法耗时为$\Theta(n+k)$，每个数为d位，那么基数排序的时间复杂度为$\Theta(d(n+k))$

桶排序

TODO:

涉及算法

点击查看实现

• 计数排序

留言與分享

7. 快速排序

快速排序是一种最坏情况时间复杂度为$\Theta(n^2)$的排序算法，虽然最坏情况的时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，它的期望时间复杂度是$\Theta(n\lg n)$，而且$\Theta(n\lg n)$中隐含的常数因子非常小。另外它是原址排序。

快速排序

快速排序也用了分治的思想。对子数组A[p…r]进行快速排序的过程如下：
分解 将A[p…r]划分为两个数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]的每一个元素小于等于A[q]，而A[q+1…r]的每一个元素大于等于A[q]。
解决 递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序。
合并 因为是原址操作，所以无需合并，这时A[p…r]已经有序。

伪代码和分解过程如下：

性能

最坏情况

若每次分解时，都分解为一个空数组和一个n-1大小的数组,则为最坏情况。
递归式为$T(n) = T(n-1) + T(0) + \Theta(n)$
$T(n)$的解为$\Theta(n^2)$

最好情况

若每次分解时，都分解为两个一样大的子问题，这时为最好情况。
递归式为$T(n) = 2 T(n/2) + \Theta(n)$
$T(n)$的解为$\Theta(n\lg n)$

平衡的划分

若每次分解时，都按照一定比例分割，比如按照9:1划分。
递归式为$T(n) = T(9n/10) + T(n/10) + \Theta(n)$
$T(n)$的解为$\Theta(n\lg n)$

可用代入法证明按照任何比例划分，$T(n)$的解都为$\Theta(n\lg n)$

平均情况

若每次分解时，最好情况和最坏情况交替出现。
$T(n)$的解为$\Theta(n\lg n)$

可以将最好情况和最坏情况合并，时间复杂度并没变

随机快速排序

随机快速排序可以避免特定输入（已排序的队列或逆序列）时运行时间较长的情况。
分解时，随机的挑选数组中的一个元素来分解。

TODO: 证明随机快速排序的期望运行时间

涉及算法

点击查看实现

• 快速排序
• 随机快速排序

留言與分享

6. 堆排序

堆排序也是一种时间复杂度为$\Omicron (n\lg n)$的排序算法，但是与归并排序不同的是堆排序是一种原址排序，也就是说排序过程只是交换数据的位置。

最大堆

堆是一个数组，存储一个近似完全二叉树，树上的每个结点对应数组中的一个元素，数组第一个元素存储根节点，第i个元素的左孩子在数组的2i位置，右孩子在数组的2i+1位置，父结点在数组的i/2位置。

最大堆指一种父节点必然大于等于子节点的堆。下图为一个最大堆的存储情况：

MAX-HEAPIFY（维护最大堆）

MAX-HEAPIFY是维护最大堆性质的重要方法。MAX-HEAPIFY的输入为数组A和下标i，当调用MAX-HEAPIFY时，假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但是A[i]可能比它的子节点要小。MAX-HEAPIFY通过让A[i]的值在最大堆中逐级下降，从而使得以下标i为根节点的树符合最大堆的性质。以下是MAX-HEAPIFY的伪代码以及MAX-HEAPIFY(A, 2)的处理过程：

因为堆的高度为$\lg n$，所以该过程的时间复杂度是$\Omicron (\lg n)$.

建堆

自下而上的调用MAX-HEAPIFY可以把一个数组转换为最大堆。
叶子节点不需要调用，所以从下标为n/2的的元素开始，一直到根节点。
伪代码和建堆过程如下：

堆排序

1. 利用BUILD-MAX-HEAP方法构建最大堆
2. 接着循环的堆的根节点和最后一个元素交换
3. 堆的大小减一
4. 调用MAX-HEAPIFY(A, 1)
5. 循环2-4步，直到堆中只剩根节点

伪代码，以及2-5步过程如下：

优先队列

堆除了堆排序还有很多应用，比如优先队列。优先队列也有两种最大优先队列和最小优先队列。
一个最大优先队列支持以下操作：

1
2
3
4

INSERT(S, x)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S, x, k)

最大优先队列的应用有很多，其中一个是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业及他们之间的相对优先级。
最小优先队列可以被用于基于事件驱动的模拟器。队列中保存要模拟的事件，每个事件都有一个发生时间作为其关键字。

涉及算法

点击查看实现

• 堆排序

习题答案

思考题

• 6-43 Young氏矩阵

留言與分享

5. 概率分析和随机算法

当算法的时间和输入的数据有关时，往往我们需要使用概率分析得到算法运行时间的期望值（平均值）。
雇用问题这种答案不唯一的问题，也需要概率分析来分析算法的期望值，从而评估算法的有效性。

随机算法也有很广的应用，比如随机快速排序可以避免特定输入（已排序的队列或逆序列）时运行时间较长的情况。

留言與分享

4. 分治策略

本着涉及更多的分治法相关的算法，以及分治法运行时间的分析方法。

递归式

递归式可以很自然的刻画分支算法的运行时间。
递归式通过更小的输入上的函数值来藐视一个函数。
下图为归并排序的递归式：

$T(n)=\left\{ \begin{aligned} & \Theta(1) & if \quad n=1, \\ & 2T(n/2) + \Theta(n) & if \quad n>1, \end{aligned} \right.$

求解递归式的方法

• 代入法
  猜测一个界，然后用数学归纳法证明这个界的正确性
• 递归树法
  将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法 可求解形式如 $T(n) = aT(n/b) + f(n)$的递归式的界

涉及算法

点击查看实现

• 最大子数组
• 矩阵乘法

练习

4.1-1

1

返回最大的一个数组成的数组

4.1-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

FIND-MAXIMUM-SUBARRAY(A, n)
    low = 1
    high = 1
    sum = A[1]
    for i = 1 to n
        max_sum = A[i]
        tmp_sum = A[i]
        for j = i+1 to n
            tmp_sum += A[j]
            if tmp_sum > max_sum
                max_sum = tmp_sum
                tmp_low = i
                tmp_high = j
        if max_sum > sum
            sum = max_sum
            low = tmp_low
            high = tmp_high
    return (low, high, sum)

4.1-4

1

在比较left-sum, right-sum, cross-sum时，增加对0的比较，当0最大时，返回空数组

留言與分享

3. 函数的增长

本章给出集中标准方法来简化算法的渐进分析。

渐进符号

Θ 渐进紧确界

   $f(n)=\Theta(g(n))$ 类似于 a = b
   当n>n0时，存在常数c₁和c₂使得c₁·g(n) <= f(n) <= c₂·g(n)

Ο 渐进上界

   $f(n)=O(g(n))$ 类似于 a ≤ b
   当n>n₀时，存在一个常数c使得 f(n) <= c·g(n)

Ω 渐进下界

   $f(n)=\Omega(g(n))$ 类似于 a ≥ b
   当n>n₀时，存在一个常数c使得 f(n) >= c·g(n)

ο

   $f(n)=\omicron(g(n))$ 类似于 a < b

ω

   $f(n)=\omega(g(n))$ 类似于 a > b

此图为书中截图，很好的说明了Θ Ο Ω 的含义

留言與分享