《算法导论》学习总结 — 11. 第12章 二叉查找树

建议先看看前言:http://www.wutianqi.com/?p=2298

推荐在看算法导论的这一章之前先看看严蔚敏老师在《数据结构》上的二叉查找树。

整体来说二叉查找树不难,就是插入和删除节点时让人纠结,我就是在删除节点时各种纠结了。

二叉树执行基本操作的时间与树的高度成正比。

首先说下二叉查找树的性质

设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]<=key[x];如果y是x的右子树的一个结点,则key[y]>=key[x]。

注意这个性质,和堆对比下,还是有区别的,并且这个性质表示二叉查找树的根节点的左子树中所有结点都小于根结点,所有右子树的结点都大于根结点。所以根据这个性质,可以用中序访问二叉查找数来实现从小大到排列。

 

首先看看这个二叉查找树(P151图12-1(a)):

chazhaoshu1

图1

按中序遍历结果为:

2->3->5->5->7->8

接下来说说二叉查找树的几个操作:

SEARCH:查找关键字等于key的结点

MINIMUM:找出关键字最小的结点

MAXIMUM:找出关键字最大的结点

SUCCESSOR:找出结点x的后继y

INSERT:在二叉查找树中插入结点z

DELETE:在二叉查找树中删除结点z

里面就INSERT和DELETE麻烦一些。

首先逐步分析代码

①.BST的数据结构

1
2
3
4
typedef struct Node{
	int key;
	Node *lchild, *rchild, *parent; 
}Node, *BSTree;

②.BST的中序遍历

根据BST的性质,对于一个根结点x,所以比x小的结点都在x的左子树中,所有比x大的结点都在x的右子树中,并且没一个结点都满足这个性质,所以可以利用中序遍历,按从小到大的顺序输出这个BST。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 递归版本
Node * BSTreeSearch(BSTree T, int k)
{
	if(T == NULL || k == T->key)
		return T;
	if(k < T->key)
		return BSTreeSearch(T->lchild, k);
	else
		return BSTreeSearch(T->rchild, k);
}
// 非递归版本
BSNode * IterativeBSTreeSearch(BSTree T, int k)
{
	while(T != NULL && k != T->key)
	{
		if(k < T->lchild->key);
			x = T->lchild;
		else
			x = T->rchild;
	}
	return x;
}

③.BST的最大值与最小值

依然是利用BST的左子树结点,根结点,右子树结点的大小关系,不解释。。。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
Node * BSTreeMinimum(BSTree T)
{
	while(T->lchild != NULL)
		T = T->lchild;
	return T;
}
 
Node * BSTreeMaximum(BSTree T)
{
	while(T->rchild != NULL)
		T = T->rchild;
	return T;
}

下面开始有些麻烦了。

④.BST的后继

这是其伪代码:

1
2
3
4
5
6
7
8
TREE-SUCCESSOR(x)
1  if right[x] ≠ NIL
2      then return TREE-MINIMUM (right[x])
3  y ← p[x]
4  while y ≠ NIL and x = right[y]
5      do x ← y
6         y ← p[y]
7  return y

根据其后继的特性,结点x的后继是具有大于key[x]中的关键字最小者的那个结点

第1~2行,x的右子树的结点都是大于key[x]的结点,所以如果x有右子树,则在右子树中寻找最小值

第3~6行,如果没有右子树,则其后继y,是x的父亲结点的第一个右子树(考虑为什么呢?根据特性:结点x的后继是具有大于key[x]中的关键字最小者的那个结点。因为x没有右子树,所以这时,按中序遍历的x下一个结点即后继,应该是这样一个子树的根结点y,x的祖先是其左孩子,这样,y就大于其左子树所有结点,并且因为x是y的左子树中最大的结点了)。这个说着肯定是云里雾里,还是看图分析最好了,依然利用上面的图1:

chazhaoshu1

叶子结点5的后继是根结点5.

具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
Node *BSTreeSuccessor(Node *x)
{
	if(x->rchild != NULL)
		return BSTreeMinimum(x->rchild);
	Node *y = x->parent;
	while(y != NULL && x == y->rchild)
	{
		x = y;
		y = y->parent;
	}
	return y;
}

⑤.BST的插入

比如要把结点z插入二叉查找数T中,分以下几步:

1.将key[z]从根结点x开始比较,并用y记录x的父亲结点,直到到达最后一层某一叶节点比较完,此时y指向某一叶节点,x是NULL。

