Trees and arboresences
Trees and trees are special graphs often used to represent decision support, data, or for calculating complexity.
For example, calculators organize mathematical expressions according to operator precedence and depth: (y / 2 - x) * (75 + z) will be represented by <*, <- ,,>,>, <+ ,, >>. The operation is then done by a particular path 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 facilitate reading:
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:
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.
Let us determine the total number of leaves and nodes of a complete binary tree.
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.
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).
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.