#include <et-forest.h>

Collaboration diagram for et_node:

Data Fields
void *	data
int	dfs_num_in
int	dfs_num_out
struct et_node *	father
struct et_node *	son
struct et_node *	left
struct et_node *	right
struct et_occ *	rightmost_occ
struct et_occ *	parent_occ

Detailed Description

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; see the file COPYING3. If not see http://www.gnu.org/licenses/. This package implements ET forest data structure. Each tree in the structure maintains a tree structure and offers logarithmic time for tree operations (insertion and removal of nodes and edges) and poly-logarithmic time for nearest common ancestor.

ET tree stores its structure as a sequence of symbols obtained by dfs(root)

dfs (node) { s = node; for each child c of node do s = concat (s, c, node); return s; }

For example for tree

4 5

the sequence is 1 2 4 2 5 3 1 3 1 4 1.

The sequence is stored in a slightly modified splay tree. In order to support various types of node values, a hashtable is used to convert node values to the internal representation. The node representing the node in an et tree.