【树型查找】二叉排序树

一、定义

中序遍历有序的二叉树为二叉排序树（简称BST），又叫二叉查找树、二叉搜索树。

定义一个二叉树：

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;
1
2
3
4
5
6

支持的操作：插入、删除、查找

三个操作都是O(h)
（h是树的高度，因为这三种操作都是从树头往下走，每次都进入一个分支）

二、操作

1.插入

算法思路：
因为每次插入都必然是忘叶节点插入新节点，所以递归找到x待插入的位置
1.如果发现root为空，就将x插入到当前位置上
2.如果题目中没有保证x互不相同，就判断一下：如果x=当前root的值，直接return
3.如果x<当前root的值,就递归到左子树上插
4.如果x>当前root的值,就递归到右子树上插

代码实现：

void insert(TreeNode* &root, int x)//注意：需要加&引用符号，当既在函数内修改变量的值，又想在函数修改变量的值，就要加上引用符号
{
    /*
        递归找到x的待插入的位置
        1.如果发现当前根节点为空，就将x插入当前位置上
        2.如果题目中没有保证x互不相同，就判断一下：如果x=当前root，直接return
        3.如果x<当前root,就递归到左子树上插
        4.如果x>当前root,就递归到右子树上插
        
    */ 
    if (!root) root = new TreeNode(x);
    // 如果发现数值相同的话就判断一下;
    if (root->val == x) return;
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.删除

算法思路：
递归找到待删除的root：
1.如果树不存在（root为空），直接return
2.如果x<当前root的值,就递归到左子树上删
3.如果x>当前root的值,就递归到右子树上删
4.如果x=当前root的值，有以下四种情况：
①左右都为空（即是叶节点），则直接删除
②左为空，直接提右子树
③右为空，直接提左子树
④左右都不为空，找到左子树最右下方的结点，然后用它的值拿来覆盖root，然后删除这个左子树最右下方的结点
（把中序遍历中前驱的值覆盖到当前位置上，然后把前驱删掉，中序序列不变）

代码实现：

void remove(TreeNode* &root, int x)
{
    // 1.如果不存在直接return
    if (!root) return;
    // 递归找到待删除的root
    if (x < root->val) remove(root->left, x);//2.如果x<当前root的值,就递归到左子树上删
    else if (x > root->val) remove(root->right, x);//3.如果x>当前root的值,就递归到右子树上删
    else  //4.如果x=当前root的值，有以下四种情况：
    {
        // 四种情况
        // 1.左右都为空（即是叶节点），则直接删除
        // 2.左为空，直接提右子树
        // 3.右为空，直接提左子树
        // 4.左右都不为空，找到左子树最右下方的结点，然后用它的值拿来覆盖root，然后删除这个左子树最右下方的结点
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else
        {
            auto p = root->left;//找到root的左子树
            while (p->right) p = p->right;//找到左子树的最大值
            root->val = p->val;//将根节点前驱的值覆盖过来
            remove(root->left, p->val);//覆盖完之后去左子树中，删除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

3.查找

算法思路：
普通查找：
1.如果x<当前root的值,就递归到左子树上查找
2.如果x>当前root的值,就递归到右子树上查找
3.如果x=当前root的值，查找成功

代码实现：

// INF我定义为了2e9 可以定义为0x3f3f3f3f,感兴趣可以搜一下为什么要这样定义
const int INF = 2e9;

// 输出数值 x 的前驱(前驱定义为现有所有数中小于 x 的最大的数)。
int get_pre(TreeNode* root, int x)
{
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    else return max(root->val, get_pre(root->right, x));
}

// 输出数值 x 的后继(后继定义为现有所有数中大于 x 的最小的数)。
int get_suc(TreeNode* root, int x)
{
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    else return min(root->val, get_suc(root->left, x));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、例题

1.题目描述

2.AC代码

#include 
using namespace std;
const int INF = 2e9;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;


void insert(TreeNode* &root, int x)//注意：需要加&引用符号，当既在函数内修改变量的值，又想在函数修改变量的值，就要加上引用符号
{
    /*
        因为每次插入都必然是忘叶节点插入新节点，所以递归找到x待插入的位置:
        1.如果发现当前根节点为空，就将x插入当前位置上
        2.如果题目中没有保证x互不相同，就判断一下：如果x=当前root，直接return
        3.如果x<当前root,就递归到左子树上插
        4.如果x>当前root,就递归到右子树上插

    */ 
    if (!root) root = new TreeNode(x);
    // 如果发现数值相同的话就判断一下;
    if (root->val == x) return;
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}

void remove(TreeNode* &root, int x)
{
    // 1.如果不存在直接return
    if (!root) return;
    // 递归找到待删除的root
    if (x < root->val) remove(root->left, x);//2.如果x<当前root的值,就递归到左子树上删
    else if (x > root->val) remove(root->right, x);//3.如果x>当前root的值,就递归到右子树上删
    else  //4.如果x=当前root的值，有以下四种情况：
    {
        /*四种情况
        1.左右都为空（即是叶节点），则直接删除
        2.左为空，直接提右子树
        3.右为空，直接提左子树
        4.左右都不为空，找到左子树最右下方的结点，然后用它的值拿来覆盖root，然后删除这个左子树最右下方的结点
        （把中序遍历中前驱的值覆盖到当前位置上，然后把前驱删掉，中序序列不变）
        */
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else
        {
            auto p = root->left;//找到root的左子树
            while (p->right) p = p->right;//找到左子树的最大值
            root->val = p->val;//将根节点前驱的值覆盖过来
            remove(root->left, p->val);//覆盖完之后去左子树中，删除root的前驱
        }
    }
}

// 输出数值 x 的前驱(前驱定义为现有所有数中小于 x 的最大的数)。
int get_pre(TreeNode* root, int x)
{
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    else return max(root->val, get_pre(root->right, x));
}

// 输出数值 x 的后继(后继定义为现有所有数中大于 x 的最小的数)。
int get_suc(TreeNode* root, int x)
{
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    else return min(root->val, get_suc(root->left, x));
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << 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
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