tpl_treapRk.H File Reference

Treap with rank (order statistics). More...

#include <gsl/gsl_rng.h>
#include <ahFunction.H>
#include <tpl_binTreeOps.H>
#include <ran_array.h>
#include <treapNode.H>
#include <ah-errors.H>

Include dependency graph for tpl_treapRk.H:

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

Go to the source code of this file.

Classes
class	Aleph::TreapRkNode_Data
class	Aleph::Treap_Rk_Node< Key >
class	Aleph::Treap_Rk_NodeVtl< Key >
class	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >
	Extended Treap with rank support for O(log n) indexed access. More...
class	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...
struct	Aleph::Treap_Rk< Key, Compare >
	Extended treap (a special type of randomized binary search tree) which manages selection and splitting for inorder position. More...
struct	Aleph::Treap_Rk_Vtl< Key, Compare >
	Extended treap (a special type of randomized binary search tree) which manages selection and splitting for inorder position. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Treap with rank (order statistics).

Randomized BST augmented with subtree sizes. Simple implementation with expected O(log n).

Features

• select(k): Expected O(log n)
• position(x): Expected O(log n)
• Implicit keys possible

See also

tpl_treap.H Base treap

tpl_rbRk.H Deterministic alternative

Author

Leandro Rabindranath León

Definition in file tpl_treapRk.H.