平衡树

Splay树

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
162
163
164
165
#include<bits/stdc++.h>
using namespace std;
int n, p, val;
const int N = 1000010, INF = 0x7fffffff;

struct Node
{
	int s[2];
	int p;
	int v;
	int cnt;
	int siz;
	void init(int p1, int v1)
	{
		cnt = siz = 1;
		p = p1, v = v1;
	}
}tree[N];
int root;
int idx;
// 更新树的大小
void pushup(int x)
{
	tree[x].siz = tree[tree[x].s[0]].siz + tree[tree[x].s[1]].siz + tree[x].cnt;
}
// 旋转 旋转不仅使得x转到y处，x的其中一个儿子也要给y
void rotate(int x)
{
    // 先找到x的父节点y和y的父节点z，k判断x是否为y的右儿子 假设x为y的右儿子 k为1
	int y = tree[x].p, z = tree[y].p;
	int k = tree[y].s[1] == x;
	// 先转动使 y的右儿子处放上x的左儿子 然后让x的左儿子的父节点为y
	tree[y].s[k] = tree[x].s[k ^ 1];
	tree[tree[x].s[k ^ 1]].p = y;
	// 然后使x的右儿子为y，y的父亲为x
	tree[x].s[k ^ 1] = y;
	tree[y].p = x;
	// 如果z的右儿子为y 那么z的右儿子为x （x替代y） 然后x的父亲为z
	tree[z].s[tree[z].s[1] == y] = x;
	tree[x].p = z;
	//记得更新节点
	pushup(y), pushup(x);
}
// splay 伸展结点，使x为k的儿子  k为0的时候使x为根
void splay(int x, int k)
{
	while (tree[x].p != k)
	{
		int y = tree[x].p, z = tree[y].p;
        // 当x的祖父结点不为k的时候 旋转
		if (z != k)
            // y的左儿子为x 并且z的左儿子为y 也就是直线型 转动y（1^1=0） 折线型转动x
			(tree[y].s[0] == x) ^ (tree[z].s[0] == y) ? rotate(x) : rotate(y);
        // 再转一次（双旋
		rotate(x);
	}
    // k为0的时候 让x为根
	if (k == 0)root = x;
}
// 查找v并让v为根
void find(int v)
{
	int x = root;
	while (tree[x].s[v > tree[x].v] && v != tree[x].v)
		x = tree[x].s[v > tree[x].v];
	splay(x, 0);
}
// 找前驱 先找到v 然后如果根的值小于v，直接返回x，因为比根大，不可能有前驱了（前驱是比）
int get_pre(int v)
{
	find(v);
	int x = root;
	if (tree[x].v < v)return x;
	// 根节点的左子树的最大结点就是前驱
	x = tree[x].s[0];
	while (tree[x].s[1]) x = tree[x].s[1];
	return x;
}
// 找后继 同理
int get_suc(int v)
{
	find(v);
	int x = root;
	if (tree[x].v > v)return x;

	x = tree[x].s[1];
	while (tree[x].s[0])x = tree[x].s[0];
	return x;
}
// 删除 并不是真的结点删除
void del(int v)
{
    // 先找前驱和后继
	int pre = get_pre(v);
	int suc = get_suc(v);
	// 转动前驱到根，转动后继为前驱的儿子，就是逻辑上的删除了该结点（此时待删除结点为后继的左儿子）
	splay(pre, 0), splay(suc, pre);
    // 后继的左儿子设为del（即待删除的点）
	int del = tree[suc].s[0];
	if (tree[del].cnt > 1)// 如果待删点不止一个，只删除一个并把他放回到根结点
		tree[del].cnt--, splay(del, 0);
	else
        // 后继的左儿子为0 即删除了待删除结点
		tree[suc].s[0] = 0, splay(suc, 0);
}

int get_rank(int v)
{
	find(v);
	return tree[tree[root].s[0]].siz;
}

int get_val(int k)
{
	int x = root;
	while (1)
	{
		int y = tree[x].s[0];
		if (tree[y].siz + tree[x].cnt < k)
		{
			k -= tree[y].siz + tree[x].cnt;
			x = tree[x].s[1];
		}
		else
		{
			if (tree[y].siz >= k)x = tree[x].s[0];
			else break;
		}
	}
	splay(x, 0);
	return tree[x].v;
}
// 插入结点
void insert(int v)
{
	int x = root, p = 0;
	while (x && tree[x].v != v)
		p = x, x = tree[x].s[v > tree[x].v];
	if (x) tree[x].cnt++;
	else
	{
		x = ++idx;
		tree[p].s[v > tree[p].v] = x;
		tree[x].init(p, v);
	}
    // 转动新插入的结点为根
	splay(x, 0);
}

