(+212) 616 374 790 contact@developpement-informatique.com
| Connexion
MPSI, PCSI et la PTSI MP, PSI et la TSI Les arbres

Propriétés des arbres binaires

27 Apr 2019 27 Apr 2019 13239 vues ESSADDOUKI Mostafa 4 min de lecture
Complexité algorithmique
1 Introduction à l'analyse des algorithmes 2 Notations asymptotiques 3 Opérations élémentaires et modèles de coût 4 Complexité temporelle et spatiale 5 Méthode de comptage des pas 6 Méthode de comptage des pas pour les boucles
Diviser pour régner & algorithmes de tri
7 Rappel sur l'approche récursive 8 Diviser pour régner 9 la recherche dichotomique 10 Tri par fusion 11 Tri rapide 12 Analyse des fonctions récursives
Les arbres binaires
13 Introduction aux arbres binaires 14 Définitions récursives des arbres 15 Propriétés des arbres binaires 16 Types d'arbre binaire 17 Parcours en profondeur des arbres binaires 18 Parcours en largeur des arbres binaires 19 Exercices corrigés sur les arbres - TD 1 20 Exercices corrigés sur les arbres - TD 2 21 Exercices corrigés sur les arbres - TD 3 22 DS - Arbres binaires de recherche équilibrés (AVL) 23 DS - Codage de Huffman - Compression de données
Algorithmes gloutons
24 Introduction aux algorithmes gloutons 25 Problème de la sélection d'activités 26 Problème de séquencement des tâches 27 Problème du Sac à Dos fraction
Programmation dynamique
28 Introduction à la programmation dynamique 29 Le concept de sous-structure optimale 30 Le concept de sous-problèmes superposés 31 Méthodes de la programmation dynamique 32 Différence entre la programmation dynamique, l'approche diviser pour régner, et les algorithmes gloutons 33 Calculer les nombres de catalan en C++ et Python 34 Calculer le coefficient binomial 35 Le nombre de façons pour construire un mur de dimension 4*N 36 Défi de conversion de mots 37 Décomposition de phrases à partir d'un dictionnaire 38 La collection de pièces dans un labyrinthe 39 Nombre de façons de regrouper les étudiants 40 Compter tous les chemins possibles dans une grille MxN
Méta heuristique
41 Algorithmes heuristiques et métaheuristiques 42 Algorithme de Recuit simulé 43 Algorithme Colonies de fourmis
Théorie des graphes
44 Introduction et notions fondamentales 45 Chemins, cycles et connexité 46 Représentations des graphes 47 Parcours de graphes 48 Algorithme de Dijkstra 49 Algorithme A* 50 Algorithme de Bellman-Ford 51 Algorithme Floyd-Warshall 52 Coloration des graphes
Base de données et SQL
53 Introduction au langage SQL 54 Concepts de base de SGBDR 55 Syntaxes de différentes instructions SQL 56 Création et suppression d'une base de données 57 Opérateurs SQL 58 Les contraintes en SQL 59 Création et suppression des tables en SQL 60 Insertion et modifications des enregistrements 61 Extraction des données - SELECT 62 Filtrer les données - WHERE 63 Recherche de motifs - LIKE 64 Trier les données - ORDER BY 65 Les jointures en SQL - JOIN 66 Fonctions d'agrégation en SQL - SUM, COUNT, AVG, MIN et MAX 67 Organiser des données identiques en groupes - GROUP BY et HAVING 68 Les sous-requêtes en SQL 69 Les fonctions SQL de manipulation de date 70 DS - langage SQL 71 Exercices corrigés de langage SQL
Introduction à l'intelligence artificielle
Introduction à la théorie des jeux
Préparation aux concours
72 Réseau de distribution d'eau 73 Arbre d'expression arithmétique 74 Exploration d'une grotte souterraine

Propriétés des arbres binaires

Objectifs

Maîtriser les relations fondamentales entre le nombre de nœuds, la hauteur et le nombre de feuilles dans un arbre binaire.

Nombre maximum de nœuds par niveau

Théorème Le nombre maximum de nœuds au niveau \(l\) d'un arbre binaire est : \[ \boxed{2^{\,l-1}} \]

Le niveau correspond au nombre de nœuds sur le chemin de la racine jusqu'au nœud considéré (racine incluse). Le niveau de la racine est donc \(1\).

Illustration

  • Niveau 1 (racine) : \(2^{0} = 1\) nœud maximum
  • Niveau 2 : \(2^{1} = 2\) nœuds maximum
  • Niveau 3 : \(2^{2} = 4\) nœuds maximum
  • Niveau \(l\) : \(2^{l-1}\) nœuds maximum

