搜索二叉树

二叉搜索树

C++

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
160
161
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x7fffffff;
int cont = 0; 

struct BiNode
{
	int ls, rs, val, cnt, siz;
}tree[1000010];

int n,q,val;

void add(int x,int val)
{
	tree[x].siz++;// 首先，插入的这个结点的siz++
	// 如果已经有这个结点，就cnt++，因为搜索树中不能有重复结点
	if (val == tree[x].val)
	{
		tree[x].cnt++;
		return;
	}
	
	if (val < tree[x].val)
	{
        // 到最左边
		if (tree[x].ls == 0)
		{
            // 开辟新结点并赋值
			cont++;
			tree[cont].val = val;
			tree[cont].cnt = tree[cont].siz = 1;
			tree[x].ls = cont;
		}
		else
		{
			add(tree[x].ls, val);
		}
	}
	else
	{
		if (tree[x].rs == 0)
		{
			cont++;
			tree[cont].cnt = tree[cont].siz = 1;
			tree[cont].val = val;
			tree[x].rs = cont;
		}
		else
		{
			add(tree[x].rs, val);
		}
	}
}
// 找前驱
int queryfr(int x, int val, int ans)
{
    // 如果小于当前结点
	if (tree[x].val >= val)
	{
        // 找到最左边了，直接返回ans
		if (tree[x].ls == 0)
			return ans;
		else
            //不然就继续找
			queryfr(tree[x].ls, val, ans);
	}
	else
	{
		if (tree[x].rs == 0)
			return tree[x].val > val ? ans : tree[x].val;
		else
			return queryfr(tree[x].rs, val, tree[x].val);
		
	}
}
// 找后继
int queryne(int x, int val, int ans)
{
	if (tree[x].val <= val)
	{
		if (tree[x].rs == 0)
			return ans;
		else
			queryne(tree[x].rs, val, ans);
	}
	else
	{
		if (tree[x].ls == 0)
			return tree[x].val < ans ? tree[x].val : ans;
		else
			queryne(tree[x].ls, val, tree[x].val);
	}

}
// 找val的排位
int quertval(int x, int val)
{
    // 没找到就返回0，当找到最后还没有找到的时候，就会走到ls或rs==0，赋值给x，就会从这里退出
	if (x == 0) return 0;
	// 找到了就返回，当前这个结点的左子树的长度
	if (tree[x].val == val)
		return tree[tree[x].ls].siz;
    // 如果小于当前结点的值，往左
	if (tree[x].val > val)
		return quertval(tree[x].ls, val);
    // 往右的时候要先减掉左子树和自身的值
	else
		return quertval(tree[x].rs, val) + tree[tree[x].ls].siz + tree[x].cnt;
}
// 找排位为rk的值
int quertrk(int x, int rk)
{
    // rk索引越界
	if (x == 0)
		return INF;
	// 左子树大于rk，说明在左子树里面找
	if (tree[tree[x].ls].siz >= rk)
		return quertrk(tree[x].ls, rk);
    // 左子树+cnt大于rk，说明就是当前的val
	if (tree[tree[x].ls].siz + tree[x].cnt >= rk)
		return tree[x].val;
    // 否则在右子树，要先减掉左子树和cnt
	return quertrk(tree[x].rs, rk - tree[tree[x].ls].siz - tree[x].cnt);
}
int main()
{
	cin >> n;
	while (n--)
	{
		cin >> q >> val;
		switch (q)
		{
		case 1:
			cout << quertval(1, val) + 1 << endl;
			break;
		case 2:
			cout << quertrk(1, val) << endl;
			break;
		case 3:
			cout<<queryfr(1, val, -INF) << endl;
			break;
		case 4:
			cout << queryne(1, val, INF) << endl;
			break;
		case 5:
			//特判根节点
			if (cont == 0)
			{
				cont++;
				tree[cont].cnt = tree[cont].siz = 1;
				tree[cont].val = val;
			}
			else add(1, val);
			break;

		default:
			break;
		}
	}
}

这个小伙居然还用python写了一遍

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
INF = 0x7fffffff
cont = 0


class Node:
    def __init__(self,val=0,siz=0,cnt=0,ls=0,rs=0):
        self.val = val
        self.siz = siz
        self.cnt = cnt
        self.ls = ls
        self.rs = rs


# 神奇的方法
tree = [Node() for _ in range(100000)]


def add(x,v):
    global cont,tree
    tree[x].siz += 1
    if tree[x].val == v:
        tree[x].cnt += 1
        return

    if tree[x].val > v:
        if tree[x].ls != 0:
            add(tree[x].ls,v)
        else:
            cont += 1
            tree[cont].val = v
            tree[cont].siz = tree[cont].cnt = 1
            tree[x].ls = cont
    else:
        if tree[x].rs != 0:
            add(tree[x].rs,v)
        else:
            cont += 1
            tree[cont].val = v
            tree[cont].siz = tree[cont].cnt = 1
            tree[x].rs = cont


def queryfr(x,val,ans):
    global tree
    if tree[x].val >= val:
        if tree[x].ls == 0:
            return ans
        else:
            return queryfr(tree[x].ls,val,ans)
    else:
        if tree[x].rs == 0:
            if tree[x].val < val:
                return tree[x].val
            else:
                return ans
        if tree[x].cnt != 0:
            return queryfr(tree[x].rs,val,tree[x].val)
        else:
            return queryfr(tree[x],val,ans)

def queryne(x,val,ans):
    global tree
    if tree[x].val <= val:
        if tree[x].rs == 0:
            return ans
        else:
            return queryne(tree[x].rs,val,ans)
    else:
        if tree[x].ls == 0:
            if tree[x].val > val:
                return tree[x].val
            else:
                return ans
        # 这里有点多余
        if tree[x].cnt != 0:
            return queryne(tree[x].ls,val,tree[x].val)
        else:
            return queryne(tree[x].ls, val,ans)



def queryrk(x,rk):
    global tree
    if x == 0:
        return INF
    if tree[tree[x].ls].siz >= rk:
        return queryrk(tree[x].ls,rk)
    if tree[tree[x].ls].siz + tree[x].cnt >= rk:
        return tree[x].val
    return queryrk(tree[x].rs,rk - tree[tree[x].ls].siz-tree[x].cnt)

def queryval(x,val):
    global tree
    if x == 0:
        return 0
    if val == tree[x].val:
        return tree[tree[x].ls].siz
    if val < tree[x].val:
        return queryval(tree[x].ls,val)
    return queryval(tree[x].rs,val)+tree[tree[x].ls].siz+tree[x].cnt



n = int(input())
for i in range(n):
    q,v = [int(x) for x in input().split()]
    if q == 5:
        if cont == 0:
            cont += 1
            tree[cont].cnt = tree[cont].siz = 1
            tree[cont].val = v
        else:
            add(1,v)
    elif q == 1:
        print(queryval(1,v)+1)
    elif q == 2:
        print(queryrk(1,v))
    elif q == 3:
        print(queryfr(1,v,-INF))
    elif q == 4:
        print(queryne(1,v,INF))
algorithm
#Tree #study
搜索二叉树
https://brtulien.github.io/2023/08/07/搜索二叉树/
作者
Brtulien
发布于
2023年8月7日
更新于
2024年7月1日
许可协议