二叉搜索树和平衡树

数据结构
字数统计: 1.7k   |   阅读时长≈ 8 分钟

二叉搜索树基本介绍

给定一棵二叉树，树上的每一个节点带有一个数值，称为节点的关键值$val$。

对于树上的每一个节点：

1、该节点的关键码不小于它的左子树任意节点的关键码

2、该节点的关键码不大于它的右子树任意节点的关键码

这样的树就叫做二叉查找树（二叉排序树），即BST。

显然二叉查找树的中序遍历就是一个按照关键值递增的节点序列。

实现方式

1、建树

我们可以建立两个初始节点，一个点的值为$INF$，另一个为$-INF$。

（书上说可以避免越界，减少边界的特殊情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int INF = 1e9, N = 1e6;
int tot, root;
struct {
	int l, r, val;
}a[N];

int New(int val) {
	a[++tot].val = val;
    return tot;
}

void build() {
	New(-INF), New(INF), root = 1, a[1].r = 2;
}

2、搜索

从根节点开始搜索，分为三种情况

1、若val等于p的关键值，表示已经找到，直接退出

2、若val大于p的关键值

1、若p的右节点为空，说明不存在val

2、若p的右节点不为空，在右子树中进行递归查找

3、若val小于p的关键值

1、若p的左节点为空，说明不存在val

2、若p的左节点不为空，在左子树中进行递归查找

1
2
3
4
5
int search(int p,int val) {
	if (p == 0)	return 0;
	if (val == a[p].val)	return 1;
	return val > a[p].val ? search(a[p].r, val) : search(a[p].l, val);
}

3、插入

当我们发现走向p节点的子节点为空时，说明不存在，直接建立新节点。

1
2
3
4
5
6
7
8
void insert(int &p,int val) {
	if (p == 0) {
		p = New(val);//这里是引用，其父节点l，r同时也会被更新
		return ;
	}
	if (val == a[p].val)	return ;
	val > a[p].val ? insert(a[p].r, val) : insert(a[p].l, val);
}

4、求前驱后继

前驱就是在BST中关键值小于val的情况下，关键值最大的节点，而后继就是在BST中关键值大于val的情况下，关键值最小的节点。

这里以后继为例。

分为三种情况。

1、没有找到val,说明val的后继已经在所遍历的节点中，ans即为所求

2、找到了关键值为val的节点p,但是该节点没有右子树，结果和1一样

3、找到了关键值为val的节点p，且有右子树，则从它的右子节点开始遍历，从左走，就找到了val的后继

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int GetNext(int val) {
	int ans = 2;//a[p].val为INF
	int p = root;
	while (p) {
		if (a[p].val == val) {
			if (a[p].r) {
				p = a[p].r;
				while (p) p = a[p].l;
				ans = p;
			}
		}
		if (a[p].val > val && a[p].val < a[ans].val)	ans = p;//不断更新
		p = a[p].val > val ? a[p].l : a[p].r;
	}
}

4、删除

我们先查找到关键值为val的节点p。

若p的子节点数小于二，那么直接删除P，令p的子节点代替p的位置，与p的父节点相连。

若p既有左子树又有右子树，那么就先求出val的后继节点next,然后直接删除next(没有左子树)，并令next的右子树代替next的位置，最后让next节点代替p，删除p即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void remove(int &p,int val) {
	if (!p)	return;
	if (val == a[p].val) {
		if (!a[p].l)	p = a[p].r;//左子树为空
		else if (!a[p].r)	p = a[p].l;//右子树为空
		else {
			int next = a[p].r;
			while (a[next].l)	next = a[p].l;//找到后缀
			remove(a[p].r, a[next].val);//删除后缀
			a[next].l = a[p].l, a[next].r = a[p].r, p = next;//用后缀来替代p
		}
	}
	val > a[p].val ? remove(a[p].r, val) : remove(a[p].l, val);
}

因为数据的随机性，很有可能BST会变成链，那么时间复杂度又会从$O(logN)$变成$O(n)$。

所以出现了平衡树。

平衡树

（平衡树还不是很会啊。。

这边先放一下模板吧

到时候会了再补上。

例题

普通平衡树

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
//ycx的代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 1e8;

int n;
struct Node
{
    int l, r;
    int key, val;
    int cnt, size;
}tr[N];

int root, idx;

void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

int get_node(int key)
{
    tr[ ++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int &p)    // 右旋
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int &p)    // 左旋
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    //之前一直对这个东西保有疑惑，后面发现必须要配合insert(&p,val)和remove(&p，key)来理解
    pushup(tr[p].l), pushup(p);
}

void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);

    if (tr[1].val < tr[2].val) zag(root);
}


void insert(int &p, int key)
{
    if (!p) p = get_node(key);
    else if (tr[p].key == key) tr[p].cnt ++ ;
    else if (tr[p].key > key)
    {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

void remove(int &p, int key)
{
    if (!p) return;
    if (tr[p].key == key)
    {
        if (tr[p].cnt > 1) tr[p].cnt -- ;
        else if (tr[p].l || tr[p].r)
        {
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else
            {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if (tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);

    pushup(p);
}

int get_rank_by_key(int p, int key)    // 通过数值找排名
{
    if (!p) return 0;   // 本题中不会发生此情况
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank)   // 通过排名找数值
{
    if (!p) return INF;     // 本题中不会发生此情况
    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key)   // 找到严格小于key的最大数
{
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key)    // 找到严格大于key的最小数
{
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();

    scanf("%d", &n);
    while (n -- )
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove(root, x);
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));
        else if (opt == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }

    return 0;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信