Nombre maximum de nœuds pour une hauteur donnée

Théorème Le nombre maximum de nœuds dans un arbre binaire de hauteur \(h\) est : \[ \boxed{2^{h} - 1} \]

La hauteur d'un arbre est le nombre maximum de nœuds sur le chemin de la racine à une feuille. Un arbre réduit à un seul nœud a une hauteur de \(1\).

Proposition Un arbre atteint son nombre maximal de nœuds lorsque tous ses niveaux sont complètement remplis.

Le calcul s'effectue par somme des nœuds de chaque niveau :

Somme géométrique Math
$$1 + 2 + 4 + \dots + 2^{h-1} = 2^h - 1 $$

\[ \sum_{k=0}^{h-1} 2^{k} = 2^{h} - 1 \]

Convention alternative Si la hauteur de la racine est définie comme \(0\) (au lieu de \(1\)), la formule devient : \[ \boxed{2^{\,h+1} - 1} \]

Hauteur minimale pour \(N\) nœuds

Théorème Dans un arbre binaire à \(N\) nœuds, la hauteur minimale (nombre minimum de niveaux) est : \[ \boxed{\lceil \log_2(N + 1) \rceil} \]
Conseil pratique Cette formule découle de l'inégalité \(2^{h} - 1 \ge N\), où \(h\) est la hauteur minimale recherchée.
Convention alternative Si la hauteur d'une feuille est définie comme \(0\), la formule devient : \[ \boxed{\lceil \log_2(N + 1) \rceil - 1} \]

Nombre de niveaux en fonction des feuilles

Théorème Un arbre binaire contenant \(L\) feuilles possède au moins : \[ \boxed{\lceil \log_2(L) \rceil + 1} \]

Complément

Un arbre binaire atteint son nombre maximum de feuilles (et donc son nombre minimum de niveaux) lorsque tous ses niveaux sont entièrement remplis.

Relation feuilles / nœuds internes

Théorème Dans un arbre binaire strict (chaque nœud possède \(0\) ou \(2\) enfants), le nombre de feuilles est toujours égal au nombre de nœuds internes à deux enfants, augmenté de \(1\).
Définition
  • \(L\) = nombre de feuilles (nœuds sans enfant)
  • \(T\) = nombre de nœuds internes ayant exactement deux enfants
Proposition \[ \boxed{L = T + 1} \]
Exemple
Arbre strict
        (A)
       /   \
     (B)   (C)
    /   \
  (D)   (E)
Résultat
Feuilles (L) = 3 (D, E, C)
Nœuds internes à 2 enfants (T) = 2 (A, B)
Vérification : 3 = 2 + 1 ✓
Rappel mathématique

\(\lceil x \rceil\) désigne la partie entière supérieure : le plus petit entier supérieur ou égal à \(x\).

Exemple : \(\lceil 3.2 \rceil = 4\), \(\lceil 5 \rceil = 5\)

L'essentiel en bref

Propriété Formule Convention
Max nœuds au niveau \(l\) \(2^{l-1}\) racine : niveau \(1\)
Max nœuds pour hauteur \(h\) \(2^{h} - 1\) hauteur racine = \(1\)
Hauteur minimale pour \(N\) nœuds \(\lceil \log_2(N + 1) \rceil\) hauteur racine = \(1\)
Niveaux min pour \(L\) feuilles \(\lceil \log_2(L) \rceil + 1\) —
Relation feuilles / nœuds internes \(L = T + 1\) arbre binaire strict

Récapitulatif des conventions

Propriété Formule
Max nœuds pour hauteur \(h\) \(2^{h} - 1\)
Hauteur minimale pour \(N\) nœuds \(\lceil \log_2(N + 1) \rceil\)
Propriété Formule
Max nœuds pour hauteur \(h\) \(2^{h+1} - 1\)
Hauteur minimale pour \(N\) nœuds \(\lceil \log_2(N + 1) \rceil - 1\)

Un peu d'histoire

La notion de hauteur d'un arbre et ces formules fondamentales ont été formalisées dans les années 1960 avec le développement des premiers algorithmes de recherche arborescente, notamment par Donald Knuth dans The Art of Computer Programming.

Sortie
// La sortie apparaîtra ici…
Prêt · Ctrl+Entrée pour exécuter
arbres arbres binaires arbres binaires complets
Précédent Introduction aux arbres binaires
Suivant Définitions récursives des arbres

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.