Arbres 3 hauteur⚓︎
Définition d'un arbre⚓︎
Un arbre est un ensemble d'éléments appelés nœuds, parmi lesquels on en distingue un appelé racine, avec une structure hiérarchique définie par une relation de parenté:
- un nœud seul est un arbre qui a pour racine ce nœud;
- avec un nœud \(n\) et \(k\) arbres de racines respectives \(n_1, n_2, ..., n_k\), on construit un nouvel arbre de racine \(n\) qui est le parent des nœuds \(n_1, n_2, ..., n_k\).
Chaque nœud, excepté la racine, a donc exactement un parent.
On suppose qu'il n'y a pas d'ordre sur les sous-arbres et on dit alors que l'arbre n'est pas ordonné.
Représentation d'un arbre⚓︎
Exemple du même arbre représenté de deux manières différentes. Les huits nœuds sont représentés par des cercles:
graph TB
r(( )) --- n1(( ))
r(( )) --- n2(( ))
r(( )) --- n3(( ))
n1(( )) --- n4(( ))
n3(( )) --- n5(( ))
n3(( )) --- n6(( ))
n3(( )) --- n7(( ))
r1(( )) --- n12(( ))
r1(( )) --- n13(( ))
r1(( )) --- n11(( ))
n13(( )) --- n15(( ))
n13(( )) --- n16(( ))
n13(( )) --- n17(( ))
n11(( )) --- n14(( ))Les nœuds sont numérotés de 0 à 7:
graph TB
r((0)) --- n1((1))
r --- n2((2))
r --- n3((3))
n1 --- n4((4))
n3 --- n5((5))
n3 --- n6((6))
n3 --- n7((7))Implémentation⚓︎
Les \(n\) nœuds d'un arbre sont numérotés de \(0\) à \(n-1\). L'ordre de numérotation n'a aucune importance. Lorsque les nœuds ont été numérotés, l'arbre peut être implémenté par un tableau dans lequel les indices représentent les numéros des nœuds. La valeur à l'indice \(i\) représente le numéro (et l'indice) du parent du nœud \(i\).
Si un élément à l'indice \(i\) vaut \(i\), cela signifie que le nœud numéro \(i\) n'a pas de parent: c'est donc la racine. La racine est donc l’unique nœud ayant une valeur égale à son indice.
Par exemple, l'arbre dessiné ci-dessus est représenté par le tableau [0, 0, 0, 0, 1, 3, 3, 3].
Le même arbre peut être implémenté par des tableaux différents selon l'ordre de numérotation choisi. Les tableaux [1, 2, 2, 2], [0, 0, 0, 1] et [3, 3, 1, 3] correspondent aux numérotations choisies dans les trois représentations ci-dessous:
graph TB
r((2)) --- n1((1))
r --- n2((3))
n1 --- n3((0))
r1((0)) --- n11((1))
r1 --- n12((2))
n11 --- n13((3))
r2((3)) --- n21((0))
r2 --- n22((1))
n22 --- n23((2))Un chemin est une suite de nœuds telle que chaque nœud est le parent du nœud suivant. La longueur d'un chemin est le nombre d'arêtes parcourues le long du chemin.
La profondeur d'un nœud est la longueur du chemin (unique) allant de la racine jusqu'à ce nœud.
La hauteur d'un arbre est la plus grande des profondeurs.
Vocabulaire
-
La profondeur ou le niveau de la racine est 0.
-
La plus grande profondeur ou le plus grand niveau d'une feuille est 3.
-
La hauteur de la racine est 3.
-
La hauteur d'une feuille peut être 0, 1 ou 2.
-
La hauteur de l'arbre est 3. C'est à la fois:
-
la plus grande profondeur
-
le plus grand niveau
-
la plus grande hauteur
-
la hauteur de la racine
-
Afin d'obtenir la hauteur, on choisit de calculer la plus grande profondeur.
Il est demandé de compléter la fonction profondeurs qui prend en paramètre un arbre et renvoie un dictionnaire dont les clés sont les numéros des nœuds, la valeur associée à chaque nœud étant sa profondeur.
Un algorithme qui calculerait la profondeur de chaque nœud, l'un après l'autre, ne serait pas efficace. Si lors du parcours d'un chemin, on rencontre \(k\) nœuds, on peut obtenir la profondeur de chacun des \(k\) nœuds en un seul passage. Pour cela, on mémoïse les résultats dans un dictionnaire.
Compléter ensuite la fonction hauteur qui prend en paramètre un arbre et renvoie la hauteur de l'arbre. Cette fonction utilise la fonction profondeurs puis une recherche de maximum.
Exemples
>>> profondeurs([1, 2, 2, 2])
{0: 2, 1: 1, 2: 0, 3: 1}
>>> hauteur([1, 2, 2, 2])
2
>>> profondeurs([1, 1])
{0: 1, 1: 0}
>>> hauteur([1, 1])
1
>>> hauteur([0, 0, 0, 0, 1, 3, 3, 3])
3
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)