tpl_rbRk.H File Reference

Red-Black tree with rank (order statistics). More...

#include <ahFunction.H>
#include <tpl_arrayStack.H>
#include <tpl_binNodeUtils.H>
#include <tpl_binNodeXt.H>
#include <tpl_binTreeOps.H>
#include <rbNodeRk.H>
#include <ah-errors.H>

Include dependency graph for tpl_rbRk.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >
	Red-black tree with rank support (select/position operations). More...
class	Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...
struct	Aleph::Rb_Tree_Rk< Key, Compare >
	Red-Black binary search tree with nodes without virtual destructor and with subtree counters for select/position operations. More...
struct	Aleph::Rb_Tree_Rk_Vtl< Key, Compare >
	Red-Black binary search tree with virtual destructor in its nodes and with subtree counters for select/position operations. More...

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

Detailed Description

Red-Black tree with rank (order statistics).

Bottom-up RB tree augmented with subtree sizes for order statistics queries.

Features

• select(k): O(log n) k-th element
• position(x): O(log n) rank of element
• split_pos(): Split at position

See also

tpl_rb_tree.H Base RB tree

tpl_avlRk.H AVL with rank

Author

Leandro Rabindranath León

Definition in file tpl_rbRk.H.