C5 : Arbres
💚 Vocabulaire
Arbres
Structure de donnée
Un arbre est une structure de données hiérarchique.
Ensemble de nœuds
Un arbre est constitué de nœuds.
Les nœuds peuvent :
- - avoir des nœuds enfants, aussi appelés sous-arbres ;
- - ne pas avoir d'enfant (c'est-à-dire avoir des sous-arbres vides), le nœud est alors appelé une feuille.
Le nœud qui n'a pas de parent est appelé nœud racine ou simplement la racine.
Stockage d'informations
Les nœuds peuvent tous (racine, nœuds avec enfants ou feuilles) stocker de l'information.
Arbres binaires
Définition d'un arbre binaire
Un arbre binaire est un cas particulier d'arbre où chaque nœud peut :
- - soit être vide ;
- - soit avoir exactement deux sous-arbres (deux nœuds enfants) : le sous-arbre de gauche et le sous-arbre de droite.
Le nœud de départ d'un arbre est appelé la racine.
Lorsque les deux sous-arbres sont des arbres vides, le nœud est appelé une feuille.
Grandeurs caractéristiques d'un arbre binaire
Taille d'un arbre
La taille d'un arbre est le nombre de nœuds de cet arbre.
Profondeur d'un nœud
La profondeur d'un nœud est le nombre de nœuds du chemin qui va de la racine à ce nœud.
Propriété : La profondeur du nœud racine est égale à 1.
Hauteur d'un arbre
La hauteur d'un arbre est le plus grand nombre de nœuds rencontrés en partant de la racine et en allant jusqu'aux feuilles.
Propriété : L'arbre vide à une hauteur de 0.
Propriété : La hauteur d'un arbre est la plus grande profondeur de ces nœuds (non vides).
Remarque : Il existe une autre façon de définir la profondeur d'un nœud, en prenant une profondeur égale à 0 pour la racine.
Relation entre la hauteur et la taille d'un arbre binaire
Relation : \(hauteur \le taille \le 2^{hauteur}-1\)
Démonstration (à connaitre) :
• L'arbre binaire de hauteur h et dont la taille est la plus petite est tel que : \(taille = hauteur\)
Donc \(taille \ge hauteur\)
• L'arbre binaire de hauteur h et dont la taille est la plus grande est tel que : \(taille = 2^0 + 2^1 + ... + 2^{hauteur-1} = 2^{hauteur}-1\)
Donc \(taille \le 2^{hauteur}-1\)
CQFD
Parcours d'un arbre binaire
Parcours en profondeur d'abord
Dans un parcours en profondeur d'abord, l'un des deux sous-arbres est entièrement exploré avant que l'exploration de l'autre commence.
On distingue trois cas :
- • Le parcours préfixe : la valeur du nœud est récupérée avant l'exploration du sous-arbre de gauche et du sous-arbre de droite.
- • Le parcours infixe : le sous-arbre de gauche est exploré d'abord, puis la valeur du nœud est récupérée, puis le sous-arbre de droite est exploré.
- • Le parcours suffixe : le sous-arbre de gauche et le sous-arbre de droite sont explorés puis la valeur du nœud est récupérée.
Parcours en largeur d'abord
Dans un parcours en largeur d'abord, l'arbre est parcouru étage par étage.
Arbres binaires de recherche (ABR)
Un arbre binaire de recherche (ABR) est un arbre binaire tel que :
- - les valeurs du sous-arbre de gauche sont inférieures ou égales à la valeur de la racine ;
- - les valeurs du sous-arbre de droite sont strictement supérieures à la valeur de la racine ;
- - les sous-arbres de gauche et de droite sont eux-mêmes des arbres binaires de recherche.