tlx
splay_tree.hpp File Reference
#include <functional>
#include <memory>

Go to the source code of this file.

Classes

class  SplayTree< Key, Compare, Duplicates, Allocator >
 
struct  SplayTree< Key, Compare, Duplicates, Allocator >::Node
 splay tree node, also seen as public iterator More...
 

Namespaces

 tlx
 

Typedefs

template<typename Key , typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_set = SplayTree< Key, Compare, false, Allocator >
 
template<typename Key , typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_multiset = SplayTree< Key, Compare, true, Allocator >
 

Functions

template<typename Tree , typename Compare >
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 More...
 
template<typename Tree , typename Compare >
bool splay_check (const Tree *t, const Compare &cmp)
 check the tree order More...
 
template<typename Key , typename Tree , typename Compare >
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, and the tree used is defined by rat size fields are maintained. More...
 
template<typename Tree , typename Compare >
Tree * splay_insert (Tree *nn, Tree *t, const Compare &cmp)
 Insert key i into the tree t, if it is not already there. More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splay_erase (const Key &k, Tree *&t, const Compare &cmp)
 Erases i from the tree if it's there. More...
 
template<typename Tree , typename Functor >
void splay_traverse_preorder (const Functor &f, const Tree *t)
 traverse the tree in preorder (left, node, right) More...
 
template<typename Tree , typename Functor >
void splay_traverse_postorder (const Functor &f, Tree *t)
 traverse the tree in postorder (left, right, node) More...