Week4 树（by 施伟）

二叉搜索树
红黑树
B树
最小生成树

##1、二叉搜索树

二叉搜索树性质：设 $x$ 是二叉搜索树中的一个结点。如果 $y $是 $x$ 的左子树中的一个结点，那么$y.key \leq x.key$。如果 $y$ 是 $x$ 的右> 子树中的一个结点，那么$y.key \geq x.key$。

###遍历

中序遍历(inorder tree walk)：输出的子树根的关键字位于其左子树的关键字值和右子树的关键字值之间。
前序遍历(preorder tree walk)
后序遍历(postorder tree walk)

INORDER-TREE-WALK(x)
if x != NIL
	INORDER-TREE-WALK(x.left)
	print x.key
	INORDER-TREE-WALK(x.right)

enter image description here

查询

####查找(SEARCH)

TREE-SEARCH(x,k)
if x==NIL or k==x.key 
	return x
if k<x.key
	return TREE-SEARCH(x.left, k)
else return TREE-SEARCH(x.right, k)

INTERATIVE-TREE-SEARCH(x, k)
while x!=NIL and k!=x.key
	if k<x.key
		x=x.left
	else x=x.right
return x

####最小(MINIMUM)

TREE-MINIMUM(x)
while x.left != NIL
	x=x.left
return x

####最大(MAXIMUM)

TREE-MAXIMUM(x)
while x.right != NIL
	x=x.right
return x

####后继(SUCCESSOR)

TREE-SUCCESSOR(x)
if x.right != NIL
	return TREE-MINIMUM(x.right)
y=x.p
while y!=NIL and x==y.right
	x = y
	y = y.p
return y

enter image description here 分两种情况：

如果结点 $x$ 的右子树非空，那么 $x$ 的后继恰是 $x$ 右子树中的最左结点。
如果结点 $x$ 的右子树为空并有一个后继 $y$，那么 $y$ 就是 $x$ 的最底层祖先，并且 $y$ 的左孩子也是 $x$ 的一个祖先。为了找到 $y$ ,只需简单地从 $x$ 开始沿树而上直到遇到这样一个结点：这个结点是其双亲的左孩子。例如13的后继15。 ####前驱(PREDECESSOR) 略

插入

将一个新值 $v$ 插入到一个二叉搜索树 $T$中。$z.key=v$, $z.left=NIL$, $z.right=NIL$

TREE-INSERT(T, Z)
y=NIL
x=T.root
while x!=NIL
	y=x
	if z.key < x.key
		x=x.left
	else x=x.right
z.p=y				#遍历y,找到z属于哪个结点
if y == NIL
	T.root=z		#tree T was empty
else if z.key<y.key
	y.left=z
else y.right=z

删除

三种情况：

如果 $z$ 没有孩子结点，直接简单删除，并修改它的父节点，用NIL作为孩子来替换 $z$
如果 $z$ 只有一个孩子结点，那么将这个孩子提升到树中 $z$ 的位置上，并修改 $z$ 的父节点，用 $z$ 的孩子来替换 $z$
如果 $z$ 有两个孩子结点，那么找 $z$ 的后继 $y$ (一定在 $z$ 的右子树中)，并让 $y$ 占据树中 $z$ 的位置。 $z$ 原来右子树部分称为 $y$ 的新的右子树，并且 $z$的左子树成为 $y$ 的新的左子树。定义一个TRANSPLANT函数，是用另一棵子树替换一棵子树并成为其双亲的孩子结点。

TRANSPLANT(T, u, v)
if u.p == NIL
	T.root = v
else if u == u.p.left
	u.p.left = v
else u.p.right = v
if v != NIL
	v.p = u.p

注意，这个函数并没有解决$v.left$ 和$v.right$ 的更新，这个需要调用者来解决。

TREE-DELETE	(T,z)
if z.left == NIL					#处理结点z没有左孩子的情况
	TRANSPLANT(T, z, z.right)
