write_tree.C File Reference

Generates tree structure files for visualization and analysis. More...

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <set>
#include <tclap/CmdLine.h>
#include <aleph.H>
#include <tpl_avl.H>
#include <tpl_rb_tree.H>
#include <tpl_splay_tree.H>
#include <tpl_treap.H>
#include <tpl_rand_tree.H>
#include <tpl_binTree.H>
#include <tpl_binNodeUtils.H>

Include dependency graph for write_tree.C:

Go to the source code of this file.

Functions
vector< int >	generate_random_values (size_t n, unsigned int seed)
static void	avl_print_key (Avl_Tree< int >::Node *p, int, int)
void	write_avl (const vector< int > &values, const string &prefix)
static void	rb_print_key (Rb_Tree< int >::Node *p, int, int)
static void	rb_write_colors (Rb_Tree< int >::Node *p, int, int)
void	write_rb (const vector< int > &values, const string &prefix)
static void	splay_print_key (Splay_Tree< int >::Node *p, int, int)
void	write_splay (const vector< int > &values, const string &prefix)
static void	treap_print_key (Treap< int >::Node *p, int, int)
void	write_treap (const vector< int > &values, const string &prefix)
static void	rand_print_key (Rand_Tree< int >::Node *p, int, int)
void	write_rand (const vector< int > &values, const string &prefix)
static void	bin_print_key (BinTree< int >::Node *p, int, int)
void	write_bin (const vector< int > &values, const string &prefix)
int	main (int argc, char *argv[])

Variables
static ofstream *	current_output = nullptr
static int	rb_pos = 0

Detailed Description

Generates tree structure files for visualization and analysis.

This utility program creates .Tree files containing binary search tree structures in preorder traversal format. These files are designed for visualization tools like btreepic or for algorithm testing and analysis. This tool is essential for understanding how different BST implementations structure the same data differently.

Purpose

Use Cases

This tool is useful for:

• Visualization: Generating tree structures for LaTeX/eepic diagrams
• Algorithm testing: Creating test cases for tree algorithms
• Comparison: Generating the same data with different tree types
• Education: Understanding how different BST implementations structure data
• Research: Studying tree structure properties
• Documentation: Creating tree diagrams for papers/presentations

Supported Tree Types

Balanced Trees

AVL Tree

• Balance: Strictly balanced (height difference ≤ 1)
• Structure: Most balanced possible
• Use: When balance is critical

Red-Black Tree

• Balance: Relaxed balance (no path > 2× shortest)
• Structure: Good balance, efficient operations
• Use: General-purpose balanced tree

Self-Adjusting Trees

Splay Tree

• Strategy: Moves accessed nodes to root
• Structure: Adapts to access patterns
• Use: When temporal locality matters

Randomized Trees

Treap

• Strategy: Randomized BST with heap priorities
• Structure: Probabilistically balanced
• Use: Simple, good average case

Rand Tree

• Strategy: Randomized BST variant
• Structure: Different randomization approach
• Use: Alternative randomized structure

Unbalanced Tree

Binary Tree

• Strategy: No balancing
• Structure: Can degrade to linked list
• Use: Baseline comparison, educational

Summary Table

Type	Description	Balance Strategy	Best For
AVL	Strictly balanced	Height difference ≤ 1	Read-heavy
Red-Black	Relaxed balance	No path > 2× shortest	General purpose
Splay	Self-adjusting	Moves accessed nodes to root	Temporal locality
Treap	Randomized	Heap priorities for balance	Simple, average case
Rand	Randomized BST	Random insertion order	Alternative random
Binary	Unbalanced	No balancing	Baseline, educational

Output Format

File Structure

Each .Tree file contains:

• Preorder traversal: Tree structure in preorder format
• Node values: Keys stored in nodes
• Format: Compatible with btreepic visualization tool

File Naming

Files are named: @p prefix + @p tree_type + ".Tree"

