tpl_avlRk.H File Reference

AVL tree with rank (order statistics). More...

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

Include dependency graph for tpl_avlRk.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >
	AVL balanced binary search tree with rank (order statistics). More...
class	Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Iterator
	Iterator over the nodes. More...
struct	Aleph::Avl_Tree_Rk< Key, Compare >
	AVL binary search tree with nodes without virtual destructor and with subtree counters for select/position operations. More...
struct	Aleph::Avl_Tree_Rk_Vtl< Key, Compare >
	AVL 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

AVL tree with rank (order statistics).

AVL tree augmented with subtree sizes for order statistics. Combines strict balance with rank queries.

Features

• select(k): O(log n) k-th element
• position(x): O(log n) rank of element
• Strictly balanced (height ≤ 1.44 log n)

See also

tpl_avl.H Base AVL tree

tpl_rbRk.H RB tree with rank

Author

Leandro Rabindranath León

Definition in file tpl_avlRk.H.