tlx
Loading...
Searching...
No Matches
splay_tree.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/container/splay_tree.hpp
3 *
4 * Part of tlx - http://panthema.net/tlx
5 *
6 * Copyright (C) 2016-2019 Timo Bingmann <tb@panthema.net>
7 *
8 * All rights reserved. Published under the Boost Software License, Version 1.0
9 ******************************************************************************/
10
11#ifndef TLX_CONTAINER_SPLAY_TREE_HEADER
12#define TLX_CONTAINER_SPLAY_TREE_HEADER
13
14#include <functional>
15#include <memory>
16
17namespace tlx {
18
19//! \addtogroup tlx_container
20//! \{
21
22/******************************************************************************/
23// splay -- free Splay Tree methods
24
25/*
26 An implementation of top-down splaying
27 D. Sleator <sleator@cs.cmu.edu>
28 March 1992
29
30 "Splay trees", or "self-adjusting search trees" are a simple and efficient
31 data structure for storing an ordered set. The data structure consists of a
32 binary tree, without parent pointers, and no additional fields. It allows
33 searching, insertion, deletion, deletemin, deletemax, splitting, joining, and
34 many other operations, all with amortized logarithmic performance. Since the
35 trees adapt to the sequence of requests, their performance on real access
36 patterns is typically even better. Splay trees are described in a number of
37 texts and papers [1,2,3,4,5].
38
39 The code here is adapted from simple top-down splay, at the bottom of page 669
40 of [3]. It can be obtained via anonymous ftp from spade.pc.cs.cmu.edu in
41 directory /usr/sleator/public.
42
43 The chief modification here is that the splay operation works even if the item
44 being splayed is not in the tree, and even if the tree root of the tree is
45 nullptr. So the line:
46
47 t = splay(i, t);
48
49 causes it to search for item with key i in the tree rooted at t. If it's
50 there, it is splayed to the root. If it isn't there, then the node put at the
51 root is the last one before nullptr that would have been reached in a normal
52 binary search for i. (It's a neighbor of i in the tree.) This allows many
53 other operations to be easily implemented, as shown below.
54
55 [1] "Fundamentals of data structures in C", Horowitz, Sahni,
56 and Anderson-Freed, Computer Science Press, pp 542-547.
57 [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
58 Harper Collins, 1991, pp 243-251.
59 [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
60 JACM Volume 32, No 3, July 1985, pp 652-686.
61 [4] "Data Structure and Algorithm Analysis", Mark Weiss,
62 Benjamin Cummins, 1992, pp 119-130.
63 [5] "Data Structures, Algorithms, and Performance", Derick Wood,
64 Addison-Wesley, 1993, pp 367-375.
65*/
66
67//! check the tree order, recursively calculate min and max elements
68template <typename Tree, typename Compare>
69bool splay_check(const Tree* t,
70 const Tree*& out_tmin, const Tree*& out_tmax,
71 const Compare& cmp) {
72 if (t == nullptr) return true;
73
74 const Tree* tmin = nullptr, * tmax = nullptr;
75 if (!splay_check(t->left, out_tmin, tmax, cmp) ||
76 !splay_check(t->right, tmin, out_tmax, cmp))
77 return false;
78
79 if (tmax && !cmp(tmax->key, t->key))
80 return false;
81 if (tmin && !cmp(t->key, tmin->key))
82 return false;
83 return true;
84}
85
86//! check the tree order
87template <typename Tree, typename Compare>
88bool splay_check(const Tree* t, const Compare& cmp) {
89 if (t == nullptr) return true;
90 const Tree* tmin = nullptr, * tmax = nullptr;
91 return splay_check(t, tmin, tmax, cmp);
92}
93
94//! Splay using the key i (which may or may not be in the tree.) The starting
95//! root is t, and the tree used is defined by rat size fields are maintained.
96template <typename Key, typename Tree, typename Compare>
97Tree * splay(const Key& k, Tree* t, const Compare& cmp) {
98 Tree* N_left = nullptr, * N_right = nullptr;
99 Tree* l = nullptr, * r = nullptr;
100
101 if (t == nullptr) return t;
102
103 for ( ; ; ) {
104 if (cmp(k, t->key)) {
105 if (t->left == nullptr) break;
106
107 if (cmp(k, t->left->key)) {
108 // rotate right
109 Tree* y = t->left;
110 t->left = y->right;
111 y->right = t;
112 t = y;
113 if (t->left == nullptr) break;
114 }
115 // link right
116 (r ? r->left : N_left) = t;
117 r = t;
118 t = t->left;
119 }
120 else if (cmp(t->key, k)) {
121 if (t->right == nullptr) break;
122
123 if (cmp(t->right->key, k)) {
124 // rotate left
125 Tree* y = t->right;
126 t->right = y->left;
127 y->left = t;
128 t = y;
129 if (t->right == nullptr) break;
130 }
131 // link left
132 (l ? l->right : N_right) = t;
133 l = t;
134 t = t->right;
135 }
136 else {
137 break;
138 }
139 }
140
141 (l ? l->right : N_right) = (r ? r->left : N_left) = nullptr;
142
143 // assemble
144 (l ? l->right : N_right) = t->left;
145 (r ? r->left : N_left) = t->right;
146 t->left = N_right;
147 t->right = N_left;
148
149 return t;
150}
151
152//! Insert key i into the tree t, if it is not already there. Before calling
153//! this method, one *MUST* call splay() to rotate the tree to the right
154//! position. Return a pointer to the resulting tree.
155template <typename Tree, typename Compare>
156Tree * splay_insert(Tree* nn, Tree* t, const Compare& cmp) {
157 if (t == nullptr) {
158 nn->left = nn->right = nullptr;
159 }
160 else if (cmp(nn->key, t->key)) {
161 nn->left = t->left;
162 nn->right = t;
163 t->left = nullptr;
164 }
165 else {
166 nn->right = t->right;
167 nn->left = t;
168 t->right = nullptr;
169 }
170 return nn;
171}
172
173//! Erases i from the tree if it's there. Return a pointer to the resulting
174//! tree.
175template <typename Key, typename Tree, typename Compare>
176Tree * splay_erase(const Key& k, Tree*& t, const Compare& cmp) {
177 if (t == nullptr) return nullptr;
178 t = splay(k, t, cmp);
179 // k == t->key ?
180 if (!cmp(k, t->key) && !cmp(t->key, k)) {
181 // found it
182 Tree* r = t;
183 if (t->left == nullptr) {
184 t = t->right;
185 }
186 else {
187 Tree* x = splay(k, t->left, cmp);
188 x->right = t->right;
189 t = x;
190 }
191 return r;
192 }
193 else {
194 // it wasn't there
195 return nullptr;
196 }
197}
198
199//! traverse the tree in preorder (left, node, right)
200template <typename Tree, typename Functor>
201void splay_traverse_preorder(const Functor& f, const Tree* t) {
202 if (t == nullptr) return;
203 splay_traverse_preorder(f, t->left);
204 f(t);
205 splay_traverse_preorder(f, t->right);
206}
207
208//! traverse the tree in postorder (left, right, node)
209template <typename Tree, typename Functor>
210void splay_traverse_postorder(const Functor& f, Tree* t) {
211 if (t == nullptr) return;
212 splay_traverse_postorder(f, t->left);
213 splay_traverse_postorder(f, t->right);
214 f(t);
215}
216
217/******************************************************************************/
218// Splay Tree
219
220template <typename Key, typename Compare = std::less<Key>,
221 bool Duplicates = false,
222 typename Allocator = std::allocator<Key> >
224{
225public:
226 //! splay tree node, also seen as public iterator
227 struct Node {
228 Node* left = nullptr, * right = nullptr;
229 Key key;
230 explicit Node(const Key& k) : key(k) { }
231 };
232
233 explicit SplayTree(Allocator alloc = Allocator())
234 : node_allocator_(alloc) { }
235
236 explicit SplayTree(Compare cmp, Allocator alloc = Allocator())
237 : cmp_(cmp), node_allocator_(alloc) { }
238
240 clear();
241 }
242
243 //! insert key into tree if it does not exist, returns true if inserted.
244 bool insert(const Key& k) {
245 if (root_ != nullptr) {
246 root_ = splay(k, root_, cmp_);
247 // k == t->key ?
248 if (!Duplicates && !cmp_(k, root_->key) && !cmp_(root_->key, k)) {
249 // it's already there
250 return false;
251 }
252 }
253 Node* nn = new (node_allocator_.allocate(1)) Node(k);
255 size_++;
256 return true;
257 }
258
259 //! erase key from tree, return true if it existed.
260 bool erase(const Key& k) {
261 Node* out = splay_erase(k, root_, cmp_);
262 if (!out) return false;
263 delete_node(out);
264 return true;
265 }
266
267 //! erase node from tree, return true if it existed.
268 bool erase(const Node* n) {
269 return erase(n->key);
270 }
271
272 //! free all nodes
273 void clear() {
274 splay_traverse_postorder([this](Node* n) { delete_node(n); }, root_);
275 }
276
277 //! check if key exists
278 bool exists(const Key& k) {
279 root_ = splay(k, root_, cmp_);
280 return !cmp_(root_->key, k) && !cmp_(k, root_->key);
281 }
282
283 //! return number of items in tree
284 size_t size() const {
285 return size_;
286 }
287
288 //! return true if tree is empty
289 bool empty() const {
290 return size_ == 0;
291 }
292
293 //! find tree node containing key or return smallest key larger than k
294 Node * find(const Key& k) {
295 return (root_ = splay(k, root_, cmp_));
296 }
297
298 //! check the tree order
299 bool check() const {
300 return splay_check(root_, cmp_);
301 }
302
303 //! traverse the whole tree in preorder (key order)s
304 template <typename Functor>
305 void traverse_preorder(const Functor& f) const {
306 splay_traverse_preorder([&f](const Node* n) { f(n->key); }, root_);
307 }
308
309private:
310 //! root tree node
311 Node* root_ = nullptr;
312 //! number of items in tree container
313 size_t size_ = 0;
314 //! key comparator
315 Compare cmp_;
316 //! key allocator
317 Allocator alloc_;
318
319 //! node allocator
320 typedef typename std::allocator_traits<Allocator>::template rebind_alloc<Node> node_alloc_type;
321
322 //! node allocator
324
325 //! delete node
326 void delete_node(Node* n) {
327 n->~Node();
328 node_allocator_.deallocate(n, 1);
329 size_--;
330 }
331};
332
333template <typename Key, typename Compare = std::less<Key>,
334 typename Allocator = std::allocator<Key> >
335using splay_set = SplayTree<Key, Compare, /* Duplicates */ false, Allocator>;
336
337template <typename Key, typename Compare = std::less<Key>,
338 typename Allocator = std::allocator<Key> >
340 SplayTree<Key, Compare, /* Duplicates */ true, Allocator>;
341
342//! \}
343
344} // namespace tlx
345
346#endif // !TLX_CONTAINER_SPLAY_TREE_HEADER
347
348/******************************************************************************/
size_t size() const
return number of items in tree
std::allocator_traits< Allocator >::template rebind_alloc< Node > node_alloc_type
node allocator
void traverse_preorder(const Functor &f) const
traverse the whole tree in preorder (key order)s
bool erase(const Key &k)
erase key from tree, return true if it existed.
bool empty() const
return true if tree is empty
SplayTree(Allocator alloc=Allocator())
bool check() const
check the tree order
bool erase(const Node *n)
erase node from tree, return true if it existed.
void clear()
free all nodes
SplayTree(Compare cmp, Allocator alloc=Allocator())
Node * find(const Key &k)
find tree node containing key or return smallest key larger than k
bool insert(const Key &k)
insert key into tree if it does not exist, returns true if inserted.
bool exists(const Key &k)
check if key exists
void delete_node(Node *n)
delete node
Tree * splay_erase(const Key &k, Tree *&t, const Compare &cmp)
Erases i from the tree if it's there.
SplayTree< Key, Compare, true, Allocator > splay_multiset
SplayTree< Key, Compare, false, Allocator > splay_set
void splay_traverse_preorder(const Functor &f, const Tree *t)
traverse the tree in preorder (left, node, right)
void splay_traverse_postorder(const Functor &f, Tree *t)
traverse the tree in postorder (left, right, node)
Tree * splay(const Key &k, Tree *t, const Compare &cmp)
Splay using the key i (which may or may not be in the tree.) The starting root is t,...
bool splay_check(const Tree *t, const Tree *&out_tmin, const Tree *&out_tmax, const Compare &cmp)
check the tree order, recursively calculate min and max elements
Tree * splay_insert(Tree *nn, Tree *t, const Compare &cmp)
Insert key i into the tree t, if it is not already there.