• Examples: test_avl.Tree (use -o test_), rb.Tree (default prefix), mytree_splay.Tree (use -o mytree_)

Format Details

The .Tree format includes:

• Node keys in preorder
• Tree structure information
• Metadata for visualization

Comparison Capabilities

Same Data, Different Structures

Generate same data with different tree types to compare:

• Structure differences: See how trees differ
• Balance: Compare balance quality
• Height: Compare tree heights
• Visualization: Visual comparison

Example

# Generate same data with different trees
write_tree -n 50 -s 42 -t avl   -o compare_
write_tree -n 50 -s 42 -t rb    -o compare_
write_tree -n 50 -s 42 -t splay -o compare_
 
# Visualize and compare
btreepic compare_avl.Tree
btreepic compare_rb.Tree
btreepic compare_splay.Tree

Usage Examples

# Generate all tree types with 100 nodes
write_tree -n 100
 
# Generate only AVL tree with specific seed
write_tree -n 50 -t avl -s 12345 -o mytree_
 
# Generate Red-Black and Splay trees
write_tree -n 200 -t rb
write_tree -n 200 -t splay
 
# Generate multiple types for comparison
write_tree -n 100 -t avl -s 42 -o compare_
write_tree -n 100 -t rb  -s 42 -o compare_
write_tree -n 100 -t splay -s 42 -o compare_

Parameters

Parameter	Short	Description	Default
--count	-n	Number of nodes to insert	30
--seed	-s	Random seed for reproducibility	Time-based
--type	-t	Tree type (avl, rb, splay, treap, rand, bin, all)	all
--output	-o	Output file prefix (concatenated literally; use a trailing _ if you want a separator)	empty

Integration with Visualization

btreepic Tool

Generated .Tree files can be visualized:

btreepic output_avl.Tree > avl.tex
pdflatex avl.tex

LaTeX Output

The visualization generates LaTeX files suitable for:

• Papers: Include in academic papers
• Presentations: Use in slides
• Documentation: Document tree structures

Applications

Algorithm Development

• Test cases: Generate test trees for algorithms
• Debugging: Visualize tree structures during debugging
• Validation: Verify algorithm correctness

Education

• Teaching: Demonstrate tree structures visually
• Learning: Understand how trees differ
• Comparison: Compare different implementations

Research

• Experiments: Generate trees for experiments
• Analysis: Analyze tree properties
• Publications: Create figures for papers

See also

btreepic.C Visualization tool for binary trees

timeAllTree.C Performance comparison (related)

dynset_trees.C Practical comparison

tpl_avl.H AVL tree implementation

tpl_rb_tree.H Red-Black tree implementation

tpl_splay_tree.H Splay tree implementation

tpl_treap.H Treap implementation

Author

Leandro Rabindranath León

Definition in file write_tree.C.

Function Documentation

avl_print_key()

static void avl_print_key ( Avl_Tree< int >::Node *  p, int  , int    )

static

Definition at line 278 of file write_tree.C.

References current_output.

Referenced by write_avl().

bin_print_key()

static void bin_print_key ( BinTree< int >::Node *  p, int  , int    )

static

Definition at line 503 of file write_tree.C.

References current_output.

Referenced by write_bin().

generate_random_values()

vector< int > generate_random_values	(	size_t	n,
		unsigned int	seed
	)

Definition at line 247 of file write_tree.C.

References StlAlephIterator< SetName >::end(), Aleph::DynList< T >::insert(), and Aleph::maps().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 545 of file write_tree.C.

