Please enable JavaScript.
Coggle requires JavaScript to display documents.
Les structures arborescentes et les monceaux (Terminologie (Ancêtres d’un…
Les structures arborescentes et les monceaux
Terminologie
Ancêtres d’un noeud
Tous les noeuds prédécesseurs jusqu’à la racine
Descendants d’un noeud
Tous les noeuds successeurs jusqu’aux feuilles
accessibles par ce noeud
Feuille
Un noeud qui n’a pas d’enfants
Hauteur d’un noeud
Longueur du chemin le plus long pour atteindre une feuille
Racine
Le noeud qui n’a pas de prédécesseur
Hauteur de l’arbre
La hauteur du noeud racine
Enfant(s) d’un noeud
Les noeuds immédiatement successeurs du noeud
Niveau ou profondeur d’un noeud
Longueur du chemin à partir de la racine
Parent d’un noeud
Le noeud immédiatement prédécesseur
Types d'arbes
Arbre binaire
Ses noeuds ont 2 enfant max
Arbre n-aire
Ses noeuds ont n enfant max
Arbre dégénéré
Ses noeuds ont 1 enfant max
ex: Liste simplement chaîné
Arbre binaire de recherche
:warning: Un arbre binaire est dit de recherche si chaque noeud
possède une clé dont les valeurs satisfont la propriété
suivante:
Pour tout noeud de l’arbre la valeur de sa clé est:
'>' aux clés de tous les noeuds de son sous-arbre gauche
'<' aux clés de tous les noeuds de son sous-arbre droit
Toutes les clés doivent être distinctes
Tout ajout ou suppression de noeud doit donc maintenir
cette propriété vraie
Le facteur d’équilibre pour arbres binaires de recherche
Un arbre binaire est dit équilibré lorsque, pour tout noeud, la différence entre les hauteurs de ses sous-arbres gauche et droit est ≤ 1.
Le facteur d’équilibre (Height-Balanced, HB[k]) d’un arbre est donné par la valeur maximale de cette différence de hauteur parmi tous les noeuds de l’arbre
Un arbre équilibré de n noeuds possède:
Une hauteur en
O(Log n)
:timer_clock: La recherche d’un élément se fera donc en temps O(Log n)
Arbre d’expression
Arbre dont les feuilles sont des opérandes
(variables ou constantes) et dont les noeuds internes sont des opérateurs
Un opérateur unaire possède un enfant
Un opérateur binaire possède deux enfants
Arbre complet
Un arbre de degré n est dit complet lorsque tous
ses niveaux, à l’exception du dernier, possède un nombre maximal de noeuds. Le dernier niveau est, quant à lui, partiellement rempli de gauche à droite, sans trou.
Parcours d’arbre
Post-ordre
:warning: Priorité aux fils (post-ordre)
visiter récursivement les enfants : v1, v2, …, vk
visiter la racine r
:warning: Dans le parcours post-ordre, les descendants d’un noeud sont traités avant lui
Symétrique
visiter la racine r
visiter l’enfant de droite (v2)
visiter l’enfant de gauche (v1)
:warning: Dans le parcours en ordre, un descendant est traité avant le noeud, l’autre est traité après lui
:warning: Est défini seulement pour les arbres binaires
Le parcours en-ordre d’un arbre binaire de recherche nous donne les éléments triés par ordre croissant!
Pré-ordre
:warning: Priorité au père (pré-ordre)
visiter la racine r
visiter récursivement les enfants : v1, v2, …, vk
:warning: Dans le parcours pré-ordre, les descendants d’un noeud sont traités après lui
Implémentation des arbres
Implémentation dans un tableau
La position des enfants est obtenu par une opération
arithmétique très simple
Utilisé pour les monceaux/tas (objet de ce chapitre)
Aucune utilisation de pointeurs
Les noeuds sont insérés dans un tableau
:check: Aucun espace utilisé pour stocker des pointeurs
:check: Simplicité pour visiter les enfants
:check: L’espace pour insérer un noeud est déjà disponible
:red_cross: Espace perdu pour les trous
:red_cross: Ré-allocation d’un tableau plus grand si la position du noeud que l’on désire ajouter déborde du tableau
Les enfants du noeud en position j se trouvent
respectivement aux positions 2j et 2j+1 (s’ils existent)
en débutant par h=0 (la racine), on réserve 2h cases mémoires consécutives pour stocker les noeuds du niveau h de gauche à droite
Implémentation par chaînage
Chaque noeud pointe sur ses enfants (un pointeur par enfant)
Utilisé pour les arbres binaires de recherche (prochain
chapitre)
Tas
Utilisée pour la mise en oeuvre
des files de priorité
Ex: File d’impression de fichiers
Ex: Utilisation pour algorithmes glouton (ex: Dijkstra)
:warning: Une file de priorité doit supporter efficacement les opérations suivantes
Enlever un item ayant la priorité la plus élevée
Ajouter un item à la file de priorité
Trouver un item avec la priorité la plus élevée
Le tas est une structure intermédiaire utilisée par l’algorithme du tri
par tas (« heapsort »)
:warning:Un arbre binaire dont chaque noeud contient une valeur (ou une clé) est appelé un tas lorsque ces deux propriétés sont satisfaites:
La valeur d’un noeud est toujours supérieure où égale à celle
de ses enfants (propriété du tas_max) (la valeur de la racine est donc la valeur maximale du tas)
L’arbre binaire est complet: tous les niveaux sont remplis
excepté (possiblement) le dernier et, dans ce cas, les noeuds
manquant sont tous à droite
Insertion dans un tas
:timer_clock: :timer_clock: ⎣log2(n+1)⎦ comparaisons
Analyse HeapButtomUp
:timer_clock: en Θ(n) dans tous les cas
Enlever la racine d'un tas
:timer_clock: au plus O(log n) comparaisons
Tri par tas
:timer_clock: en Θ(n log n) en pire cas et en Θ(n) en
meilleur cas
