5 Trees

5.1 Examples of trees.

dir1
|---dir2
|   |---file1
|   |---file2
|   |---dir3
|---dir4
    |---file3

5.2 Advantages of trees

• "unlimited" size (like a linked lists)
• fast insertion/search by key
• possibility to create hierarchical data structure
• still easy to implement

5.3 Formal definition of trees

1. There is one "special" node in a tree, it is called the "root".
2. Every other node (not root) "C" is connected (by an edge) to some one other node "P". This node "P" is called the "parent" of "C", and "C" is called a "child" of "P".
3. All nodes are connected to the root (of course, via their parents).

1. A parent of a node, a parent of the parent and so on are called "ancestors" of the node. (Strictly speaking a node is also its own ancestor.)
2. A child of a node, a child of the child and so on are called "descendants" of the node.
3. If m₁, m₂, ..., m_k are such nodes that m₁ is the parent of m₂, m₂ is the parent of m₃, ..., m_k-1 is the parent of m_k then m₁, m₂, ..., m_k is called a "path" from m₁ to m_k in the tree. The "length" of this path is k-1, i.e. this is a number of the edges we have to "pass" going this path. (Again, strictly speaking one node is also a path with zero length.)
4. If length of a path between 2 nodes is more than 0 than the upper node is called a "proper ancestor" and the lower node is called "proper descendant".
5. Nodes that have the same parent are called "siblings".
6. The length of the longest path from a node to its descendant is "height" of the node.
7. Height of the root is called "height of the tree".
8. The length of the from the root to a node is "depth" or "level" of the node.

5.4 Operations on trees

• search
• insertion of node
• deletion of node
• deletion of subtree
• merge of 2 trees
• traversing tree
• etc. etc. etc.

5.5 Various types of trees and tree implementations

1. Common trees. These are representations of a tree when each node has unlimited possible number of children. Such trees are usually implemented as "list of lists", namely in one of 2 ways:
   • Array-of-Pointers, when each node has an array of pointers looking to its children;
   • Leftmost-Child-Right-Sibling, when each node has 2 pointers: one - to the leftmost child of it and another one - to the next right child in its sibling.
2. Binary trees. This is a special case of trees which can satisfy many tasks where a tree is needed. Binary tree is a tree where each node can have not more than 2 children. The words "binary tree" have a shortcut "B-tree".

5.6 Binary trees

typedef struct tree_node
{
	int val;
	struct tree_node* gt;
	struct tree_node* lt;
} TNODE;

{
	action A0;
	recursive call on left subtree;
	action A1;
	recursive call on right subtree;
	action A2;
}

void print_tree( TNODE* tree)
{
	if( tree == NULL)
		return;
	print_tree( tree->lt);
	printf( "[%d] ", tree->val);
	print_tree( tree->lt);
}

5.6.1 Search in B-tree

int lookup( TNODE* tree, int v)
{
	if( tree == NULL)
		return( 0);
	if( v == tree->val)
		return( 1);
	if( v < tree->val)
		return( lookup( tree->lt, v));
	else
		return( lookup( tree->gt, v));
}

int lookup( TNODE* tree, int v)
{
	TNODE* n;
	for( n = tree; n != NULL; )
	{
		if( n->val == v)
			return( 1);
		if( n->val < v)
			n = n->lt;
		else
			n = n->gt;
	}
	return( 0);
}

5.6.2 Insertion of a node to B-tree

TNODE* insert( TNODE* tree, int v)
{
	if( tree == NULL)
	{

		tree = (TNODE*)malloc( sizeof( TNODE));
		tree->val = v;
		tree->gt = tree->lt = NULL;
	}
	else if( tree->val > v)
		tree->lt = insert( tree->lt, v);
	else if( tree->val < v)
		tree->gt = insert( tree->gt, v);
	return( tree);
}

5.6.3 Deletion of a node from B-tree