2.如果此时y是NULL,则证明是空树,于是根结点就是z

3.否则如果key[z]小于key[y],则让left[y] = z;当key[z]大于或等于key[y],则让right[y] = z。

插入就是那么简单。

看看伪代码,就是按这个步骤来的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TREE-INSERT(T, z)
 1  y ← NIL
 2  x ← root[T]
 3  while x ≠ NIL
 4      do y ←  x
 5         if key[z] < key[x]
 6            then x ← left[x]
 7            else x ← right[x]
 8  p[z] ← y
 9  if y = NIL
10     then root[T] ← z              // Tree T was empty
11     else if key[z] < key[y]
12             then left[y] ← z
13             else right[y] ← z

具体的代码如下:

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
void BSTreeInsert(BSTree &T, int k)
{
	Node *y = NULL;
	Node *x = T;
	Node *z = new Node;
	z->key = k;
	z->lchild = z->parent = z->rchild = NULL;//////////
 
	while(x != NULL)
	{
		y = x;
 
		if(k < x->key)
			x = x->lchild;
		else
			x = x->rchild;
	}
 
	z->parent = y;
	if(y == NULL)
	{
		T = z;
	}
	else
		if(k < y->key)
			y->lchild = z;
		else
			y->rchild = z;
}

⑥.BST的删除

比如要把二叉查找数T中的z结点删除掉,这是要分三种情况:

1.z没有左子树和右子树:

汗,这个就是直接删除z,把z的父亲结点parent[z]指向z的子树设置为NULL。

chazhaoshu2

如图,直接删除z,并让结点12的右子树为NULL。

2.z只有左子树或者只有右子树:

这个是让z的子树与其父亲结点相连,删除z即可。

chazhaoshu3

如图,此时直接删除z,并让z的子树20的父亲结点变成z的父亲结点15。

3.z既有左子树又有右子树:

这是先用SUCCESSOR找到z的后继y,因为y一定没有左子树(考虑为什么?下面解释),所以可以删除y,并让y的父亲结点成为y的右子树的父亲结点(类似第2中情况),并用y的key代替z的key。

chazhaoshu5

如图,y的右子树7成为10的子树,并且y取代了z的未知。

这是我们来考虑一个关键问题,y为何一定没有左子树?(习题12.2-5)

答:因为y是z的后继,所以y是z的右子树中最小的一个结点,如果y还有左子树,则y的左子树中的结点一定比y小!
具体代码如下:

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
Node* BSTreeDelete(BSTree T, Node *z)
{
	Node *x, *y;
	// z是要删除的节点,而y是要替换z的节点
	if(z->lchild == NULL || z->rchild == NULL)   
		y = z;   // 当要删除的z至多有一个子树,则y=z;
	else
		y = BSTreeSuccessor(z);  // y是z的后继
	if(y->lchild != NULL)
		x = y->lchild;  
	else
		x = y->rchild;
	if(x != NULL)
		x->parent = y->parent;  //如果y至多只有一个子树,则使y的子树成为y的父亲节点的子树
	if(y->parent == NULL)   // 如果y没有父亲节点,则表示y是根节点,词典其子树x为根节点
		T = x;
	else if(y == y->parent->lchild)   
		// 如果y是其父亲节点的左子树,则y的子树x成为其父亲节点的左子树,
		// 否则成为右子树
		y->parent->lchild = x;
	else
		y->parent->rchild = x;
	if(y != z)
		z->key = y->key;
	return y;
}

下面是整个二叉查找树的实现:

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
* Author: Tanky Woo
* Blog:   www.WuTianQi.com
* Description: 《算法导论》第12章 BST
*/
#include <iostream>
#define NULL 0
using namespace std;
 
// ①
typedef struct Node{
	int key;
	Node *lchild, *rchild, *parent; 
}Node, *BSTree;
 
// ②
Node * BSTreeSearch(BSTree T, int k)
{
	if(T == NULL || k == T->key)
		return T;
	if(k < T->key)
		return BSTreeSearch(T->lchild, k);
	else
		return BSTreeSearch(T->rchild, k);
}
 
/*
// 2011-5-16号改正,之前把T写成x了,感谢manfeyn提醒
Node * IterativeBSTreeSearch(BSTree T, int k)
{
	while(T != NULL && k != T->key)
	{
		if(k < T->lchild->key)
			T = T->lchild;
		else
			T = T->rchild;
	}
	return T;
}
*/
 
