《算法导论》12.3 插入和删除

一、插入和删除

1、插入

1、思路：引入一个辅助指针y，跟随树的结点向下遍历；根据z关键字的值和x的值的大小比较，遍历下面的孩子结点；最终决定插入到什么位置上。
2、伪代码：

TREE-INSERT(T,z)
1 y = NIL
2 x = T.root
3 while x != NIL
4 	y = x
5 if z.key < x:key
6 	x = x.left
7 else x = x.right
8 z.p = y
9 if y == NIL
10 	T.root = z // tree T was empty
11 elseif z.key < y:key
12 	y.left = z
13 else y.right = z 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、图解：

图中浅阴影结点表示了一条从树根向下到插入数据项位置处的简单路径（也是遍历顺序），虚线表示加入的一条链。
4、正式代码

#include 
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;
	TreeNode(int x):val(x), left(NULL), right(NULL), parent(NULL) {}
};

//向二叉树中插入结点
TreeNode* Insert_Node(TreeNode* root, TreeNode* z)
{
	TreeNode* y = NULL;
	TreeNode* x = root;
	//y随着结点向下遍历，途中选择往左还是往右
	while (x != NULL) {
		y = x;
		if (z->val < x->val) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NULL) {
		root = z;
	}
	else if (z->val < y->val) {
		y->left = z;
	}
	else {
		y->right = z;
	}
	return root;
}

//遍历二叉树
//递归写法
void inorderSortCure(TreeNode* root)
{
	if (root != NULL)
	{
		inorderSortCure(root->left);
		cout << root->val << " ";
		inorderSortCure(root->right);
	}
}

int main()
{
	TreeNode* root = new TreeNode(3);
	TreeNode* tmpl = new TreeNode(1);
	TreeNode* tmpr = new TreeNode(5);
	root->left = tmpl; tmpl->parent = root;
	root->right = tmpr; tmpr->parent = root;
	TreeNode* tmprl = new TreeNode(4);
	tmpr->left = tmprl; tmprl->parent = tmpr;
	TreeNode* tmprr = new TreeNode(6);
	tmpr->right = tmprr; tmprr->parent = tmpr;
	cout << "Result:" << endl;
	TreeNode* t = new TreeNode(0);
	root = Insert_Node(root,t);
	cout << "result:" << endl;
	inorderSortCure(root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

2、删除

（1）基本思路：分为三种情况
a、z没有孩子结点，直接将其删除并用NIL代替就行
b、z只有一个孩子，那么将孩子提升到树里z的位置上（代替）
c、z有两个孩子，先找到z的后继（一定在z的右子树中）y，并且让y来代替z。z中原来的右子树和左子树部分都成为了y新的右子树和左子树，但是这个比较复杂，下面会讲到。
（2）通过图解考虑：

（a）：z没有左孩子用右孩子来替换z，右孩子可以是NIL也可以不是。右孩子为NIL时，这种情况归为z没有孩子结点的情形；当不为NIL时，归为仅有一个孩子结点（右孩子）的情形。
（b）：结点z有一个左孩子但是没有右孩子，用l替换z。
（c）：结点z有两个孩子，左孩子是结点l，右孩子是其后继，y的右孩子是结点x。用y替换z；使l变为y的左孩子，x作为y的右孩子的现实不改变。
（d）：结点z有两个孩子，并且z的后继结点y!=r位于以r为根的子树中。用y自己的右孩子x来代替y，并且让y成为r的双亲；然后置y为q的孩子和l的双亲。

（3）Transplant
用TransPlant来让一棵以v为根的子树来替换一棵以u为根的子树，此时结点u的双亲就变成了结点v的双亲，并且最后v成为u双亲的孩子。

TRANSPLANT(T,u,v)
//当u为根的时候，直接赋给v
if u.p ==NIL
	T.root = v
//当u为左孩子的时候，将v变成左孩子
else if u == u.p.left 
	u.p.left = v
else u.p.right = v //右孩子
if v !=NIL
	v.p = u.p
1
2
3
4
5
6
7
8
9
10

（4）TREE-DELETE

if x.left == NIL
	TRANSPLANT(T,z,z.right)
elseif z.right ==NIL
	TRANSPLANT(T,z,z,left)
else y = TREE-MINIMUM(z.right)
	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
1
2
3
4
5
6
7
8
9
10
11
12

解释伪代码：
（1）第1~2行代码处理结点z没有左孩子的情况，第3 ~ 4行处理z有左孩子但是没有右孩子的情况。
（2）第5~12行处理剩下两种情况：第5行查找结点y，y是z的后继结点
（a）如果y是z的右孩子，那么10~12行将y替换z成为z双亲的一个孩子，用z的左孩子替换y的左孩子，右孩子不变。
（b）如果y不是z的左孩子，那么7 ~ 9行用y的右孩子替换y成为y双亲的一个孩子，然后将z的右孩子转变为y的右孩子，最后10~12行用y替换z变成z双亲的一个孩子，再用z的左孩子替换为y的左孩子（左孩子这个放前面也可以，但是要和（a）统一代码）。

再附一张和上面一样的图。

C++代码（delete完整代码）

#include 
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;
	TreeNode(int x) :val(x), left(NULL), right(NULL), parent(NULL) {}
};

//查找最小值
TreeNode* TreeNode_Minmum(TreeNode* root)
{
	TreeNode* p = root;
	while (p->left != NULL)
	{
		p = p->left;
	}
	return p;
}

//中序遍历打印递归写法
void inorderSortCure(TreeNode* root)
{
	if (root != NULL)
	{
		inorderSortCure(root->left);
		cout << root->val << " ";
		inorderSortCure(root->right);
	}
}
//TRANSPLANT(T,u,v)
void Transplant(TreeNode* root, TreeNode* u, TreeNode* v)
{
	//u为树根
	if (u->parent == NULL) {
		v = root;
		v->left->parent = v;
		v->right->parent = v;
	}
	//v替代u成为u父结点的子结点
	else if (u == u->parent->left) {
		u->parent->left = v;
	}
	else {
		u->parent->right = v;
	}
	//u父结点成为v的父结点
	if (v != NULL) {
		v->parent = u->parent;
	}
}

//TREE-DELETE(T,z)
void Tree_delete(TreeNode* root, TreeNode* z)
{
	//针对没有左孩子和有一个左孩子但是没有右孩子的情况
	if (z->left == NULL) {
		Transplant(root, z, z->right);
	}
	else if (z->right == NULL) {
		Transplant(root, z, z->left);
	}
	//针对后两种情况
	else {
		TreeNode *y = TreeNode_Minmum(z->right);
		if (y->parent != z) {
			Transplant(root, y, y->right);//y的right取代y
			//y代替z获得z的right
			y->right = z->right;
			y->right->parent = y;
		}
		Transplant(root, z, y);//y成为z父结点的子结点
		//y代替z获得z.left
		y->left = z->left;
		y->left->parent = y;
	}
}

int main()
{
	TreeNode* root = new TreeNode(3);
	TreeNode* tmpl = new TreeNode(1);
	TreeNode* tmpr = new TreeNode(5);
	root->left = tmpl; tmpl->parent = root;
	root->right = tmpr; tmpr->parent = root;
	TreeNode* tmprl = new TreeNode(4);
	tmpr->left = tmprl; tmprl->parent = tmpr;
	TreeNode* tmprr = new TreeNode(6);
	tmpr->right = tmprr; tmprr->parent = tmpr;
	Tree_delete(root,tmpr);
	inorderSortCure(root);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95