Skip to content

Commit 0b83599

Browse files
fredbrfredbr
committed
Added splay tree
1 parent 8064cad commit 0b83599

File tree

3 files changed

+422
-73
lines changed

3 files changed

+422
-73
lines changed

‎data_structures/seg_class.cpp

Lines changed: 22 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,8 @@ class Seg {
1212

1313
std::vector<T> tree;
1414

15-
T const& build(int no, int l, int r, std::vector<T> const& v)
15+
template<typename Iter>
16+
T const& build(int no, int l, int r, Iter const& v)
1617
{
1718
if (l == r)
1819
return tree[no] = v[l];
@@ -58,29 +59,35 @@ class Seg {
5859

5960
public:
6061
Seg(int n_, join_t op_) :
61-
join(op_), n(n_)
62+
join(op_), n(n_), tree(n*4) {};
63+
64+
Seg(int n_, join_t op_, fix_t fix_) :
65+
join(op_), n(n_), fix(fix_), tree(n*4) {};
66+
67+
Seg(std::vector<T> const& v, join_t op_) :
68+
join(op_), n(v.size()), tree(v.size()*4)
6269
{
63-
tree.resize(n*4);
70+
build(0, 0, n-1, v.data());
6471
}
6572

66-
Seg(int n_, join_t op_, fix_t fix_) :
67-
join(op_), n(n_), fix(fix_)
73+
Seg(std::vector<T> const& v, join_t op_, fix_t fix_) :
74+
join(op_), n(v.size()), fix(fix_), tree(v.size()*4)
6875
{
69-
tree.resize(n*4);
76+
build(0, 0, n-1, v.data());
7077
}
7178

72-
Seg(std::vector<T> const& v, join_t op_) :
73-
join(op_), n(v.size())
79+
template<typename Iter>
80+
Seg(Iter const& begin, Iter const& end, join_t op_) :
81+
join(op_), n(end-begin), tree(4*(end-begin))
7482
{
75-
tree.resize(n*4);
76-
build(0, 0, n-1, v);
83+
build(0, 0, n-1, begin);
7784
}
7885

79-
Seg(std::vector<T> const& v, join_t op_, fix_t fix_) :
80-
join(op_), n(v.size()), fix(fix_)
86+
template<typename Iter>
87+
Seg(Iter const& begin, Iter const& end, join_t op_, fix_t fix_) :
88+
join(op_), n(end-begin), fix(fix_), tree(4*(end-begin))
8189
{
82-
tree.resize(n*4);
83-
build(0, 0, n-1, v);
90+
build(0, 0, n-1, begin);
8491
}
8592

8693
void upd(int pos, T val)
@@ -129,7 +136,7 @@ int main()
129136
for (int i = 0; i < n; i++)
130137
std::cin >> v[i].mini, v[i].maxi = v[i].mini;
131138

132-
auto sg = Seg<Problem::Node>(v, Problem::join, Problem::fix);
139+
auto sg = Seg<Problem::Node>(v.begin(), v.end(), Problem::join, Problem::fix);
133140

134141
while (q--) {
135142

‎data_structures/splay.cpp

Lines changed: 195 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,195 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
template<typename T, typename Comp = less<T>>
6+
class Splay {
7+
private:
8+
struct Node {
9+
Node *p;
10+
Node *l, *r;
11+
12+
T val;
13+
14+
Node(T const& v) : p(nullptr), l(nullptr), r(nullptr), val(v) {};
15+
};
16+
17+
Node *root;
18+
int64_t sz;
19+
Comp comp;
20+
21+
void lrot(Node *x) {
22+
Node *y = x->r;
23+
if (y) {
24+
x->r = y->l;
25+
if (y->l) y->l->p = x;
26+
y->p = x->p;
27+
}
28+
if (!x->p) root = y;
29+
else if (x->p->l == x) x->p->l = y;
30+
else if (x->p->r == x) x->p->r = y;
31+
if (y) y->l = x;
32+
x->p = y;
33+
}
34+
35+
void rrot(Node *x) {
36+
Node *y = x->l;
37+
if (y) {
38+
x->l = y->r;
39+
if (y->r) y->r->p = x;
40+
y->p = x->p;
41+
}
42+
if (!x->p) root = y;
43+
else if (x->p->l == x) x->p->l = y;
44+
else if (x->p->r == x) x->p->r = y;
45+
if (y) y->r = x;
46+
x->p = y;
47+
}
48+
49+
void splay(Node *x) {
50+
while (x->p) {
51+
if (!x->p->p) {
52+
if (x->p->l == x) rrot(x->p);
53+
else lrot(x->p);
54+
}
55+
else if (x->p->l == x and x->p->p->l == x->p) {
56+
rrot(x->p->p);
57+
rrot(x->p);
58+
}
59+
else if (x->p->r == x and x->p->p->r == x->p) {
60+
lrot(x->p->p);
61+
lrot(x->p);
62+
}
63+
else if (x->p->l == x and x->p->p->r == x->p) {
64+
rrot(x->p);
65+
lrot(x->p);
66+
}
67+
else {
68+
lrot(x->p);
69+
rrot(x->p);
70+
}
71+
}
72+
}
73+
74+
void replace(Node *x, Node *y) {
75+
if (!x->p) root = y;
76+
else if (x == x->p->l) x->p->l = y;
77+
else x->p->r = y;
78+
if (y) y->p = x->p;
79+
}
80+
81+
void insert(Node *&x, Node *y, Node *p) {
82+
if (!x) {
83+
x = y;
84+
y->p = p;
85+
splay(y);
86+
}
87+
else if (comp(y->val, x->val)) insert(x->l, y, x);
88+
else insert(x->r, y, x);
89+
}
90+
91+
Node* find(Node *t, T const& v) {
92+
if (!t) return nullptr;
93+
else if (t->val == v) {
94+
splay(t);
95+
return root;
96+
}
97+
else if (comp(v, t->val)) return find(t->l, v);
98+
else return find(t->r, v);
99+
}
100+
101+
void print(Node *t) {
102+
if (!t) return;
103+
print(t->l);
104+
cout << t->val << " ";
105+
print(t->r);
106+
}
107+
108+
Node* find_min(Node *t) {
109+
if (!t) return nullptr;
110+
else if (t->l) return find_min(t->l);
111+
else return t;
112+
}
113+
114+
Node* find_max(Node *t) {
115+
if (!t) return nullptr;
116+
else if (t->r) return find_max(t->r);
117+
else return t;
118+
}
119+
120+
Node* join(Node *l, Node *r) {
121+
l = find_max(l), r = find_min(r);
122+
splay(l);
123+
splay(r);
124+
l->r = r;
125+
r->p = l;
126+
127+
return l;
128+
}
129+
130+
public:
131+
Splay() : root(nullptr), sz(0), comp() {};
132+
133+
void insert(T const& v) {
134+
Node *t = new Node(v);
135+
insert(root, t, nullptr);
136+
sz++;
137+
}
138+
139+
Node const* find(T const& v) {
140+
return find(root, v);
141+
}
142+
143+
void erase(T const& v) {
144+
Node *t = find(root, v);
145+
if (!t) return;
146+
147+
sz--;
148+
149+
if (!t->l) replace(t, t->r);
150+
else if (!t->r) replace(t, t->l);
151+
else {
152+
replace(t, join(t->l, t->r));
153+
delete t;
154+
}
155+
}
156+
157+
int64_t size() const {
158+
return sz;
159+
}
160+
161+
void print() {
162+
print(root);
163+
cout << "\n";
164+
}
165+
};
166+
167+
int main() {
168+
Splay<int> st;
169+
170+
st.insert(2);
171+
st.insert(4);
172+
st.insert(3);
173+
st.insert(5);
174+
175+
assert(!st.find(1));
176+
assert(st.find(2));
177+
assert(st.find(3));
178+
assert(st.find(4));
179+
assert(st.find(5));
180+
assert(!st.find(6));
181+
182+
st.print();
183+
184+
st.erase(2);
185+
st.erase(4);
186+
187+
assert(!st.find(1));
188+
assert(!st.find(2));
189+
assert(st.find(3));
190+
assert(!st.find(4));
191+
assert(st.find(5));
192+
assert(!st.find(6));
193+
194+
st.print();
195+
}

0 commit comments

Comments
 (0)