斯坦福算法专项课程Course2 week3内容回顾

这一周的内容主要介绍了一些常用的数据结构。

Course 2 Week 3

Heap

Heap是一种特殊的数据结构,其特点为父节点的值或者都不小于子节点,或者都不大于子节点,所以根节点或者为最小值(此时称为最小堆),或者根节点为最大值(此时称为最大堆),来看下堆的具体特点:

以最小堆为例,堆支持如下操作:

下面介绍堆的实现方法(以最小堆为例):

Implementation

我们这里使用数组表示Heap,注意此时用完全二叉树表示堆,特点为第$i$个元素的父节点为第$[i/2]$个元素,子节点为$2i,2i+1$(注意下标从1开始),来看个图示:

有了这种表示之后,下面介绍Insert以及Extract-Min

Insert

将元素插入队尾(记下标为$i$),如果该元素小于其父节点元素(第$[i/2]$个元素),那么插入成功;否则交换其父节点和该元素的位置,重复此操作直至满足条件或者无法交换为止。可以看到,因为堆是用完全二叉树表示,所以树的高度为$O(\log n)$,所以最多交换$O(\log n)$次。

下面从一个图示中看下具体过程:

Extract-Min

删除位置为$1$的元素,将队尾元素放置在第一个位置,如果该元素小于等于其两个子节点,则删除成功;否则将该元素与其较小的子节点交换,重复此操作直至满足条件或者无法交换为止。同理可得最多交换$O(\log n)$次。

从一个图示中看下具体过程:

最后介绍几个堆的应用:

Application: Sorting

假设输入长度为$n$,首先用$O(n)$的时间进行堆化,不停地Extract-Min,每次的时间复杂度为$O(\log i)$,一共操作$n$次,所以时间复杂度为$O(n\log n)$,和归并排序的效果一致,这种排序方法称为堆排序。

Application: Median Maintenence

问题:依次输入$n$个元素$x_1,…,x_n$

要求:每一步在$O(\log i)$时间内找出中位数

方法:

设置两个堆(假设此时已输入$i$个元素),一个最小堆,一个最大堆,最大堆存储前$[i/2]$小的元素,其余元素存储在最小堆中。所以每次最大堆可以在$O(\log i)$时间内输出第$[i/2]$大的元素$a$,最小堆可以在$O(\log i)$时间内输出第$[i/2]+1$大的元素$b$,从而一共可以在$O(\log i)$时间内输出中位数。接下来的任务就是如何维持两个堆的元素数量的平衡性,假设现在获得了第$i+1$个元素$x_{i+1}$,如果$x_{i+1} < a$,则将$x_{i+1}$放入最大堆,否则将$x_{i+1}$放入最小堆,放置完成之后,如果堆中元素数量相差$2$,则从元素较多的堆栈中弹出栈顶元素,将其插入到另一个堆栈中,注意其中每一步的时间复杂度都为$O(\log i)$,所以总共的时间复杂度也为$O(\log i)$

Application: Speeding Up Dijkstra

还有一个应用就是加速上周介绍的Dijkstra算法,假设有$n$个节点,$m$条边,上周使用的方法是将未访问节点存入Heap,这样最后的时间复杂度为$O(m\log n)$

Binary Search Tree

二叉搜索树是一种特殊的二叉树,最大的特点为每个节点的左子节点都小于节点,右节点都大于节点,如下图:

该数据结构支持的操作如下:

The Height of a BST

不难发现,搜索的效率和树的高度有关,一般的二叉搜索树的高度介于$\log_2 n$到$n$之间,例子如下:

Searching and Inserting

由于二叉搜索树的特点,我们可以用类似二分查找的方法查找元素$x$,即如果$x$等于节点,直接返回,如果$x$小于节点,则查找左子树,否则查找右子树。插入操作可以先在树中查找该元素,再根据返回的位置插入,具体如下:

Min, Max, Pred, And Succ

找最小元素只要不停返回节点的左子节点,直至该节点没有左子节点即可,找最大元素同理。Pred操作是指找到小于元素$x$的最大元素,可以先在树中搜索$x$,如果$x$的左子树非空,则返回其左子树的最大元素即可,否则返回$x$的父节点中第一个小于$x$的节点:

In-Order Traversal

二叉搜索树的中序遍历会按照从小到大的顺序输出树中的节点:

Deletion

删除操作比较麻烦,分几种情形讨论。

首先查找该元素,如果该元素没有子节点,则直接删除;如果该元素有一个子节点,则删除该元素,子节点放入该元素的位置即可:

如果有两个子节点,计算该元素的Pred,即该元素左子树中最大元素(该最大元素必然没有右子节点),交换Pred和该元素,然后再按照前两种方式删除:

Select and Rank

在树中额外存储一些信息,例如定义size(x)为以$x$为根节点的子树元素数量,那么

其中$y,z$为左右子节点。

最后介绍如何利用size查找次序统计量,即从小到大排序为$i$的元素,按照如下方式即可:

时间复杂度为$\theta(\text{height})$

Red-Black Trees

Binary Search Tree的操作都和height有关,但是我们知道一般的BST高度可能达到$\theta(n)$,所以我们需要更平衡的二叉搜索树,这类树就叫Balanced Search Trees,红黑树就是其中一个特例,下面介绍其特点。

Red-Black Invariants

红黑树有以下4个不变量

  • 每个节点是红色或者黑色
  • 根节点是黑色
  • 没有连续两个红色节点(即红色节点的子节点必然为黑色)
  • 每个root-NULL的路径中黑色节点数量一致

来看几个例子:

Height Guarantee

红黑树最大的特点就在于高度可以保持为$\theta(\log_2 n)$,有如下结论:

证明:

令$b(x)$为x-NULL路径中黑色节点的数量,我们证明$x$的后代元素数量至少为$2^{b(x)}-1$,关于$b(x)$的大小利用数学发归纳法证明:

如果$b(x)=0$,$2^{b(x)}-1=0$,结论显然成立,假设对于$b(x)-1$成立,则$x$的后代数量为$d(x)$,则

所以结论成立。

假设$h(x)$为$x$的height,那么由红黑树的性质3可得

所以

由于插入删除的时候会破坏树的结构,为了维护红黑树的性质,我们需要对插入删除操作做一些说明,首先介绍Rotation 的概念。

Rotation

从图中第一棵树变为第二课树的过程称为right rotation of x,反过来的过程称为left rotation of y。Rotation操作在红黑树中非常常用,下面将利用Rotation完成插入的工作。

Insertion In A Red-Black Tree

假设插入元素为$x$,我们找到$x$,其父节点为$p$,下面分为三种情形讨论。

情形1:

$p$是黑色,则$x$直接涂为红色即可。

情形2:

$p$为红色,$p$的父节点$p’$为黑色,$p$的兄弟节点$u$为红色,则按下图的方式处理即可:

情形3:

$p$为红色,$p$的父节点$p’$为黑色,$p$的兄弟节点$u$为黑色,将$p’$涂红,$u$涂黑,再对$p’$做右旋操作即可: