Les structures arborescentes et les monceaux Flashcards
Déf : Feuille
Noeud qui n’a pas d’enfant
Déf : Ancêtres d’un nœud
Tous les nœuds prédécesseurs jusqu’à la racine.
Déf : Descendants d’un nœud
Tous les nœuds successeurs jusqu’aux feuilles accessibles par ce nœud
Déf : Hauteur d’un nœud
Longueur du chemin le plus long pour atteindre une feuille.
Déf : Hauteur de l’arbre
la hauteur du noeud racine
Déf : Niveau ou profondeur d’un nœud
Longueur du chemin à partir de la racine.
Déf : degré d’un nœud
nombre d’enfants que possède ce nœud
Déf : degré d’un arbre
le degré le plus élevé de ses noeuds
Déf : Arbre binaire
Arbre de degré 2
Déf : Arbre n-aire
Arbre de degré n
Conditions pour avoir un arbre binaire de recherche
- 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 nœuds de son sous-arbre droit.
- > aux clés de tous les noeuds de son sous-arbre gauche.
- Toutes les clés doivent donc être distinctes.
Déf : Arbre binaire équilibré
Différence entre Hauteur sous-arbres gauche et droit | <= 1
Déf : Le facteur d’équilibre (Height-Balanced, HB[k]) d’un arbre
valeur maximale de la | différence de hauteur gauche/droit | parmi tous les nœuds de l’arbre
Hauteur max (asymptotique) d’un arbre équilibré HB[1] est en
O(Log n)
Les 3 parcours typiques d’arbres
- Le parcours en pré-ordre
- Le parcours en post-ordre
- Le parcours en-ordre (symétrique)
Le parcours en pré-ordre
(Priorité au père)
1- Visite du père
2- Visite récursive des enfants
Le parcours en post-ordre
(Les descendants d’un nœud sont traités avant lui)
1- visiter récursivement les enfants : v1, v2, …, vk 2.
2- visiter la racine r ;
Le parcours en-ordre (symétrique)
(Un descendant est traité AVANT le nœud et l’autre APRÈS)
- visiter l’enfant de gauche
- visiter la racine
- visiter l’enfant de droite
Particularité : Le parcours en-ordre d’un arbre binaire de recherche nous donne …
les éléments triés par ordre croissant!
Avantages Implémentation arbres dans un tableau :
- Les nœuds sont insérés dans un tableau
- Aucune utilisation de pointeurs
- la position des enfants est obtenu par une opération
arithmétique très simple - Utilisé pour les monceaux/tas
Implémentation en tableau des arbres binairesPrincipe
- Dimensionner un tableau avec 2^h cases par niveau h.
- Les nœuds absents ont leur case de réservé
- Valeur du nœud racine = 1, puis ses enfant 2 et 3 etc..
Implémentation en tableau des arbres binaires : position des enfants du nœud en position j ?
Les enfants du nœud en position j se trouvent respectivement aux positions 2j et 2j+1 (s’ils existent)
Preuve enfant de j sont en 2j et 2j+1
- Rappeler le 1er nœud du niveau h est 2^h
- Poser ième nœud du niveau h est à la position 2^h +(i-1) noté j
- Les enfants de ce nœud sont à la position 2i-1 et 2i du niveau h+1
- Donc L’indice de l’enfant gauche est alors = 2^h+1 + (2i-1) – 1 = 2(2^h + (i-1)) = 2j
- L’indice de l’enfant droit est alors = 2j+1
Implémentation en tableau des arbres binaires : Positionnement des parents
- Les enfants du nœud en position j se trouvent aux positions 2j et 2j+1 s’ils existent.
- Alors le parent d’un œud en position i se trouve en position ⌊𝒊/𝟐⌋
