RandTree< T > Class Template Reference

Generator for uniformly random trees. More...

#include <random_tree.H>

Public Member Functions
	RandTree (unsigned long seed)
	Construct generator with specified seed.
	RandTree ()
	Construct generator with time-based seed.
	~RandTree ()
	Destructor releases GSL resources.
Tree_Node< T > *	operator() (size_t n)
	Generate a random tree with n nodes.

Private Member Functions
BinNode< T > *	random (unsigned long n)
	Recursively generate random binary tree.

Private Attributes
gsl_rng *	r = nullptr
	GSL random number generator.

Detailed Description

template<typename T>
class RandTree< T >

Generator for uniformly random trees.

Uses the GSL Mersenne Twister (MT19937) random number generator to create uniformly distributed random trees with a specified number of nodes.

Template Parameters

T	Type of data stored in tree nodes (not used for generation)

Complexity

• Time: O(n) expected for n nodes
• Space: O(n) for the tree structure

Example

// Create generator with specific seed for reproducibility
RandTree<std::string> gen(12345);
 
// Generate random tree with 50 nodes
Tree_Node<std::string>* root = gen(50);
 
// Tree structure is random but deterministic for same seed

Author

Leandro Rabindranath León

Definition at line 112 of file random_tree.H.

Constructor & Destructor Documentation

RandTree() [1/2]

template<typename T >

RandTree< T >::RandTree ( unsigned long  seed )

inline

Construct generator with specified seed.

Parameters

seed	Random seed for reproducibility

Exceptions

std::bad_alloc

if GSL allocation fails

Definition at line 143 of file random_tree.H.

References ah_bad_alloc_if, Aleph::maps(), and RandTree< T >::r.

RandTree() [2/2]

template<typename T >

RandTree< T >::RandTree ( )

inline

Construct generator with time-based seed.

Uses current time as seed for non-reproducible random trees.

Definition at line 156 of file random_tree.H.

~RandTree()

template<typename T >

RandTree< T >::~RandTree ( )

inline

Destructor releases GSL resources.

Definition at line 161 of file random_tree.H.

References Aleph::maps(), and RandTree< T >::r.

Member Function Documentation

operator()()

template<typename T >

Tree_Node< T > * RandTree< T >::operator() ( size_t  n )

inline

Generate a random tree with n nodes.

Parameters

n	Number of nodes in the tree (must be > 0)

Returns

Pointer to root of newly allocated tree

Precondition

n > 0

Note

Caller is responsible for freeing the returned tree

Example

RandTree<int> gen(42);
Tree_Node<int>* tree = gen(100);
// ... use tree ...
destroyRec(tree);  // Don't forget to clean up!

Definition at line 184 of file random_tree.H.

References Aleph::bin_to_tree(), Aleph::destroyRec(), l, Aleph::maps(), RandTree< T >::random(), and root().

random()

template<typename T >

BinNode< T > * RandTree< T >::random ( unsigned long  n )

inlineprivate

Recursively generate random binary tree.

Parameters

n	Number of nodes in the subtree

Returns

Root of the generated subtree, or nullptr if n=0

Definition at line 122 of file random_tree.H.

References Aleph::LLINK(), Aleph::maps(), RandTree< T >::r, RandTree< T >::random(), Aleph::RLINK(), and root().

Referenced by RandTree< T >::operator()(), and RandTree< T >::random().

Member Data Documentation

r

template<typename T >

gsl_rng* RandTree< T >::r = nullptr

private

GSL random number generator.

Definition at line 114 of file random_tree.H.

Referenced by RandTree< T >::RandTree(), RandTree< T >::~RandTree(), and RandTree< T >::random().

---

The documentation for this class was generated from the following file:

• random_tree.H