Les arbres.

Notion d'arbres.

Remarque

Un arbre est un graphe non-orienté, connexe et sans cycle où on choisit un sommet appelé racine.

Choisir la racine va entraîner une orientation implicite.

Définition

Dans un arbre, les sommets sont des nœuds, les arretes des branches.

Définition

La valeur associée à un nœud est sa clef.

Définition

Les sommets voisins du sommet racines sont ses fils et la racine est le père de ses fils. Ensuite si on prend un des fils, ses voisins (autre que son père) deviennent ses fils et il devient le père de ses fils et ainsi de suite.

Définition

Si deux nœuds ont le même père alors ils sont frères.

Exemple

Le nœud 0 est la racine.
Les nœuds 1 et 2 sont les fils du nœuds 0, les deux sont frères.
Les nœuds 3 et 4 sont les fils du nœud 1.

Définition

Si un nœud n'a pas de fils alors c'est une feuille.

Définition

La distance entre deux nœuds est la distance du plus court chemin menant les deux nœuds.

Exemple

La distance entre 0 et 3 est 2, la distance entre 3 et 2 est 1.

Définition

La profondeur d'un nœud est la distance de ce nœuds à la racine.

Exemple

La profondeur de 0 est 0.
La profondeur de 1 et de 2 est 1.
LA profondeur de 3 et de 4 est 2.

Définition

La hauteur d'un arbre est la profondeur maximale d'un nœud de l'arbre.

Ainsi un arbre ne comportant que la racine est de hauteur 0 (mais une autre convention le fixe à 1). Par convention la hauteur d'un arbre vide est -1.

Définition

La taille d'un arbre est le nombre de nœuds de l'arbre.

Exercice

Dire si les graphes suivants sont des arbres, si oui les enraciner avec la racine 0 puis donner la taille et la hauteur.
Dans l'arbre suivant (enraciner en 0) :

Donner :
- La taille de l'arbre.
- La hauteur de l'arbre.
- Les feuilles.
- Le(s) frères de 5.
- Les fils de 2.
- Le père de 9.

Arbre binaire.

Définition

Un arbre est dit binaire, si chaque noeuds de l'arbre à au plus deux fils.

Définition

Pour un arbre binaire on nomme les fils en fils gauche et/ou fils droits. Pour chaque noeuds, le graphe formé par son fils droits (resp gauche) et ses descendants est dit sous arbre droit. (resp gauche)

Exercice

Si un arbre binaire à une hauteur h alors donner une majoration de sa taille.

Si un arbre à une taille de h donner un encadrement de sa hauteur.

Définition

Un arbre est équilibré si pour chaque nœud la hauteur du sous arbre droit diffère au plus de un de la hauteur du sous arbre gauche.

Si la hauteur est toujours la même l'équilibre est total sinon il est partiel.

Ce qui veut dire que tous les niveaux de l'arbre sont complets sauf éventuellement le dernier (pour l'équilibre partiel).

Les arbres équilibrés sont les "meilleurs", ils vont optimiser les algorithmes sur les arbres.

Exemple

Partiellement équilibré

Parfaitement équilibré

non équilibré

Exercice

Soit a la racine d'un arbre, sa clef est 2.
Soit b le fils droit de a de clef 3.
Soit c le fils gauche de b de clef 4.
Soit d le fils gauche de a de clef 1.
Soit e le fils droit de b de clef 1.
Soit f le fils droit de e de clef 4.
Soit g le fils gauche de e de clef 2.

Arbre binaire de recherche.

Définition

Un arbre est dit binaire de recherche, si il est binaire et si la clef d'un nœud supérieur ou égal à tous les descendants gauches et inférieur ou égal à tous les descendants droits.

Exemple

Arbre binaire de recherche

Arbre binaire mais pas de recherche.