References generate_random_values(), Aleph::maps(), Aleph::prefix(), Aleph::HTList::size(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

rand_print_key()

static void rand_print_key ( Rand_Tree< int >::Node *  p, int  , int    )

static

Definition at line 461 of file write_tree.C.

References current_output.

Referenced by write_rand().

rb_print_key()

static void rb_print_key ( Rb_Tree< int >::Node *  p, int  , int    )

static

Definition at line 320 of file write_tree.C.

References current_output.

Referenced by write_rb().

rb_write_colors()

static void rb_write_colors ( Rb_Tree< int >::Node *  p, int  , int    )

static

Definition at line 326 of file write_tree.C.

References COLOR, current_output, rb_pos, and RED.

Referenced by write_rb().

splay_print_key()

static void splay_print_key ( Splay_Tree< int >::Node *  p, int  , int    )

static

Definition at line 377 of file write_tree.C.

References current_output.

Referenced by write_splay().

treap_print_key()

static void treap_print_key ( Treap< int >::Node *  p, int  , int    )

static

Definition at line 419 of file write_tree.C.

References current_output.

Referenced by write_treap().

write_avl()

void write_avl	(	const vector< int > &	values,
		const string &	prefix
	)

Definition at line 283 of file write_tree.C.

References avl_print_key(), Aleph::computeHeightRec(), Aleph::count(), current_output, Aleph::destroyRec(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), output, Aleph::prefix(), Aleph::preOrderRec(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search().

Referenced by main().

write_bin()

void write_bin	(	const vector< int > &	values,
		const string &	prefix
	)

Definition at line 508 of file write_tree.C.

References bin_print_key(), Aleph::computeHeightRec(), Aleph::count(), current_output, Aleph::destroyRec(), Aleph::GenBinTree< NodeType, Key, Compare >::getRoot(), Aleph::GenBinTree< NodeType, Key, Compare >::insert(), Aleph::maps(), output, Aleph::prefix(), Aleph::preOrderRec(), and Aleph::GenBinTree< NodeType, Key, Compare >::search().

Referenced by main().

write_rand()

void write_rand	(	const vector< int > &	values,
		const string &	prefix
	)

Definition at line 466 of file write_tree.C.

References Aleph::computeHeightRec(), current_output, Aleph::destroyRec(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), output, Aleph::prefix(), Aleph::preOrderRec(), rand_print_key(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size().

Referenced by main().

write_rb()

void write_rb	(	const vector< int > &	values,
		const string &	prefix
	)

Definition at line 333 of file write_tree.C.

References Aleph::computeHeightRec(), Aleph::count(), current_output, Aleph::destroyRec(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::getRoot(), Aleph::inOrderRec(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), output, Aleph::prefix(), Aleph::preOrderRec(), rb_pos, rb_print_key(), rb_write_colors(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search().

Referenced by main().

write_splay()

void write_splay	(	const vector< int > &	values,
		const string &	prefix
	)

Definition at line 382 of file write_tree.C.

References Aleph::computeHeightRec(), Aleph::count(), current_output, Aleph::destroyRec(), GenTdSplayTree< NodeType, Key, Compare >::getRoot(), GenTdSplayTree< NodeType, Key, Compare >::insert(), Aleph::maps(), output, Aleph::prefix(), Aleph::preOrderRec(), GenTdSplayTree< NodeType, Key, Compare >::search(), and splay_print_key().

Referenced by main().

write_treap()

void write_treap	(	const vector< int > &	values,
		const string &	prefix
	)

Definition at line 424 of file write_tree.C.

References Aleph::computeHeightRec(), Aleph::count(), current_output, Aleph::destroyRec(), Aleph::Gen_Treap< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::maps(), output, Aleph::prefix(), Aleph::preOrderRec(), Aleph::Gen_Treap< NodeType, Key, Compare >::search(), and treap_print_key().

Referenced by main().

Variable Documentation

current_output

ofstream* current_output = nullptr

static

Definition at line 272 of file write_tree.C.

Referenced by avl_print_key(), bin_print_key(), rand_print_key(), rb_print_key(), rb_write_colors(), splay_print_key(), treap_print_key(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

rb_pos

int rb_pos = 0

static

Definition at line 325 of file write_tree.C.

Referenced by rb_write_colors(), and write_rb().