Contenus

Toggle## Trees and arboresences

Trees and arborescences are particular graphs often used to represent thehelp with the decision, data, or for calculating the complexity.

*one father and one*, except a node which we call

*root*. If a node

**p**is the

*father*of the knot

**f**, so

**f**is a

*son*of

**p**; if

**f**has no son, so she is a

*sheet*. It is possible to store any type of information in nodes or links.

## Terminology

*label*and his

*sub-trees*. It is therefore possible to represent a tree by a tuple <e,a

_{1},…,To

_{k}> in which

**e**is the node label and

**To**are its subtrees.

_{i}For example, calculators organize the expressions math depending on the priority of the operators and their depth: (y/2 – x)*(75+z) will be represented by <*,<-,,>,>,<+,,>>. The operation is then done by a particular traversal of the tree:

- the descendants of a node are the nodes of its subtrees;
- an ancestor of a node is either its father or an ancestor of its father;
- the path from a node to the root is made up of all its ancestors;
- the brother of a node is a son of his father other than himself.

A tree is often represented by a graph to make it easier to read:

The nodes of a tree are distributed by *depths* (or levels). The depth 0 contains only the root, the depth 1 its children etc. The *height* of a tree is the number of depths, or the size of the longest path from a node to the root.

## Definition: graph theory

Given an undirected graph comprising **not** vertices, the following properties are equivalent:

- The graph is connected and without cycle,
- The graph is cycleless and has n-1 edges,
- The graph is connected and admits n-1 edges,
- The graph is cycleless, and by adding an edge, then we create one and only one elementary cycle,
- The graph is connected, and by removing any edge it is no longer connected,
- There is one chain and only one between all pairs of vertices.

A tree is a directed graph without circuit admitting a root such that for any other vertex there is a unique path from the root to this vertex. A tree has properties similar to a tree.

## Binary tree

Let us determine the total number of leaves and nodes of a complete binary tree.

At depth 0 there is a leaf, the root. Suppose the complete binary tree has 2^{(h-1)} leaves up to the task **h**. So, at the height h + 1, each of these leaves becomes a node with two threads, so we have a number of leaves of 2 * 2^{(h-1)} = 2^{h}. CQFD.

In addition, the number of nodes of the complete binary graph is equal to the sum of the leaf number of the complete binary trees of lower height. We deduce that the total number of node is ∑_{(i = 0)}^{(h-1)} 2^{i} = 2^{h} -1. Conversely, if a complete binary graph has n nodes, then its height is according to the preceding formula log_{2} (n) +1. We deduce that any binary tree has at least log height_{2} (n) +1.

The indicator on the vertices shows the difference between the height of the left subtree and the height of the right subtree.

When the tree is unbalanced, it is then necessary to swap the parent vertices and the root while maintaining the order of the sub-trees (see the continuation on research trees).

We can enlarge the definition on trees of higher degree (ternary tree etc). Only the coefficient 2 is modified according to the number of wires defined by the type of shaft.

## Research tree

A search tree is a data structure making it possible to represent a set of values if we have an order relation on them. The standard operations on search trees are: inserting, deleting or finding a value. These operations are inexpensive if the shaft is balanced. In order to facilitate understanding, we will work on binary search trees (ABR).

**E**provided with an order relation, and either

**TO**a binary tree. The tree

**TO**is an ABR of

**E**if for any node

**p**of

**TO**, the value of

**p**is strictly greater than the values of its left subtree, and is strictly smaller than the values in its right subtree; provided the values are unique. The values are called

*keys*.

The smallest value is the last left descendant of the root, and the largest is the last right descendant of the root. Other logical criteria can be deduced from the definition:

The three actions are then carried out through ABR routes.