tpl_tdRbTreeRk.H File Reference

Top-down Red-Black tree with rank support. More...

#include <functional>
#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>
#include <tpl_binNodeXt.H>
#include <tpl_binTreeOps.H>
#include <rbNodeRk.H>

Include dependency graph for tpl_tdRbTreeRk.H:

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

Go to the source code of this file.

Classes
class	Aleph::GenTdRbTreeRk< NodeType, Key, Compare >
	Top-down red-black tree with rank support (select/position). More...
struct	Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::Iterator
	Iterator. More...
class	Aleph::TdRbTreeRk< Key, Compare >
	Top-down red-black tree with rank (no virtual destructor). More...
class	Aleph::TdRbTreeRkVtl< Key, Compare >
	Top-down red-black tree with rank (virtual destructor). More...

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

Detailed Description

Top-down Red-Black tree with rank support.

Extends top-down RB tree with subtree size counts for O(log n) select() and position() operations.

Features

• select(k): Find k-th smallest element
• position(key): Find rank of key
• O(log n) insert with rank updates

See also

tpl_tdRbTree.H Base implementation

tpl_rbRk.H Bottom-up variant with rank

Author

Leandro Rabindranath León

Definition in file tpl_tdRbTreeRk.H.