else if z.right == NIL				#处理结点z没有右孩子的情况
	TRANSPLANT(T, z, z.left)
else y = TREE-MINIMUM(z.right)		#查找结点y，它是z的后继
	if y.p != z
		TRANSPLANT(T, y, y.right)
		y.right = z.right
		y.right.p = y
	TRANSPLANT(T, z, y)
	y.left = z.left
	y.left.p = y

##2、红黑树 红黑树是一棵二叉搜索树。每个结点增加一个存储位来表示结点的颜色，RED或BLACK. 树中结点有五个属性：color, key, left, right和p

一棵红黑树是满足以下红黑性质的二叉搜索树：

每个结点或是红色的，或是黑色的。

根节点是黑色的。

每个叶结点(NIL)是黑色的。

如果一个结点是红色的，则它的两个子结点都是黑色的。

对每个结点，从该结点到其所有的后代叶结点的简单路径上，均包含相同数目的黑色结点。

黑高(black-height): bh(x), 从某个结点 $x$ 出发到达一个叶结点的任意一条简单路径上的黑色结点个数。引理: 一棵有 $n$ 个内部结点的红黑树的高度至多为$2lg(n+1)$. 用途和好处:

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。

旋转

enter image description here

LEFT-ROTATE(T, x)
	y = x.right				# set y
	x.right = y.left		# turn y's left subtree into 
	if y.left != T.nil		# x's right subtree
		y.left.p = y
	y.p = x.p				# link x's parent to y
	if x.p == T.nil
		T.root = y
	else if x == x.p.left
		x.p.left = y
	else x.p.right = y
	y.left = x				# put x on y's left
	x.p=y

enter image description here

插入

$O(lgn)$ 插入分为两个过程: RB-INSERT(T, z) + RB-INSERT-FIXUP(T, z)

RB-INSERT(T, z)
y = T.nil
x = T.root
while x != T.nil
	y = x
	if z.key < x.key
		x = x.left
	else x = x.right
z.p = y
if y == T.nil
	T.root = z
else if z.key < y.key
	y.left = z
else y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED
RB-INSERT_FIXUP(T, z)

与前面的TREE-INSERT相比：

TREE-INSERT里面的NIL替代为T.nil。
置 $z.left$ 和 $z.right$ 为 T.nil，以保持合理树结构。
$z$ 置为红色。
$z$ 可能违反红黑树特性，需要FIXUP。

RB-INSERT-FIXUP(T, z)
	while z.p.color == RED
		if z.p == z.p.p.left
			y = z.p.p.right
			if y.color == RED
				z.p.color = BLACK					# case 1
				y.color = BLACK						# case 1
				z.p.p.color = RED					# case 1
				z = z.p.p							# case 1
			else if z == z.p.right
				z = z.p								# case 2
				LEFT-ROTATE(T, z)					# case 2
			z.p.color = BLACK						# case 3
			z.p.p.color = RED						# case 3
			RIGHT-ROTATE(T, z.p.p)					# case 3
		else(same as then clause
				with "right" and "left" exchange)
		T.root.color = BLACK

case 1: $z$ 的叔节点 $y$ 是红色的
case 2: $z$ 的叔节点 $y$ 是黑色的且 $z$ 是一个右孩子
case 3: $z$ 的叔节点 $y$ 是黑色的且 $z$ 是一个左孩子

enter image description here

删除

$O(lg n)$ 先设计一个RB-DELETE需要调用的子过程RB-TRANSPLANT, RB-DELETE + RB-DELETE-FIXUP

RB-TRANSPLANT(T, u ,v)
if u.p == T.nil
	T.root = v
else if u == u.p.left
	u.p.left = v
else 
	u.p.right = v
v.p = u.p				# 与TREE_TRANSPLANT比，不许判断if v!=NIL

RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
	x = z.right
	RB-TRANSPLANT(T, z, z.right)
