tlx
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 
17 namespace 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
68 template <typename Tree, typename Compare>
69 bool 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
87 template <typename Tree, typename Compare>
88 bool 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.
96 template <typename Key, typename Tree, typename Compare>
97 Tree * 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.
155 template <typename Tree, typename Compare>
156 Tree * 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.
175 template <typename Key, typename Tree, typename Compare>
176 Tree * 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)
200 template <typename Tree, typename Functor>
201 void 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)
209 template <typename Tree, typename Functor>
210 void 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 
220 template <typename Key, typename Compare = std::less<Key>,
221  bool Duplicates = false,
222  typename Allocator = std::allocator<Key> >
224 {
225 public:
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);
254  root_ = splay_insert(nn, root_, cmp_);
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 
309 private:
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 Allocator::template rebind<Node>::other node_alloc_type;
321 
322  //! node allocator
323  node_alloc_type 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 
333 template <typename Key, typename Compare = std::less<Key>,
334  typename Allocator = std::allocator<Key> >
335 using splay_set = SplayTree<Key, Compare, /* Duplicates */ false, Allocator>;
336 
337 template <typename Key, typename Compare = std::less<Key>,
338  typename Allocator = std::allocator<Key> >
339 using splay_multiset =
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_
number of items in tree container
Definition: splay_tree.hpp:313
bool check() const
check the tree order
Definition: splay_tree.hpp:299
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...
Definition: splay_tree.hpp:97
Tree * splay_insert(Tree *nn, Tree *t, const Compare &cmp)
Insert key i into the tree t, if it is not already there.
Definition: splay_tree.hpp:156
bool erase(const Node *n)
erase node from tree, return true if it existed.
Definition: splay_tree.hpp:268
Node * find(const Key &k)
find tree node containing key or return smallest key larger than k
Definition: splay_tree.hpp:294
Node(const Key &k)
Definition: splay_tree.hpp:230
bool exists(const Key &k)
check if key exists
Definition: splay_tree.hpp:278
bool insert(const Key &k)
insert key into tree if it does not exist, returns true if inserted.
Definition: splay_tree.hpp:244
bool erase(const Key &k)
erase key from tree, return true if it existed.
Definition: splay_tree.hpp:260
void traverse_preorder(const Functor &f) const
traverse the whole tree in preorder (key order)s
Definition: splay_tree.hpp:305
void splay_traverse_postorder(const Functor &f, Tree *t)
traverse the tree in postorder (left, right, node)
Definition: splay_tree.hpp:210
void splay_traverse_preorder(const Functor &f, const Tree *t)
traverse the tree in preorder (left, node, right)
Definition: splay_tree.hpp:201
Allocator alloc_
key allocator
Definition: splay_tree.hpp:317
size_t size() const
return number of items in tree
Definition: splay_tree.hpp:284
SplayTree(Allocator alloc=Allocator())
Definition: splay_tree.hpp:233
void clear()
free all nodes
Definition: splay_tree.hpp:273
Node * root_
root tree node
Definition: splay_tree.hpp:311
void delete_node(Node *n)
delete node
Definition: splay_tree.hpp:326
node_alloc_type node_allocator_
node allocator
Definition: splay_tree.hpp:323
Compare cmp_
key comparator
Definition: splay_tree.hpp:315
Allocator::template rebind< Node >::other node_alloc_type
node allocator
Definition: splay_tree.hpp:320
bool empty() const
return true if tree is empty
Definition: splay_tree.hpp:289
SplayTree(Compare cmp, Allocator alloc=Allocator())
Definition: splay_tree.hpp:236
splay tree node, also seen as public iterator
Definition: splay_tree.hpp:227
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
Definition: splay_tree.hpp:69
Tree * splay_erase(const Key &k, Tree *&t, const Compare &cmp)
Erases i from the tree if it&#39;s there.
Definition: splay_tree.hpp:176