tpl_treap.H File Reference

Treap: randomized BST combining tree and heap properties. More...

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

Include dependency graph for tpl_treap.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Treap< NodeType, Key, Compare >
	Treap - A randomized binary search tree using heap-ordered priorities. More...
struct	Aleph::Gen_Treap< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...
struct	Aleph::Treap< Key, Compare >
	Treap (a special type of randomized binary search tree) using nodes without virtual destructor. More...
struct	Aleph::Treap_Vtl< Key, Compare >
	Treap (a special type of randomized binary search tree) using nodes with virtual destructors. More...

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

Detailed Description

Treap: randomized BST combining tree and heap properties.

Each node has a key (BST order) and random priority (heap order). Provides expected O(log n) operations with simpler implementation than deterministic balanced trees.

Features

• Randomized balancing (no rotations needed for balance)
• Expected O(log n) height
• Simple split/join operations

Complexity: O(log n) expected for all operations

See also

tpl_treapRk.H Treap with rank support

Author

Leandro Rabindranath León

Definition in file tpl_treap.H.