else if z.right == T.nil
	x = z.left
	RB-TRANSPLANT(T, z, z.left)
else 
	y = TREE-MINIMUM(z.right)
	y-original-color = y.color
	x = y.right
	if y.p == z
		x.p = y
	else 
		RB-TRANSPLANT(T, y, y.right)
		y.right = z.right
		y.right.p = y
	RB-TRANSPLANT(T, z, y)
	y.left = z.left
	y.left.p = y
	y.color = z.color
if y-original-color == BLACK
	RB-DELETE-FIXUP(T, x)

RB-DELETE-FIXUP(T, x)
while x != T.root and x.color == BLACK
	if x == x.p.left
		w = x.p.right
		if w.color == RED
			w.color = BLACK									#case 1
			x.p.color = RED									#case 1
			LEFT-ROTATE(T, x.p)								#case 1
			w = x.p.right									#case 1
		if w.left.color == BLACK and w.right.color == BLACK
			w.color = RED									#case 2
			x = x.p											#case 2
		else if w.right.color == BLACK
				w.left.color = BLACK						#case 3
				w.color = RED								#case 3
				RIGHT-ROTATE(T, w)							#case 3
				w = x.p.right								#case 3
			w.color = x.p.color								#case 4
			x.p.color = BLACK								#case 4
			w.right.color = BLACK							#case 4
			LEFT-ROTATE(T, x.p)								#case 4
			x = T.root										#case 4
	else(same as then clause with "right" and "left" exchanged)
x.color = BLACK

case 1: $x$ 的兄弟结点 $w$ 是红色的
case 2: $x$ 的兄弟结点 $w$ 是黑色的，而且 $w$ 的两个子结点都是黑色的
case 3: $x$ 的兄弟结点 $w$ 是黑色的，$w$ 的左孩子是红色的，$w$ 的右孩子是黑色的
case 4: $x$ 的兄弟结点 $w$ 是黑色的，且 $w$ 的右孩子是红色的

3、B树

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。一棵 $B$ 树 $T$ 是具有以下性质的有根树(根为 $T.root$):

每个结点 $x$ 有下面属性: - $x.n$, 当前存储在结点 $x$ 中的关键字个数。 - $x.n$个关键字本身 $x.key_1, x.key_2, ... , x.key_x._n $, 以非降序存放，使得$x.key_1\leq x.key_2\leq ...\leq x.key_x._n $ - $x.leaf$ ，一个布尔值，如果 $x$ 是叶结点，则为TRUE，如果 $x$是内部结点，则为FALSE。

每个内部结点 $x$ 还包含 $x.n+1$ 个指向其孩子的指针，$x.c_1, x.c_2, ... , x.c_{n+1}$。叶子结点没有孩子，所以他们的 $c_i$ 属性没有定义。

关键字 $x.key_i$ 对存储在各个子树中的关键字范围加以分割：如果 $k_i$ 为任意一个存储在以 $x.c_i$ 为根的子树中的关键字，那么 $k_1\leq x.key_1\leq x.key_2 \leq ... \leq x.key_{x.n} \leq k_{x.{n+1}}$

每个叶结点具有相同的深度，即树的高度 $h$.

每个结点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数的固定整数 $t\geq 2$ 来表示这些界： a. 除了根节点以外每个结点必须有 $t-1$ 个关键字。因此除了根结点以外的每个内部结点至少有 $t$ 个孩子。 b. 每个结点最多可包含 $2t-1$ 个关键字，称为该结点是满的

定理：如果 $n\geq 1$, 那么对任意一棵包含 $n$ 个关键字，高度为 $h$ ，最小度数 $t\geq 2$的B树 $T$, 有 $h\leq log_t\frac{n+1}{2}$

enter image description here

搜索B树

B-TREE-SEARCH(x, k)
i=1
while i <= x.n and k>x.key_i
	i++
if i <= x.n and k == x.key_i
	return(x, i)
else if x.leaf
	return NIL
