random_tree.H File Reference

Random tree generation using GSL random number generator. More...

#include <gsl/gsl_rng.h>
#include <memory>
#include <tpl_tree_node.H>
#include <tpl_binNodeUtils.H>
#include <ah-errors.H>

Include dependency graph for random_tree.H:

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

Go to the source code of this file.

Classes
class	RandTree< T >
	Generator for uniformly random trees. More...

Detailed Description

Random tree generation using GSL random number generator.

This file provides the RandTree class for generating uniformly random trees with n nodes. Uses the recursive bijection between binary trees and general trees for generation.

Algorithm

The algorithm generates random binary trees by:

1. Choosing a random inorder position i for the root (0 to n-1)
2. Recursively building left subtree with i nodes
3. Recursively building right subtree with n-i-1 nodes
4. Converting binary tree to general tree

This produces uniformly distributed random trees.

Usage Example

#include <random_tree.H>
 
RandTree<int> gen(42);  // Seed = 42
Tree_Node<int>* tree = gen(100);  // Generate tree with 100 nodes
 
// ... use tree ...
 
destroyRec(tree);  // Clean up

See also

tpl_tree_node.H General tree node

tpl_binNode.H Binary tree node

random_graph.H Random graph generation

Author

Leandro Rabindranath León

Definition in file random_tree.H.