tpl_rand_tree.H File Reference

Randomized binary search tree. More...

#include <ctime>
#include <climits>
#include <gsl/gsl_rng.h>
#include <ahUtils.H>
#include <ahFunction.H>
#include <tpl_randNode.H>
#include <tpl_binTreeOps.H>
#include <ah-errors.H>

Include dependency graph for tpl_rand_tree.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >
	Randomized binary search tree with rank support. More...
struct	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...
struct	Aleph::Rand_Tree< Key, Compare >
	Randomized binary search tree. More...
struct	Aleph::Rand_Tree_Vtl< Key, Compare >
	Randomized binary search tree. More...

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

Detailed Description

Randomized binary search tree.

BST with randomized insertion that maintains expected O(log n) height without explicit balancing.

Features

• Root insertion with probability 1/(n+1)
• Expected O(log n) operations
• Simpler than deterministic balancing

See also

tpl_treap.H Alternative randomized BST

Author

Leandro Rabindranath León

Definition in file tpl_rand_tree.H.