// ③
Node * BSTreeMinimum(BSTree T)
{
	while(T->lchild != NULL)
		T = T->lchild;
	return T;
}
 
Node * BSTreeMaximum(BSTree T)
{
	while(T->rchild != NULL)
		T = T->rchild;
	return T;
}
 
// ④
Node *BSTreeSuccessor(Node *x)
{
	if(x->rchild != NULL)
		return BSTreeMinimum(x->rchild);
	Node *y = x->parent;
	while(y != NULL && x == y->rchild)
	{
		x = y;
		y = y->parent;
	}
	return y;
}
 
// ⑤
void BSTreeInsert(BSTree &T, int k)
{
	Node *y = NULL;
	Node *x = T;
	Node *z = new Node;
	z->key = k;
	z->lchild = z->parent = z->rchild = NULL;
 
	while(x != NULL)
	{
		y = x;
 
		if(k < x->key)
			x = x->lchild;
		else
			x = x->rchild;
	}
 
	z->parent = y;
	if(y == NULL)
	{
		T = z;
	}
	else
		if(k < y->key)
			y->lchild = z;
		else
			y->rchild = z;
}
 
// ⑤
Node* BSTreeDelete(BSTree T, Node *z)
{
	Node *x, *y;
	// z是要删除的节点,而y是要替换z的节点
	if(z->lchild == NULL || z->rchild == NULL)   
		y = z;   // 当要删除的z至多有一个子树,则y=z;
	else
		y = BSTreeSuccessor(z);  // y是z的后继
	if(y->lchild != NULL)
		x = y->lchild;  
	else
		x = y->rchild;
	if(x != NULL)
		x->parent = y->parent;  //如果y至多只有一个子树,则使y的子树成为y的父亲节点的子树
	if(y->parent == NULL)   // 如果y没有父亲节点,则表示y是根节点,词典其子树x为根节点
		T = x;
	else if(y == y->parent->lchild)   
		// 如果y是其父亲节点的左子树,则y的子树x成为其父亲节点的左子树,
		// 否则成为右子树
		y->parent->lchild = x;
	else
		y->parent->rchild = x;
	if(y != z)
		z->key = y->key;
	return y;
}
 
 
 
void InBSTree(BSTree T)
{
	if(T != NULL)
	{
		InBSTree(T->lchild);
		cout << T->key << " ";
		InBSTree(T->rchild);
	}
}
 
 
 
int main()
{
	int m;
	BSTree T = NULL;
	for(int i=0; i<6; ++i)
	{
		cin >> m;
		BSTreeInsert(T, m);
		cout << "二叉查找树中序查找:";
		InBSTree(T);
		cout << endl;
	}
	cout << "删除根节点后:";
	BSTreeDelete(T, T);
	InBSTree(T);
}

结果如图:

OK,BST分析完了,这一章一定要搞懂,否则下一章的Red-Black-Tree就会一抹黑了~~~

Tanky Woo 标签:

《算法导论》学习总结 — 10. 第10章(略) && 第11章 散列表

建议先看看前言:http://www.wutianqi.com/?p=2298

 

第10章没法说,数据结构还是看严奶奶的比较好,所以《算法导论》上的这一章我随便瞄了几眼就过去了,不过话说回来,数据结构非常重要!!!所以,大家最好把严蔚敏的《数据结构》认认真真的看N遍!!!

另外,推荐看看这个:

数据结构的源码实现:http://www.cppleyuan.com/viewthread.php?tid=418

 

第11章散列表也属于数据结构方面的知识,第10章只是讲了最基本的几个结构。这一章也很简单,其实就是介绍了一些概念及思想,很容易理解。(你可以把散列表想象成平时用的英语字典,26个英文字母就是下标,通过它来定位你要查的单词。)

所以这一章我就不重复去打出概念了,我把几个散列函数和处理碰撞的方法放在图表里方便对比。

 

①.散列表的优点:出色的期望性能。

②.引出:

直接寻址表(P132)的缺点:

1.全域U也许会很大。

2.实际关键字域K也许相对于U会很小。

由此引出了散列表。

以下是我总结对比的表:

sanlie1

sanlie4

这一章我也不知道该怎么说,表面上感觉比较简单,但是如果深入研究,会发现它的内容太多了,而且很好很强大。所以还是建议大家看看书也许以后深入了解了我会再补充。

 

