tpl_splay_treeRk.H File Reference

Top-down splay tree with rank support. More...

#include <tpl_binNodeXt.H>
#include <ah-errors.H>

Include dependency graph for tpl_splay_treeRk.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	GenTdSplayTreeRk< NodeType, Key, Compare >
	Top-down splay tree with rank support. More...
class	GenTdSplayTreeRk< NodeType, Key, Compare >::Iterator
	Inorder iterator over the extended splay tree. More...
struct	Splay_Tree_Rk< Key, Compare >
struct	Splay_Tree_Rk_Vtl< Key, Compare >

Detailed Description

Top-down splay tree with rank support.

This file implements a splay tree with node counts (rank support), enabling O(log n) access to the k-th element. The implementation is based on Danny Sleator's original splay tree code, adapted to C++ with extended functionality.

Original source: http://www.link.cs.cmu.edu/link/ftp-site/splaying/SplayTree.java

See also

Splay_Tree_Rk Convenient typedef.

DynSetSplayTree High-level wrapper with automatic memory management.

Author

Leandro Rabindranath León

Definition in file tpl_splay_treeRk.H.