Si_Yue小屋
0%

BST

发表于 分类于

BST(Binary Search Tree)，叫做二叉搜索树，是一种未平衡的数据结构。

维护的节点信息有：siz,cnt,val,支持查询排名和第k大元素的值

代码如下：

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
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+2;
int val[MAXN],cnt[MAXN],siz[MAXN],lc[MAXN],rc[MAXN],n;

void print(int& o){
    if(!o)return;
    //中序遍历，就是以从小到大输出
    print(lc[o]);
    for(int i=1;i<=cnt[o];i++)cout<<val[o]<<endl;
    print(rc[o]);
}

int findmin(int o){
    if(!lc[o])return o;
    return findmin(lc[o]);
}

int findmax(int o){
    if(!rc[o])return o;
    return findmax(rc[o]);
}

int deletemin(int& o){
    if(!lc[o]){
        //用右儿子替代该节点
        int u=o;
        o=rc[o];
        return u;
    }else{
        int u=deletemin(lc[o]);
        //每个遍历过的节点的大小减去最小值节点的大小
        siz[o]-=cnt[u];
        return u;
    }
}

void del(int& o,int v){
    //访问过的节点siz--
    siz[o]--;
    if(val[o]==v){
        if(cnt[o]>1){
            //若cnt大于1直接cnt--
            cnt[o]--;
            return;
        }
        if(lc[o]&&rc[o]){
            //若左右儿子都在就以右儿子下的最小值节点替代该节点
            o=deletemin(rc[o]);
        }else{
            //若左右儿子有一个不再在就以另一个替代，都不在就以空替代
            o=lc[o]+rc[o];
        }
        return;
    }
    if(val[o]>v)del(lc[o],v);
    if(val[o]<v)del(rc[o],v);
}

int queryrnk(int o,int v){
    if(val[o]==v)return siz[lc[o]]+1;
    if(val[o]>v)return queryrnk(lc[o],v);
    if(val[o]<v)return queryrnk(rc[o],v)+siz[lc[o]]+cnt[o]; 
    return -1;
}

int querykth(int o,int k){
    if(siz[lc[o]]>=k)return querykth(lc[o],k);
    else if(siz[lc[o]]+cnt[o]<k)return querykth(rc[o],k-siz[lc[o]]-cnt[o]);
    return val[o]; 
}

void insert(int& o,int v){
    if(!o){
        //访问到空的话创造节点
        val[o=++n]=v;
        cnt[n]=siz[n]=1;
        lc[o]=rc[o]=0;
        return;
    }
    //遍历过的节点siz++
    siz[o]++;
    if(val[o]==v){
        //访问不为空则cnt++
        cnt[o]++;
        return;
    }
    if(val[o]>v)insert(lc[o],v);
    if(val[o]<v)insert(rc[o],v);
}


int main(){
    int root=1;
    //test
    for(int i=1;i<=5;i++){
        insert(root,114+i);
    }
    print(root);
    del(root,116);
    print(root);
    cout<<queryrnk(root,117)<<endl;
    cout<<querykth(root,4)<<endl;
    return 0;
}

记住BST基础的功能有print,findmin,findmax,deletemin,del,insert,queryrnk,querykth,维护了节点的大小siz和次数cnt和数据val。

动态过程如BST动画所示