binary search tree

数据结构汇总之 binary search tree

原文见 仓库

good good study, day day leetcode


BST的定义及性质

二叉搜索树(BST binary search tree):又叫二叉排序树或者二叉查找树,其满足以下性质

  • 非空左子树所有值小于根节点值
  • 非空右子树所有值大于根节点值
  • 左、右子树都是二叉搜索树


由上可以推出:

  • BST最小值一定在最端端点上,最大值一定在最端端点上
  • 通过二叉树的中序遍历,可以获得由小到大有序排列的序列




BST的基本操作

1、查找Find
1
2
3
4
5
6
7
8
9
struct TreeNode* Find(struct TreeNode* root,ElementType x) {
if (root==NULL) return NULL;
if (x < root->val)
root->left=Find(root->left,x);
else if (x > root->val)
root->right=Find(root->right,x);
else
return root;
}


2、查找最大/最小值find Max/find Min
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct TreeNode* findMin(struct TreeNode* root) {
if (root==NULL) return NULL;
while (root->left)
root=root->left;

return root;
}

struct TreeNode* findMax(struct TreeNode* root) {
if (root==NULL) return NULL;
while (root->right)
root=root->right;

return root;
}


3、插入Insert
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//这里使用递归插入,还是比较巧妙
struct TreeNode* Insert(struct TreeNode* root,ElementType x) {
if (root==NULL) {
struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val=x;
root->left=root->right=NULL;
}
else {
if (x < root->val){
root->left=Insert(root->left,x);
}
else if (x > root->val) {
root->right=Insert(root->right,x);
}
}

return root;
}


4、删除delete









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
struct TreeNode* findMin(struct TreeNode* root) {
if (root==NULL) return NULL;
while (root->left)
root=root->left;

return root;
}

struct TreeNode* delete(struct TreeNode* root,ElementType x) {
if (root==NULL) return NULL;
//左、右子树分别递归删除
else if (x < root->val) {
root->left=delete(root->left,x);
}
else if (x > root->val) {
root->right=delete(root->right,x);
}
else {
//找到要删除的点
//找到改点右子树的最小节点temp,并赋值给当前的root
//然后递归删除掉temp
if (root->left&&root->right) {
struct TreeNode* temp=findMin(root->right);
root->val=temp->val;
root->right=delete(root->right,temp->val);
}
else {
//只有右儿子、无子节点
//只有左儿子、无子节点
struct TreeNode* temp=root;
if (root->left==NULL)
root=root->right;
else if (root->right==NULL)
root=root->left;
free(temp);
}
}

return root;
}




BST题型归纳

以下是比较常见的题型,加粗的便是比较常考的了。

BST基本操作
BST应用

这些都比较难了。。

  • 包含重复值-3 [220 Contains Duplicate III]
  • 计算后面较小数字的个数 [315 Count of Smaller Numbers After Self]
  • 连续和在指定区间内 [327 Count of Range Sum]
  • 分离区间的数据流 [352 Data Stream as Disjoint Intervals]
  • 我的日历-2 [731 My Calendar II]
  • 我的日历-3 [732 My Calendar III]


-------------本文结束感谢您的阅读-------------