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

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’$做右旋操作即可：