浅谈BST

前言

最近不顺心的事情有点多，再加上赶ptaL2 的题单，很久没做知识总结了 ，现在pta的题目告一段落，参考了某大佬 （某卷王） 总结的知识点，鸣谢大佬！总结一下BST问题的知识点，供以后参考。
封面：
在这里插入图片描述

站在巨人 （卷王） 的肩上，才能看 （卷） 的更远

二叉搜索树的性质

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点

  • 其左子树中所有结点的键值小于该结点的键值；
  • 其右子树中所有结点的键值大于等于该结点的键值；
  • 其左右子树都是二叉搜索树。

乍一看，其实感觉和二叉堆很像，不过二叉堆左右儿子之间没有可比性，因为二叉堆是根据与父亲节点大小关系建堆的，兄弟节点似乎无法比较，所以同一个序列，以不同顺序输入的生成的二叉堆序列也自然不同。
二叉搜索树也有类似的性质，但是二叉搜索树输入的节点不会发生位置交替，这和二叉堆边插入边排序不同，所以，同一组数字不同顺序输入二叉搜索树也会导致二叉搜索树结构不同。假如输入的数字过于玄学，会导致树的左右子树不平衡，如果将两个子树平衡，就变成了平衡树(Treap)

二叉搜索树的操作

必要的初始化
1
2
3
4
5
6
7
8
9
10
11
#define maxn 100000
#define INF -1
int BST[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	for (int i = 0; i < maxn; i++)
		BST[i] = INF;
}

建树
1
2
3
4
5
6
7
8
9
10
11
12
void build(int root, int x)
{
	if (BST[root] == INF)
	{
		BST[root] = x;
		return;
	}
	if (BST[root] >= x)		//说明该节点应该在其左边
		build(root * 2, x); //左儿子比父亲小，右儿子更大
	else
		build(root * 2 + 1, x); //右儿子比父亲大，往右边放
}
前序遍历
1
2
3
4
5
6
7
8
void pre_order(int root)
{
	if (BST[root] == INF)
		return;
	cout << BST[root] << " ";
	pre_order(root * 2);
	pre_order(root * 2 + 1);
}
中序遍历

中序遍历其实就是序列从小到大排序

1
2
3
4
5
6
7
8
void in_order(int root)
{
	if (BST[root] == INF)
		return;
	in_order(root * 2);
	cout << BST[root] << " ";
	in_order(root * 2 + 1);
}
后序遍历
1
2
3
4
5
6
7
8
void post_order(int root)
{
	if (BST[root] == INF)
		return;
	post_order(root * 2);
	post_order(root * 2 + 1);
	cout << BST[root] << " ";
}
找最大
1
2
3
4
5
6
7
8
int get_max(int root) //一直往右走
{
	if (BST[root * 2 + 1] == INF)
		return BST[root];
	else
		return get_max(root * 2 + 1);
}

找最小
1
2
3
4
5
6
7
8
int get_min(int root) //一直往左走
{
	if (BST[root * 2] == INF)
		return BST[root];
	else
		return get_min(root * 2);
}

删除节点
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
void modify(int root, int x) //删除操作
{
	if (x > BST[root]) //往右找
		modify(root * 2 + 1, x);
	else if (x < BST[root]) //往左找
		modify(root * 2, x);
	else //找到了，开始修改
	{
		if (BST[2 * root] == INF && BST[root * 2 + 1] == INF)
		{
			BST[root] = INF; //没有儿子，直接封杀
		}
		else if (BST[2 * root] == INF && BST[root * 2 + 1] != INF) //左子树存在，右子树无
		{
			BST[root] = BST[root * 2 + 1];
			modify(root * 2 + 1, BST[root * 2 + 1]);
		}
		else if (BST[2 * root] != INF && BST[root * 2 + 1] == INF) //左子树空，右子树存在
		{
			BST[root] = BST[root * 2];
			modify(root * 2, BST[root * 2]);
		}
		else if (BST[root * 2] != INF && BST[root * 2 + 1] != INF)
		{
			//有两种修改方式！
			//第一种是修改用后驱节点(右子树最小节点更换)
			//第二种是用前驱节点修改(左子树最大节点更换)
			//这里演示前者
			int post_point = get_min(root * 2 + 1);
			BST[root] = post_point;
			modify(root * 2 + 1, post_point);
		}
	}
}

汇总代码，实弹演习

1
2
3
样例
7
8 10 11 8 6 7 5
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
#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
#define INF -1

