Les structures arborescentes et les monceaux

Question 1

Déf : Feuille

Answer 1

Noeud qui n’a pas d’enfant

Question 2

Déf : Ancêtres d’un nœud

Answer 2

Tous les nœuds prédécesseurs jusqu’à la racine.

Question 3

Déf : Descendants d’un nœud

Answer 3

Tous les nœuds successeurs jusqu’aux feuilles accessibles par ce nœud

Question 4

Déf : Hauteur d’un nœud

Answer 4

Longueur du chemin le plus long pour atteindre une feuille.

Question 5

Déf : Hauteur de l’arbre

Answer 5

la hauteur du noeud racine

Question 6

Déf : Niveau ou profondeur d’un nœud

Answer 6

Longueur du chemin à partir de la racine.

Question 7

Déf : degré d’un nœud

Answer 7

nombre d’enfants que possède ce nœud

Question 8

Déf : degré d’un arbre

Answer 8

le degré le plus élevé de ses noeuds

Question 9

Déf : Arbre binaire

Answer 9

Arbre de degré 2

Question 10

Déf : Arbre n-aire

Answer 10

Arbre de degré n

Question 11

Conditions pour avoir un arbre binaire de recherche

Answer 11

• 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.
• Toutes les clés doivent donc être distinctes.

Question 12

Déf : Arbre binaire équilibré

Answer 12

Différence entre Hauteur sous-arbres gauche et droit | <= 1

Question 13

Déf : Le facteur d’équilibre (Height-Balanced, HB[k]) d’un arbre

Answer 13

valeur maximale de la | différence de hauteur gauche/droit | parmi tous les nœuds de l’arbre

Question 14

Hauteur max (asymptotique) d’un arbre équilibré HB[1] est en

Answer 14

O(Log n)

Question 15

Les 3 parcours typiques d’arbres

Answer 15

• Le parcours en pré-ordre
• Le parcours en post-ordre
• Le parcours en-ordre (symétrique)

Question 16

Le parcours en pré-ordre

Answer 16

(Priorité au père)

1- Visite du père
2- Visite récursive des enfants

Question 17

Le parcours en post-ordre

Answer 17

(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 ;

Question 18

Le parcours en-ordre (symétrique)

Answer 18

(Un descendant est traité AVANT le nœud et l’autre APRÈS)

1. visiter l’enfant de gauche
2. visiter la racine
3. visiter l’enfant de droite

Question 19

Particularité : Le parcours en-ordre d’un arbre binaire de recherche nous donne …

Answer 19

les éléments triés par ordre croissant!

Question 20

Avantages Implémentation arbres dans un tableau :

Answer 20

• 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

Question 21

Implémentation en tableau des arbres binairesPrincipe

Answer 21

• 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..

Question 22

Implémentation en tableau des arbres binaires : position des enfants du nœud en position j ?

Answer 22

Les enfants du nœud en position j se trouvent respectivement aux positions 2j et 2j+1 (s’ils existent)

Question 23

Preuve enfant de j sont en 2j et 2j+1

Answer 23

• 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

Question 24

Implémentation en tableau des arbres binaires : Positionnement des parents

Answer 24

• 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 ⌊𝒊/𝟐⌋