int main()
{
    // 注意先插入哨兵
	insert(-INF), insert(INF);
	cin >> n;
	while (n--)
	{
		cin >> p >> val;
		if (p == 1)insert(val);
		else if (p == 2)del(val);
		else if (p == 3)cout << get_rank(val) << endl;
		else if (p == 4)cout << get_val(val + 1) << endl;
		else if (p == 5)cout << tree[get_pre(val)].v << endl;
		else if (p == 6)cout << tree[get_suc(val)].v << endl;
	}
}

rotate

splay

flag 写个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
#include<bits/stdc++.h>
using namespace std;
int n;
int idx = 0, root;
const int INF = 0x7fffffff, N = 1000010;

struct Node
{
	int v, s[2], cnt, siz, p;
	void init(int p1, int v1)
	{
		v = v1, p = p1;
		cnt = siz = 1;
	}
}tree[N];

void pushup(int x)
{
	tree[x].siz = tree[tree[x].s[0]].siz + tree[tree[x].s[1]].siz + tree[x].cnt;
}

void rotate(int x)
{
	int y = tree[x].p, z = tree[y].p;
	int k = (tree[y].s[1] == x);

	tree[y].s[k] = tree[x].s[k ^ 1];
	tree[tree[x].s[k ^ 1]].p = y;

	tree[x].s[k ^ 1] = y;
	tree[y].p = x;

	tree[z].s[tree[z].s[1] == y] = x;
	tree[x].p = z;

	pushup(y), pushup(x);
}

void splay(int x, int k)
{
	while (tree[x].p != k)
	{
		int y = tree[x].p, z = tree[y].p;
		if (z != k)
			(tree[y].s[0] == x) ^ (tree[z].s[0] == y) ? rotate(x) : rotate(y);
		rotate(x);
	}
	if (k == 0)root = x;
}

void insert(int v)
{
	int x = root, p = 0;
	while (x && v != tree[x].v)
		p = x, x = tree[x].s[v > tree[x].v];

	if (x) tree[x].cnt++;
	else
	{
		x = ++idx;
		tree[p].s[v > tree[p].v] = x;
		tree[x].init(p, v);
	}
	splay(x, 0);
}

void find(int v)
{
	int x = root;
	while (tree[x].s[v > tree[x].v] && v != tree[x].v)
		x = tree[x].s[v > tree[x].v];
	splay(x, 0);
}
int get_pre(int v)
{
	find(v);
	int x = root;
	if (tree[x].v < v)return x;
	x = tree[x].s[0];
	while (tree[x].s[1])x = tree[x].s[1];

	return x;
}

int get_suc(int v)
{
	find(v);
	int x = root;
	if (tree[x].v > v)return x;
	x = tree[x].s[1];
	while (tree[x].s[0])x = tree[x].s[0];

	return x;
}

int search(int v)
{
	find(v);
	if (tree[root].cnt > 1)return 0;
	int pre = get_pre(v), suc = get_suc(v);

	int a = tree[pre].v, b = tree[suc].v;
	return fabs(a - v) < fabs(b - v) ? fabs(a - v) : fabs(b - v);
}

int main()
{
	cin >> n;
	int x;
	int ret = 0;
	insert(INF), insert(-INF);
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		insert(x);
		if (i != 0)
			ret += search(x);
		else ret += x;
	}
	cout << ret << endl;
}

python版

几个需要注意的地方

  • Node的siz和cnt需要设置为0 而不是1 在申请结点之后设置为1
  • idx需要自增（C++转python的时候 由于++idx并不是放在单独的一句，写的时候容易漏掉
  • idx自增之后x = idx即可
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
class Node:
    def __init__(self, key):
        self.s = [0, 0] # son
        self.p = 0 # parent
        self.v = key # val
        self.cnt = 0
        self.siz = 0

