CS61B

以下是看CS61B时做的笔记。CS61B主要教授Java语言的应用和算法与数据结构,本篇侧重算法与数据结构。

List (链表)

查看这里。

原本计划的是一种数据结构开一篇,但计划赶不上变化,故只能将网课内容合做一篇了。

Disjoint Sets (不相交集)

对于以下链式结构

graph TD
A[0] -->B[1] -->C[2]-->D[3]
E[4]-->F[5]
G[6]

需要设计以下函数

1
2
3
ds = DisjointSets(7);
ds.connect(1, 2); // 链接两个数
ds.isConnect(1, 2); // 检测两个数是否链接

需要寻求其高效的实现方式。

表与集合的嵌套

这是最显而易见的办法。
指定List<Set<Integer>>,实现方法时,先逐个寻找数字所在的集合,然后进行集合的合并或判断其是不是在同一个集合内。但该方法耗时较长。其构建、链接、判断的复杂度均为$O(n)$。
[{1,2,3,4}, {5,6}, {7}]

但是用封装好的集合类总让人有一种复杂度其实是$O(1)$的感觉。

数组索引

通过构建与元素等长的数组,用数组的索引值指代数字,数组的数字指代集合。当进行链接时,全组改为同一个数字。检查两数是否链接,只需要判断其索引对应的数字是否相同即可。

element 3 3 3 3 5 5 7
index 0 1 2 3 4 5 6

需要进行connect()函数操作时,将两个集合中的数改为同一个数。

1
connect(0, 4);
element 5 5 5 5 5 5 7
index 0 1 2 3 4 5 6
由此,虽然构建、链接的复杂度仍为$O(n)$,但判断的复杂度变成了$O(1)$。

用数组实现树

将集合变成树的形式,在一维数组中显示,仍然用索引值表示数字,但同时指明树的关系
对于以下树

graph TD
A[0]-->B[1]-->C[2]
A-->D[4]
E[3]-->F[5]
G[6]

构建等长数组

element -1 0 1 -1 0 3 -1
index 0 1 2 3 4 5 6

分析其数组中的值。为-1时,表明索引中的数是根节点。为大于-1的数时,表明索引中的数的父节点。
进行connect操作时,爬取两个节点的根节点,再将一个根节点连接到另一个即可。如图所示

1
connect(4, 5);

等效于

graph TD
A[0]-->B[1]-->C[2]
A-->D[4]
A-->E[3]-->F[5]
G[6]

数组

element -1 0 1 3 0 3 -1
index 0 1 2 3 4 5 6

但为了确保小树能拼接到大树上(确保树的高度较小),需要另外构建一个尺寸数组

element -1 0 1 -1 30 3 -1
size 3 6 2 1 2 1 1 1
index 0 1 2 3 4 5 6

或者实行更好的办法:给该数组中的根节点加上权重

element -4 -6 0 1 -1 30 3 -1
index 0 1 2 3 4 5 6

进行connect操作时需比较其尺寸大小。如此,该图结构就不会是线序的了。其构建复杂度不变,但链接和查找的难度均降为$O(\log N)$。

进一步优化的方法

在叶子节点向上回溯时,将涉及到的节点全部断连并链接至根节点,这样,日后进行查找时,可以大大节省时间。

Binary Search Tree (二叉搜索树)

二叉搜索树是这样一种二叉树,对存放的数据有这样的要求:某节点的左侧子树数据均比其小,右侧子树的数据均比其大。显而易见,其算法复杂度为$O(\log N)$。

理想状况下,一棵二叉搜索树足够浓密,搜索的算法复杂度则为$O(\log N)$,但如若操作不当,使插入的结点都在树的一侧,那么查找算法复杂度将退化为$O(N)$。

查找

BST通过递归查找,其过程较为简单。

1
2
3
4
5
6
7
8
9
10
static BST find(BST T, key k) {
if(T == null)
return null;
k.equals(T.key)
return T;
if(k < T.key)
return find(T.left, k);
else
return find(T.right, k);
}

插入

插入的过程也很简单。

1
2
3
4
5
6
7
8
9
static BST insert(BST T, key k) {
if(T == null)
return new BST(k);
if(k < T.key)
T.left = insert(T.left, k);
else if(k > T.key)
T.right = insert(T.right, k);
return T;
}

删除

