deway.C File Reference

Dewey ("deway") numbering for tree nodes (path-based hierarchical addresses). More...

#include <iostream>
#include <tclap/CmdLine.h>
#include <tpl_binNodeUtils.H>
#include <tpl_tree_node.H>
#include <generate_tree.H>
#include <ah-errors.H>

Include dependency graph for deway.C:

Go to the source code of this file.

Functions
void	deway (Tree_Node< int > *p, int prefix[], const int &len, const size_t &dim)
	Recursively compute and print Deway numbering for a tree node.
void	deway (Tree_Node< int > *p, const int &h)
	Print Deway numbering for a forest.
template<class Node >
static void	printNode (Node *node, int, int)
int	random_int (int l, int r)
	Generate a random integer in range [l, r].
BinNode< int > *	random_tree (int l, int r)
	Recursively build a random binary search tree.
int	main (int argc, char *argv[])

Detailed Description

Dewey ("deway") numbering for tree nodes (path-based hierarchical addresses).

Overview

This example demonstrates Dewey / Deway numbering: assign each node in a rooted tree a hierarchical address that encodes its full path from the root.

Conceptually, each node address is a sequence of child indices. For instance:

• root: empty address
• first child: 0
• second child of the first child: 0.1

Data model used by this example

This file builds and prints multiple representations:

• a random binary search tree using BinNode<int>
• a converted forest / general tree using Tree_Node<int>

Then it prints the Dewey numbering on the forest.

Usage / CLI

This example uses TCLAP:

• --nodes / -n <int>: number of nodes (default: 10).
• --seed / -s <unsigned>: RNG seed (0 means use time(); default: 0).
• --help: show help.

./deway
./deway --nodes 20
./deway --nodes 30 --seed 42
./deway --help

Algorithm

1. Build a random BST by recursive insertion in a numeric range.
2. Convert the binary tree to a forest (bin_to_forest).
3. Fix the is_root flag for sibling roots created by the conversion.
4. Print traversals and finally compute and print Dewey numbers.

Complexity

• Tree generation and traversals are linear in the number of nodes: O(n).
• Dewey numbering visits each node once: O(n).

Pitfalls and edge cases

• Dewey addresses are not stable under insertions/removals: changing sibling order changes addresses.
• The initial tree is a BST built from random values; its height can vary.

References / see also

• generate_forest.C (related forest utilities)
• tpl_tree_node.H (n-ary tree nodes)

Author

Leandro Rabindranath León

Definition in file deway.C.

Function Documentation

deway() [1/2]

void deway	(	Tree_Node< int > *	p,
		const int &	h
	)

Print Deway numbering for a forest.

Parameters

p	Root of the first tree in the forest
h	Height of the original binary tree (used to size prefix array)

Definition at line 150 of file deway.C.

References deway(), dim(), Aleph::Tree_Node< T >::get_right_sibling(), h, and Aleph::prefix().

deway() [2/2]

void deway	(	Tree_Node< int > *	p,
		int	prefix[],
		const int &	len,
		const size_t &	dim
	)

Recursively compute and print Deway numbering for a tree node.

Parameters

p	Current node
prefix	Array storing the current Deway address
len	Current depth in the tree
dim	Maximum dimension of prefix array

Definition at line 117 of file deway.C.

References ah_overflow_error_if, deway(), dim(), Aleph::Tree_Node< T >::get_key(), Aleph::Tree_Node< T >::get_left_child(), Aleph::Tree_Node< T >::get_right_sibling(), Aleph::maps(), and Aleph::prefix().

Referenced by Aleph::__generate_tree(), Aleph::__search_deway(), deway(), deway(), Aleph::generate_tree(), main(), and Aleph::search_deway().

main()

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

Definition at line 198 of file deway.C.

References Aleph::areEquivalents(), Aleph::computeHeightRec(), Aleph::destroy_forest(), Aleph::destroyRec(), deway(), Aleph::forest_postorder_traversal(), Aleph::forest_preorder_traversal(), Aleph::Tree_Node< T >::get_right_sibling(), Aleph::inOrderRec(), Aleph::maps(), Aleph::preOrderRec(), printNode(), and random_tree().

printNode()

template<class Node >

static void printNode ( Node *  node, int  , int    )

static

Definition at line 166 of file deway.C.

References Aleph::maps().

Referenced by main().

random_int()

int random_int	(	int	l,
		int	r
	)

Generate a random integer in range [l, r].

Definition at line 174 of file deway.C.

References l, and Aleph::maps().

Referenced by random_tree().

random_tree()

BinNode< int > * random_tree	(	int	l,
		int	r
	)

Recursively build a random binary search tree.

Definition at line 185 of file deway.C.

References KEY, l, Aleph::LLINK(), Aleph::maps(), random_int(), random_tree(), Aleph::RLINK(), and root().

Referenced by main(), and random_tree().