class SplayTree:
    def __init__(self):
        self.N = 100010
        self.INF = 0x7fffffff
        self.tree = [Node(0) for _ in range(self.N)]
        self.root = 0
        self.idx = 0

    # 更新树的大小
    def pushup(self, x):
        self.tree[x].siz = self.tree[self.tree[x].s[0]].siz + self.tree[self.tree[x].s[1]].siz + self.tree[x].cnt

    """旋转操作 
    首先得到x的父节点y和y的父节点z，用k来表示左旋和右旋（如果x在y的左子树右旋，x在y的右子树左旋）
    以右旋为例 k为0
    首先让y的左子树放上x的右子树 同时x的右子树的父亲设置为y
    然后让x的右子树放上y 同时y的父亲设为x
    最后让z的右子树放上x 同时x的父亲设为z
    
    更新x y结点树的大小
    """
    def rotate(self, x):
        y = self.tree[x].p
        z = self.tree[y].p
        k = self.tree[y].s[1] == x

        self.tree[y].s[k] = self.tree[x].s[k ^ 1]
        self.tree[self.tree[x].s[k ^ 1]].p = y

        self.tree[x].s[k ^ 1] = y
        self.tree[y].p = x

        self.tree[z].s[self.tree[z].s[1] == y] = x
        self.tree[x].p = z

        self.pushup(y)
        self.pushup(x)
    """
    splay 使x为k的儿子 有三种情况 
    k是根 做单旋  
    k不是根 直线型 做双旋 
    k不是根 折线形 做双旋
    
    先不断向上找x的父节点 当不为k时继续循环：取出父节点y和祖先结点z 如果z不是x的祖先就旋转 
    当为直线型的时候（用^判断）转x  折线形转y   最后还要再转一下x 双旋（y是根的时候只会转一次x）
    
    如果k为0 表示k为根节点 要设置x为根
    """
    def splay(self, x, k):
        while self.tree[x].p != k:
            y = self.tree[x].p
            z = self.tree[y].p
            if z != k:
                if (self.tree[y].s[0] == x) ^ (self.tree[z].s[0] == y):
                    self.rotate(x)
                else:
                    self.rotate(y)
            self.rotate(x)

        if k == 0:
            self.root = x

    # 树的查找 找到之后要把x设为根（splay）
    def find(self, v):
        x = self.root
        while self.tree[x].s[v > self.tree[x].v] and v != self.tree[x].v:
            x = self.tree[x].s[v > self.tree[x].v]
        self.splay(x, 0)

    """
    找前驱 由于find是找到v且当v不存在时找到的是最接近v的值并将其设置为根
    当该结点小于v的时候直接返回 否则返回他的左子树的最右边的值
    """
    def get_pre(self, v):
        self.find(v)
        x = self.root
        if self.tree[x].v < v:
            return x
        x = self.tree[x].s[0]
        while self.tree[x].s[1]:
            x = self.tree[x].s[1]
        return x

    def get_suc(self, v):
        self.find(v)
        x = self.root
        if self.tree[x].v > v:
            return x
        x = self.tree[x].s[1]
        while self.tree[x].s[0]:
            x = self.tree[x].s[0]
        return x

    """
    删除结点，并非真的删除，而是让他访问不到
    先取出v的前驱和后继结点 并splay
    设删除结点为del_node 如果出现次数大于1 就减一并splay del_node 否则splay 后继结点
    """
    def delete(self, v):
        pre = self.get_pre(v)
        suc = self.get_suc(v)
        self.splay(pre, 0)
        self.splay(suc, pre)
        del_node = self.tree[suc].s[0]
        if self.tree[del_node].cnt > 1:
            self.tree[del_node].cnt -= 1
            self.splay(del_node, 0)
        else:
            self.tree[suc].s[0] = 0
            self.splay(suc, 0)

    # v的排位即v为根的时候v的左子树大小
    def get_rank(self, v):
        self.find(v)
        return self.tree[self.tree[self.root].s[0]].siz

    # k位的值 不断找到x的左子树 如果左子树的siz加x的cnt大于k 就往左子树走 否则就让k减去他们俩的和并往右子树走
    def get_val(self, k):
        x = self.root
        while True:
            y = self.tree[x].s[0]
            if self.tree[y].siz + self.tree[x].cnt < k:
                k -= self.tree[y].siz + self.tree[x].cnt
                x = self.tree[x].s[1]
            else:
                if self.tree[y].siz >= k:
                    x = self.tree[x].s[0]
                else:
                    break
        self.splay(x,0)
        return self.tree[x].v

    # 插入操作 先取出根节点 父节点为0 不断向下递归找到x的插入位置  找到之后 如果该结点已经存在 就让cnt+1 否则创建新节点（idx+1 p的儿子为x 初始化x
    def insert(self, v):
        x = self.root
        p = 0
        while x and self.tree[x].v != v:
            p = x
            x = self.tree[x].s[v > self.tree[x].v]
        if x:
            self.tree[x].cnt += 1
        else:
            # 注意 这里的idx要先++
            self.idx += 1
            x = self.idx
            self.tree[p].s[v > self.tree[p].v] = x
            self.tree[x].p = p
            self.tree[x].v = v
            self.tree[x].cnt = 1
            self.tree[x].siz = 1
        self.splay(x, 0)