Tanky Woo 标签:

HDU/HDOJ 1080 Human Gene Functions

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1080

经典的DP问题。

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
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int c[5][5]=
{
     5, -1, -2, -1, -3,
    -1,  5, -3, -2, -4,
    -2, -3,  5, -2, -2,
    -1, -2, -2,  5, -1,
    -3, -4, -2, -1, -10000
};
 
char s1[105], s2[105];
int s3[105], s4[105];
int a[105][105];
int n, len1, len2;
 
int fun(char m)
{
    if(m == 'A')
        return 0;
    else if(m == 'C')
        return 1;
    else if(m == 'G')
        return 2;
    else if(m == 'T')
        return 3;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n;
    while(n--)
    {
        memset(a, 0, sizeof(a));
        cin >> len1;
        cin >> s1+1;
        cin >> len2;
        cin >> s2+1;
 
        for(int i=1; i<=len1; ++i)
            s3[i] =fun(s1[i]);
        for(int i=1; i<=len2; ++i)
            s4[i] =fun(s2[i]);
        //cout << s1+1 << " " << s2+1 << endl;
 
         a[0][0]=0;
         for(int i=1; i<=len1; ++i)
             a[i][0] = a[i-1][0] + c[s3[i]][4];
         for(int i=1; i<=len2; ++i)
             a[0][i] = a[0][i-1] + c[4][s4[i]];
 
         for(int i=1; i<=len1; ++i)
             for(int j=1; j<=len2; ++j)
             {
                 int k = a[i-1][j-1]+c[s3[i]][s4[j]];
                 if(k < a[i-1][j]+c[s3[i]][4])
                     k = a[i-1][j]+c[s3[i]][4];
                 if(k < a[i][j-1]+c[4][s4[j]])
                     k = a[i][j-1]+c[4][s4[j]];
                 a[i][j]=k;
             }
 
         cout << a[len1][len2] << endl;
 
        //for(int i=0; i<len1; ++i)
    }
}

HDU/HDOJ 1084 What Is Your Grade?

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1084

水题,就是用sort或qsort比较。

不过这里有一点要注意,在比较时间时,可以统一转换成按s来比较。

AC代码,写的很水很烂,自己都觉得晕了。。。

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef struct time{
    int h, m, s;
    int tot;
}time;
 
typedef struct stu{
    int p;
    time t;
    int id;
    int sco;
}stu;
 
stu ss[105], ss2[105];
int n;
 
bool cmp (stu e1, stu e2 )
{
    if(e1.p != e2.p)
        return e1.p > e2.p;
    else
        return e1.t.tot < e2.t.tot;
}
 
bool cmp2(stu e1, stu e2)
{
    return e1.id < e2.id;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //bool flag = 0;
 
    while(cin >> n && n != -1)
    {
        //if(flag == 1)
        //    cout << endl;
        //flag = 1;
        int c[6];  // 1, 2, 2, 4;
        memset(c, 0, sizeof(c));
        int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
        int cnt = 0;
        for(int i=0; i<n; ++i)
        {
            ss[i].id = i+1;
            scanf("%d", &ss[i].p);
            scanf("%d:%d:%d", &ss[i].t.h, &ss[i].t.m, &ss[i].t.s);
            ss[i].t.tot = ss[i].t.h*3600 + ss[i].t.m*60 + ss[i].t.s;
        }
        sort(ss, ss+n, cmp);
        for(int i=0; i<n; ++i)
        {
            //cout << ss[i].p << "    " << ss[i].t.h << " " << ss[i].t.m << " " << ss[i].t.s << endl;
            c[ss[i].p]++;
        }
        for(int i=0; i<n; ++i)
        {
            if(ss[i].p == 5)
                ss[i].sco = 100;
            else if(ss[i].p == 4)
            {
                ++c4;
                if(c4 <= c[4]/2)
                    ss[i].sco = 95;
                else
                    ss[i].sco = 90;
            }
            else if(ss[i].p == 3)
            {
                ++c3;
                if(c3 <= c[3]/2)
                    ss[i].sco = 85;
                else
                    ss[i].sco = 80;
            }
            else if(ss[i].p == 2)
            {
                ++c2;
                if(c2 <= c[2]/2)
                    ss[i].sco = 75;
                else
                    ss[i].sco = 70;
            }
            else if(ss[i].p == 1)
            {
                ++c1;
                if(c1 <= c[1]/2)
                    ss[i].sco = 65;
                else
                    ss[i].sco = 60;
            }
            else
                ss[i].sco = 50;
        }
        sort(ss, ss+n, cmp2);
        for(int i=0; i<n; ++i)
        {
            //cout << ss[i].p << "    " << ss[i].t.h << " " << ss[i].t.m << " " << ss[i].t.s << endl;
            //c[ss[i].p]++;
        }
        for(int i=0; i<n; ++i)
            cout << ss[i].sco << endl;
        cout << endl;
    }
}