TNODE* detach_min( TNODE* node, TNODE* prev0)
{
/* this function is called only if "node" has "less" children */
	TNODE* n;
	TNODE* prev = prev0;

	for( n = node; n->lt != NULL; n = n->lt)
		prev = n;
	/* now we found the node with the smallest element - "n" */
	/* and "prev" is its father */

	/* well, now n has no "lt" child, so we can force "prev" */
	/* to "forget" about it */

	/* let's handle a special case when we have reached */
	/* the minimal node immediately, i.e. it is the "gt" */
	/* child of our node */
	if( prev == prev0)
		prev->gt = NULL;
	else
		prev->lt = n->gt;

	return( n);
}

TNODE* remove_node( TNODE* tree, int v)
{
	TNODE* tmp;
	if( tree == NULL)
		return( NULL);
	if( tree->val > v)
		tree->lt = remove_node( tree->lt, v);
	else if( tree->val < v)
		tree->gt = remove_node( tree->gt, v);
	else /* OK, "tree" is the node to be deleted */
	{
		if( tree->gt == NULL)
		{
			tmp = tree;
			tree = tree->lt;
			free( tmp);
		}
		else if( tree->lt == NULL)
		{
			tmp = tree;
			tree = tree->gt;
			free( tmp);
		}
		else	/* the case of both children presented */
		{
			tmp = detach_min( tree->gt, tree);
			tmp->gt = tree->gt;
			tmp->lt = tree->lt;
			free( tree);
			tree = tmp;
		}
	}
	return( tree);
}

5.6.4 Balanced trees. AVL trees

5.6.4.1 Disadvantages of simple B-trees. The main idea of balanced trees.

5.6.4.2 The main idea of the AVL algorithm.

5.7 Exercise 5

5.8 Not binary trees

5.8.1 Children vector (Array-of-Pointers)

5.8.2 Trie

• he
• hers
• his
• she

typedef struct trie_node
{
	char			letter;
	int			end_of_word;
	struct trie_node*	children[26]; /* 0 - a, 1 - b, ... */
} NODE;

5.8.3 Sibling

typedef struct LCRS_node
{
	int			val;
	struct LCRS_node*	leftmostChild;
	struct LCRS_node*	rightSibling;
} LCRS_NODE;

int lookup( LCRS_NODE* tree, int v)
{
	if( tree == NULL)
		return( 0);
	if( tree->val == v)
		return( 1);
	if( lookup( tree->leftmostChild, v))
		return( 1);
	return( lookup( tree->rightSibling, v));
}

5.9 Traversing tree

F(n)
{
	action A0;
	F( c1);
	action A1;
	F( c2);
	action A2;
	...
	F( ck);
	action Ak;
}

5.9.1 Preorder

{
	action on the node;
	recursive call on subtrees;
}

void preorder_print( LCRS_NODE* tree)
{
	LCRS_NODE* n;

	if( tree == NULL)
		return;
	/* our action - to print the value */
	printf( "%d\n", tree->val);
	/* now the same for all children */
	for( n = tree->leftmostChild; n != NULL; n = n->rightSibling)
		preorder_print( n);
}

5.9.2 Postorder

{
	recursive call on subtrees;
	action on the node;
}

void postorder_print( LCRS_NODE* tree)
{
	LCRS_NODE* n;

	if( tree == NULL)
		return;
	/* first the same for all children */
	for( n = tree->leftmostChild; n != NULL; n = n->rightSibling)
		postorder_print( n);
	/* our action (to print the value) - after passing children */
	printf( "%d\n", tree->val);
}

5.9.3 Inorder

{
	recursive call on left subtree;
	action on the node;
	recursive call on right subtree;
}

5.10 Important tree applications

5.10.1 Expression trees

5 + ( 7 - 3) * 2

int eval( NODE* tree)
{
	if( no children)
		return( tree->val);
	switch( tree->operation)
	{
	case OP_PLUS:
		return( eval( tree->left) + eval( tree->right));
	case OP_MINUS:
		return( eval( tree->left) - eval( tree->right));
	case OP_MULTIPLY:
		return( eval( tree->left) * eval( tree->right));
	case OP_DIVIDE:
		return( eval( tree->left) / eval( tree->right));
	}
}

5.10.2 Syntax trees (Parse trees)

5.10.3 Decision making trees

if(some condition)
	do something
else
	do something else
etc.