def main():
    st = SplayTree()
    st.insert(-st.INF)
    st.insert(st.INF)
    n = int(input())
    for _ in range(n):
        p, val = map(int, input().split())
        if p == 1:
            st.insert(val)
        elif p == 2:
            st.delete(val)
        elif p == 3:
            print(st.get_rank(val))
        elif p == 4:
            print(st.get_val(val + 1))
        elif p == 5:
            print(st.tree[st.get_pre(val)].v)
        elif p == 6:
            print(st.tree[st.get_suc(val)].v)


if __name__ == "__main__":
    main()

AVL树

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


#include <iostream>
using namespace std;
struct Node
{
	int key;
	Node* left, * right;
	int Height;
};

Node* newNode(int key)
{
	Node* newNode = new Node;
	newNode->Height = 0;
	newNode->key = key;
	newNode->left = newNode->right = NULL;
	return newNode;
}
int GetHeight(Node* root)
{
	if (!root)
		return 0;
	return 1 + max(GetHeight(root->left), GetHeight(root->right));
}

int GetBalanceFactor(Node* root)
{
	if (!root)
		return 0;
	return GetHeight(root->left) - GetHeight(root->right);
}

Node* LRotate(Node* y)
{
	/* 树结构示意图：
			   y
			  / \
			 O   x
				/ \
			   O   O
   */
	Node* x = y->right;
	Node* t = x->left;

	x->left = y;
	y->right = t;

	x->Height = GetHeight(x);
	y->Height = GetHeight(y);

	return x;
}

Node* RRotate(Node* y)
{
	/* 树结构示意图：
			   y
			  / \
			 x   O
			/ \
		   O   O
   */
	Node* x = y->left;
	Node* t = x->right;

	x->right = y;
	y->left = t;

	x->Height = GetHeight(x);
	y->Height = GetHeight(y);

	return x;
}
Node* Insert(Node* root, int key)
{
	if (!root)
		return newNode(key);
	if (key < root->key)
		root->left = Insert(root->left, key);
	else if (key > root->key)
		root->right = Insert(root->right, key);
	else
		return root;

	root->Height = GetHeight(root);

	int bf = GetBalanceFactor(root);
	// L
	if (bf > 1)
	{
		// L
		if (key < root->left->key)
			return RRotate(root); // 左左 右
		// R
		else if (key > root->left->key)
		{
			root->left = LRotate(root->left);
			return RRotate(root);
		}
	}
	else if (bf < -1)
	{
		if (key > root->right->key)
			return LRotate(root);
		else if (key < root->right->key)
		{
			root->right = RRotate(root->right);
			return LRotate(root);
		}
	}

	return root;
}

BST树

其中insert函数未使用引用 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
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
#include <iostream>
typedef struct Node
{
	struct Node* left, * right;
	int data;
}Node;

Node* searchBST(Node* root, int x, Node* f)
{
	if (!root)return f;
	else if (root->data == x)return root;
	else if (root->data > x)return searchBST(root->left, x, root);
	else return searchBST(root->right, x, root);
}

Node* insertBST(Node* root, int x)
{
	Node* p = searchBST(root, x, NULL);
	Node* s = (Node*)malloc(sizeof(Node));
	s->data = x;
	s->right = s->left = NULL;
	if (!p)return s;
	else if (p->data > x)p->left = s;
	else p->right = s;
	return root;
}

void Delete(Node*& T)
{
	if (!T->left && !T->right)
	{
		T = NULL; 
		return;
	}
	if (T->left)
	{
		Node* s = T->left;
		Node* q = T;
		while (s->right)
		{
			q = s;
			s = s->right;
		}
		T->data = s->data;
		if (T != q)q->right = s->left;
		else T->left = s->left;
	}
	else
	{
		Node* s = T->right;
		Node* q = T;
		while (s->left)
		{
			q = s;
			s = s->left;
		}
		T->data = s->data;
		if (T != q)q->left = s->right;
		else T->right = s->right;
	}
}

void removeBST(Node*& T, int e)
{
	if (!T)
		return;
	if (T->data == e)
	{
		Delete(T);
	}
	else if (T->data > e)
		removeBST(T->left, e);
	else
		removeBST(T->right, e);
}

algorithm
#Tree #study
平衡树
https://brtulien.github.io/2023/08/08/平衡树/
作者
Brtulien
发布于
2023年8月8日
更新于
2024年7月1日
许可协议