删除过程较为复杂,可将其拆成3种情况

  1. 叶子节点:找到后直接删除。
  2. 只有一个孩子节点的节点,可以将其父节点指向其子节点,该节点将自动删除(如果不是Java,则需要手动清理内存)
  3. 有两个孩子节点的节点,需要找到该节点左子树中最大的节点或右子树中最小的节点将其替换掉。

B-树

对于以下树

graph TD
13-->5-->2
5-->7
13-->15-->14
15-->16

如果插入数据16、17、18、19,那么数据将会挤在右子树一侧,并不高效。一种可行的办法是几个数据挤在一个枝叶节点中。

graph TD
13-->5-->2
5-->7
13-->15-->14
15-->a[16 17 18 19]

但单侧插入得多后,顺序表的寻找也同样有$O(N)$的复杂度。因此需要为顺序表大小设定一个限度。当一个表中数据溢出时,就将其中中间的一个节点放到父节点中。假设以下的树中一个节点最多只能存放3个数字。

graph TD
13-->5-->2
5-->7
13-->b[15 17]-->14
b-->16
b-->a[18 19]

其中的[15, 17]节点上,小于15的数在其左子树,在15和17之间的数在中间子树,大于17的数在右子树。当继续插入数据时,也依次进行类似操作。

graph TD
a[13]-->5-->2
5-->7
a-->b[15 17 19]-->14
b-->16
b-->18
b-->c[20 21 25 26]

$$
\downarrow
$$
最小项生成靠左的子树,第二项向上移动

graph TD
a[13]-->5-->2
5-->7
a-->b[15 17 19 21]-->14
b-->16
b-->18
b-->20
b-->c[25 26]

$$
\downarrow
$$
最小项生成靠左的子树,第二项向上移动

graph TD
a[13 17]-->5-->2
5-->7
a-->15-->14
15-->16
a-->b[19 21]
b-->18
b-->20
b-->c[25 26]

如果根节点也满了,就向上生成新的根节点。
对于具有以上特点的树,称作B-树。当其被赋予特定规则时,则另称2-3树2-3-4树
对源代码感兴趣的可以看这里

树的旋转

树的旋转能够在改变结构的同时不改变节点的值,是实现avl树和红黑树的基本操作。

引例

对于以下结构

graph TD
5-->a{child}
5-->A[9]-->7
A-->b{child}

要实现5的左旋操作,即将5从根节点变成左节点。由此。需要将右节点9变成根节点。

graph TD
5-->a{child}
5-->c{null}
A[9]-->5
A-->7
A-->b{child}

此时这棵树有一个不合理的地方,就是根节点9分出的树枝有3个,不符合二叉树的定义。恰好,5的右节点由于旋转空了出来,刚好可以容纳多余的节点。于是结果变成了

graph TD
5-->a{child}
5-->7
A[9]-->5
A-->b{child}

以上就是将一个节点左旋的过程。右旋也遵循类似的操作。如果不太明白上述的操作,也可以借助B-树的知识进行理解。
同样的一棵树

graph TD
5-->a{child}
5-->A[9]-->7
A-->b{child}

在进行左旋时,可以将需要变换主从次序的两个节点暂时合到一起。即先和右节点合并,再将5分配下去。

graph TD
A[5  9]
A-->B{child}
A-->7
A-->C{child}

$$
\downarrow
$$
然后分开

graph TD
5-->a{child}
5-->7
A[9]-->5
A-->b{child}

多次旋转

经过多次旋转,可以将一棵不平衡树转变成平衡树

graph TD
1-->A[null]
1-->C[3]-->2
C-->B[null]

$$
\downarrow
$$
3右旋

graph TD
1-->A[null]
1-->C[2]-->B[null]
C-->3

$$
\downarrow
$$
1左旋

graph TD
2-->1
2-->3

成功变成了平衡树。

AVL树简介

AVL树在普通BST的基础上,给每个节点添加了平衡因子,平衡因子=左子树高度-右子树高度
插入一个元素时,从该节点回溯到其根节点的所有节点的平衡因子都会发生变化。当平衡因子的绝对值 >1时,进行旋转操作。

Left Leaning Red-Black Tree (左倾红黑树)

哈希表


CS61B
http://example.com/2024/11/07/cs61b/
作者
Ivan Chen
发布于
2024年11月7日
许可协议
IVAN