Trees are particular graphs often used to represent decision support, data, or complexity calculations.

## Terminology

_{1},…,a

_{k}> in which

**e**is the tag of the node and

**a**are its subtrees.

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

- the descendants of a node are the nodes of its subtrees;
- an ancestor of a node is either his father or an ancestor of his father;
- the path of a node at 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 facilitate reading:

The nodes of a tree are divided by depths (or levels). Depth 0 contains only the root, the depth 1 its threads etc. The height of a tree is the number of depths, or the size of the largest path of a node at the root.

## Definition

Given an undirected graph with n vertices, the following properties are equivalent:

- The graph is connected without cycle
- The graphe is acyclic and has n-1 edges,
- The graph is connected and has n-1 edges,
- The graph is acyclic and if one adds an edge then it exists an unique elementary cycle,
- The graph is connected and if one deletes an edge then it becomes non-connected,
- It exists an unique path between any pair of vertices

## Binary tree

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

At depth 0, there is only the root. Supose the complete binary tree has 2^{(h-1)} leaves at depth **h**. Then at depth h+1, each of these leaves becomes a father with two leaves, 2*2^{(h-1)} = 2^{h}. QED.

The number of nodes of the complete binary graph is equal to the sum of the number of leaves of the complete binary trees of lower height. We deduce that the total number of nodes is ∑_{(i=0)}^{(h-1)} 2^{i} = 2^{h} -1. Conversely, if a complete binary graph has n nodes, then its depth is from the previous formula log_{2} (n)+1.

When the tree is unbalanced, it is necessary to swap the parent vertices and the root while keeping the order of the sub-trees (see more on the search 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 sons defined by the type of tree.

## Search tree

A search tree is a data structure that can be used to represent a set of values if there is an order relationship on them. Standard operations on search trees are: inserting, deleting or searching for a value. These operations are inexpensive if the tree is balanced. To facilitate understanding, we will work on binary search trees (BST).

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 done through BST route.