tlx
Loading...
Searching...
No Matches
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

namespace  tlx

Typedefs

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

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
template<typename Tree, typename Compare>
bool splay_check (const Tree *t, const Compare &cmp)
 check the tree order
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.
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.
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.
template<typename Tree, typename Functor>
void splay_traverse_preorder (const Functor &f, const Tree *t)
 traverse the tree in preorder (left, node, right)
template<typename Tree, typename Functor>
void splay_traverse_postorder (const Functor &f, Tree *t)
 traverse the tree in postorder (left, right, node)