else DISK_READ(x, c_i)
	return B-TREE-SEARCH(x.c_i, k)

创建空B树

B-TREE-CREATE(T)
x = ALLOCATE-NODE()
x.leaf = TRUE
x.n = 0
DISK-WRITE(x)
T.root = x

###插入关键字

分裂

enter image description here

插入

enter image description here

删除

case 1：如果关键字k在结点x中，并且x是叶结点，则从x中删除k。 case 2：如果关键字k在结点x中，并且x是内部结点，则做一下操作：

如果结点x中前于k的子结点y至少包含t个关键字，则找出k在以y为跟的子树中的前驱 $k'$ , 递归地删除 $k'$ ，并在x中用$k'$ 代替k
对称的，如果y有至少t个关键字，则检查结点x中后于k的子结点z。如果z至少有t个关键字，则找出k在以z为根的子树中的后继 $k'$。递归地删除$k'$ 并在x中用$k'$ 代替k
否则，如果y和z都只有t-1个关键字，则将k和z的全部合并进y，释放x并递归地从y中删除k

case 3：如果关键字k当前不在内部结点x中，则确定必包含k的子树的根 $x.c_i$(如果k确实在树中)

如果 $x.c_i$只含有t-1个关键字，但是它的一个相邻的兄弟至少包含t个关键字，则将x中的某一个关键字降至 $x.c_i$ 中，将 $x.c_i$ 的相邻左兄弟或右兄弟的一个关键字升至x，将该兄弟中相应的孩子指针移到$x.c_i$中。
如果$x.c_i$ 以及 $x.c_i$ 的所有相邻兄弟都只包含t-1个关键字，则将$x.c_i$ 和一个兄弟合并，即将x的一个关键字移至新合并的结点，使之成为该结点的中间关键字。

4、最小生成树

最小生成树: 给定一个连通无向图 $G=(V,E)$, $(u,v)$ 代表连接顶点 $u$ 与顶点 $v$ 的边, 而$w(u,v)$ 代表此边的权重，若存在 $T$ 为 $E$ 的子集且为无循环图，使得 $w(T)=\sum_{(u,v)\in T}w(u,v)$ 的 $w(T)$最小，则此 $T$ 为 $G$的最小生成树。

几个定义：

A是某棵最小生成树的子集，如果选择一条边 $(u,v)$，使得 $A\cup (u,v)$ 也是某棵最小生成树的子集，则称这样的边对为集合A的安全边。
无向图 $G=(V,E)$的一个切割$(S,V-S)$是集合V的一个划分。
如果一条边的两个顶点，一个位于S，另一个位于V-S，则称该条边横跨切割$(S,V-S)$。
如果集合A中不存在横跨该切割的边，则称该切割尊重集合A。
在横跨一个切割的所有边中，权重最小的称为轻量级边

定理：设 $G=(V,E)$是一个在边E上定义了实数值权重函数$w$的连通无向图。设集合A为E的一个子集，且A包括在图G的某棵最小生成树中，设$(S,V-S)$是图G中尊重集合A的任意一个切割，又设 $(u,v)$是横跨切割$(S,V-S)$的一条轻量边。那么边 $(u,v)$对集合A是安全的。

Kruskal算法

MST-KRUSKAL(G,w) $A = \emptyset$ for each vertex $v \in G.V$ MAKE-SET(v) sort the edges of $G.E$ into nondecreasing order by weight $w$ for each edge $(u.v) \in G.E$, taken in nondecreasing order by weight if $FIND-SET(u)\neq FIND-SET(v)$ $A=A \cup {(u, v)}$ $UNION(u, v)$ return A enter image description here

Prim算法

enter image description here

#The End

Leetcode:

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Week4 树（by 施伟）

查询

插入

删除

旋转

插入

删除

3、B树

搜索B树

创建空B树

分裂

插入

删除

4、最小生成树

Kruskal算法

Prim算法

Clone this wiki locally