int BST[maxn];
void build(int root, int x)
{
	if (BST[root] == INF)
	{
		BST[root] = x;
		return;
	}
	if (BST[root] >= x)		//说明该节点应该在其左边
		build(root * 2, x); //左儿子比父亲小，右儿子更大
	else
		build(root * 2 + 1, x); //右儿子比父亲大，往右边放
}
void pre_order(int root)
{
	if (BST[root] == INF)
		return;
	cout << BST[root] << " ";
	pre_order(root * 2);
	pre_order(root * 2 + 1);
}
void in_order(int root)
{
	if (BST[root] == INF)
		return;
	in_order(root * 2);
	cout << BST[root] << " ";
	in_order(root * 2 + 1);
}
void post_order(int root)
{
	if (BST[root] == INF)
		return;
	post_order(root * 2);
	post_order(root * 2 + 1);
	cout << BST[root] << " ";
}
void floor_order(int root)
{
	queue<int> q;
	q.push(root);
	while (q.empty() == false)
	{
		int fa = q.front();
		cout << BST[fa] << " ";
		q.pop();
		if (BST[fa * 2] != INF)
			q.push(fa * 2);
		if (BST[fa * 2 + 1] != INF)
			q.push(fa * 2 + 1);
	}
}
int get_min(int root) //一直往左走
{
	if (BST[root * 2] == INF)
		return BST[root];
	else
		return get_min(root * 2);
}
int get_max(int root) //一直往右走
{
	if (BST[root * 2 + 1] == INF)
		return BST[root];
	else
		return get_max(root * 2 + 1);
}
int search(int now, int x) //查找某一个特殊的元素
{
	if (x > BST[now])
		return search(now * 2 + 1, x);
	else if (x < BST[now])
		return search(now * 2, x);
	else
		return now;
}
void modify(int root, int x) //删除操作
{
	if (x > BST[root]) //往右找
		modify(root * 2 + 1, x);
	else if (x < BST[root]) //往左找
		modify(root * 2, x);
	else //找到了，开始修改
	{
		if (BST[2 * root] == INF && BST[root * 2 + 1] == INF)
		{
			BST[root] = INF; //没有儿子，直接封杀
		}
		else if (BST[2 * root] == INF && BST[root * 2 + 1] != INF) //左子树存在，右子树无
		{
			BST[root] = BST[root * 2 + 1];
			modify(root * 2 + 1, BST[root * 2 + 1]);
		}
		else if (BST[2 * root] != INF && BST[root * 2 + 1] == INF) //左子树空，右子树存在
		{
			BST[root] = BST[root * 2];
			modify(root * 2, BST[root * 2]);
		}
		else if (BST[root * 2] != INF && BST[root * 2 + 1] != INF)
		{
			//有两种修改方式！
			//第一种是修改用后驱节点(右子树最小节点更换)
			//第二种是用前驱节点修改(左子树最大节点更换)
			//这里演示前者
			int post_point = get_min(root * 2 + 1);
			BST[root] = post_point;
			modify(root * 2 + 1, post_point);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	for (int i = 0; i < maxn; i++)
		BST[i] = -1;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int remp;
		cin >> remp;
		build(1, remp);
	}
	pre_order(1);
	cout << endl;
	post_order(1);
	cout << endl;
	in_order(1);
	cout << endl;
	cout << get_max(1) << endl;
	cout << get_min(1) << endl;
	modify(1, 8);
	in_order(1);
	cout << endl;
	return 0;
}

运行结果
在这里插入图片描述

插一道题

在这里插入图片描述
这道题我是参考LP大佬的解法，鸣谢大佬！解法很巧妙，我们看题，它题目告诉我们它输入的序列有可能是正常的二叉搜索树，也可能是镜像的，那咋办捏？
判断两遍就可以了！先用当正常的遍历一下，试试水，如果成了就直接pass，不成了的话就用镜像的方式遍历一次
那么，我们怎么判断一个遍历是不是一个二叉搜索树捏？
以正常的为例子！
看图！

在这里插入图片描述
字有点丑不好意思我的锅
它生成的前序遍历应该是：
在这里插入图片描述
你会发现：对一段前序遍历，第一个元素是根节点，蓝色箭头之前到根节点都是小于根节点的！而绿色箭头都是大于根节点的！
而这两个箭头指的也是根节点的左右子树！
所以直接按这个规律进行判断！判断成功，就判断它的子树是否满足！

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
vector<int> ans;
int pre[maxn];
void judge1(int start, int end) //判断是否是正序
{								// start是根节点
	if (start > end)
		return;
	int node1 = start + 1;
	int node2 = end;
	while (node1 <= end && pre[node1] < pre[start])
		node1++; //从前往后寻找比根节点小的最后一个值
	while (node2 > start && pre[node2] >= pre[start])
		node2--; //从后往前寻找比根节点大的最后一个值

	node1--; //多加了
	node2++; //多减了
	// cout<<node1<<" "<<node2<<endl;
	if (node2 != node1 + 1) //只有两个指针中间只差一个(根节点)
		return;
	judge1(start + 1, node1);  //验证左子树
	judge1(node2, end);		   //查右子树
	ans.push_back(pre[start]); //后序遍历，最后放入
}
void judge2(int start, int end) //判断是否是镜像
{
	if (start > end)
		return;
	int node1 = start + 1;
	int node2 = end;
	while (node1 <= end && pre[node1] >= pre[start])
		node1++;
	while (node2 >= start && pre[node2] < pre[start])
		node2--;

	node1--;
	node2++;
	if (node2 != node1 + 1)
		return;
	judge2(start + 1, node1);
	judge2(node2, end);
	ans.push_back(pre[start]);
}
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 1; i <= num; i++)
	{
		scanf("%d", &pre[i]);
	}
	judge1(1, num);		   //先正序构造一下，试一下水
	if (ans.size() != num) //试水失败，说明可能是镜像，再试一次水
	{
		ans.clear();
		judge2(1, num);
	}
	if (ans.size() == num)
	{
		printf("YES\n");
		for (int i = 0; i < num; i++)
		{
			printf("%d", ans[i]);
			if (i != num - 1)
				printf(" ");
		}
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}