HDU/HDOJ 1086 You can Solve a Geometry Problem too

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1086

判断两条直线是否相交,感觉这是一道非常不错的题,高中学的向量积,数量积都还给老师了(其实在高数上册最后也讲过),悲催啊~~~

这里有一篇非常给力的讲解:

http://dev.gameres.com/Program/Abstract/Geometry.htm

AC代码:

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
#include <iostream>  
using namespace std;  
 
typedef struct line 
{  
    double x1,y1,x2,y2;  
}line;  
 
int n;
line ln[105];
 
int mul(double a, double b, double c, double d)  
{  
    return a * d - b * c;  
}
 
bool judge(int i, int j)
{
    double a = mul(ln[i].x1-ln[j].x1, ln[i].y1-ln[j].y1, ln[j].x2-ln[j].x1, ln[j].y2-ln[j].y1);
    double b = mul(ln[i].x2-ln[j].x1, ln[i].y2-ln[j].y1, ln[j].x2-ln[j].x1, ln[j].y2-ln[j].y1);
    double c = a * b;
 
    double d = mul(ln[j].x1-ln[i].x1, ln[j].y1-ln[i].y1, ln[i].x2-ln[i].x1, ln[i].y2-ln[i].y1);
    double e = mul(ln[j].x2-ln[i].x1, ln[j].y2-ln[i].y1, ln[i].x2-ln[i].x1, ln[i].y2-ln[i].y1);
    double f = d * e;
 
    if(c <= 0 && f <= 0)
        return 1;
    else
        return 0;
}
 
 
int main()  
{  
    //freopen("input.txt", "r", stdin);  
    while(scanf("%d", &n) && n)  
    {  
        for(int i=1; i<=n; ++i)  
            scanf("%lf %lf %lf %lf", &ln[i].x1, &ln[i].y1, &ln[i].x2, &ln[i].y2);  
        int count=0;  
        for(int i=1; i<n; ++i)  
        {  
            for(int j=i+1; j<=n; ++j)  
                if(judge(i,j)) 
                    ++count;  
        }  
        cout << count << endl;  
    }  
    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
#include<iostream>
using namespace std;
 
double p[100][2],q[100][2];
 
// 判断点与直线的关系
double direction(double p[],double q[] ,double r[]){
    return ((r[0]-p[0])*(q[1]-p[1])-(r[1]-p[1])*(q[0]-p[0]));
}
 
// 判断是否在线段构成的矩形内
bool onsegment(double p[],double q[], double r[]){
    if(((r[0]-p[0])*(r[0]-q[0])<=0)&&((r[1]-p[1])*(r[1]-q[1])<=0))
        return true;
    else return false;
}
 
bool judge(int i, int j){
    double d1,d2,d3,d4;
    d1=direction(p[i],q[i],p[j]);
    d2=direction(p[i],q[i],q[j]);
    d3=direction(p[j],q[j],p[i]);
    d4=direction(p[j],q[j],q[i]);
    if((d1*d2<0)&&(d3*d4<0))
        return true;
    else if(d1==0&& onsegment(p[i],q[i],p[j])==1)
        return true;
    else if(d2==0&& onsegment(p[i],q[i],q[j])==1)
        return true;
    else if(d3==0&& onsegment(p[j],q[j],p[i])==1)
        return true;
    else if(d4==0&& onsegment(p[j],q[j],q[i])==1)
        return true;
    else return false;
}
 
int main(){
    int n,i,j,count;
    while(scanf("%d",&n)){
        if(n==0)    break;
        for(i=0;i<n;++i){
            scanf("%lf %lf %lf %lf",&p[i][0],&p[i][1],&q[i][0],&q[i][1]);
        }
        for(i=0,count=0;i<n;i++)
            for(j=i+1;j<n;j++)
                if(judge(i,j)==1)
                    ++count;
        printf("%d\n",count);
    }
    return 0;
}