Arbre binaire de recherche

Problème de la recherche On aimerai avoir une structure de donnée où l’insertion et la recherche sont efficace. Pour les tableaux : insertion en O(n), recherche en O(log(n)) Pour les listes : insertion en O(1), recherche en O(n) 4 de 1 Représentations graphiques d’arbres binaires et vocabulaire nœuds 21 4 15 6 branches 9 33 11 3 28 25 5 7 7 12 15 valeurs 29 une branche droite une branche gauche Ici : arbre, nœuds, branches ; arbre binaire, branches

O(n²), temps quadratique : apparaît notamment lorsque l’algorithme envisage toutes les paires de données parmi les n entrées (ex. deux boucles imbriquées) remarque : O(n3) temps cubique • T(n) = O(2n), temps exponentiel : souvent le résultat de recherche brutale d’une solution. On distingue également d’autres type de complexité: la compelxité en moyenne et la compelxité amortie. La complexité en moyenne nécessite une connaissance de la distribution probabliliste des données. La compelxité amortie

hauteur de l’arbre (h) (nœuds n = ni + f ) Pour tout arbre binaire : n ≤ 2 h +1 − 1 f ≤ 2h si x = 1 si | x | < 1 si | x | < 1 Arbres x profondeur de x feuilles ( f ) h ≥ log2 (n + 1) − 1 = log2 n si n > 0 h ≥ log2 f si f > 0 exponentielle Θ(cn ) factorielle Θ(n!) Θ(nn ) Identités utiles n ( n + 1) ∑k= 2 k =0 x n +1 − 1 ∑ x = x−1 k =0 k k =0 ∞ n n f = ni + 1 (si l’arbre est complet = les nœud internes ont tous 2 fils) Dans un arbre binaire équilibré une feuille est soit à la profondeur log2

de programme de O’Hare e 1.1 R`gles et axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . e 1.2 Construction de programmes sur invariant . . . . . . . . . . . . . 2 Probl`mes de recherches e 2.1 Remarques sur l’´valuation e 2.2 Recherche dichotomique . 2.3 Recherche s´quentielle . . e 2.4 Recherche arri`re . . . . . e de complexit´ d’un e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

struct Noeud { Element contenu; struct Noeud *filsG; struct Noeud *filsD; }*Arbre; void ParcoursPrefixe(Arbre a) { if (a != NULL ) { printf("%3d", a->contenu); ParcoursPrefixe(a->filsG); ParcoursPrefixe(a->filsD); } } X, Petite classe 7 5 void ParcoursInfixe(Arbre a) { if (a != NULL ) { ParcoursInfixe(a->filsG); printf("%3d", a->contenu); ParcoursInfixe(a->filsD); } } void ParcoursSuffixe(Arbre a) { if (a != NULL ) { ParcoursSuffixe(a->filsG); ParcoursSuffixe(a->filsD);

données Arbres (Trees) Structures de données (2012-2013) 1 ah-fsr-v2.0 Objectifs Etudier des structures non linéaires Arbres binaires Arbres binaires de recherche Arbres maximiers ou Tas Arbres équilibrés Structures de données (2012-2013) 2 1 ah-fsr-v2.0 Contenu Introduction Terminologie Arbres binaires Arbres binaires de recherche Arbres maximiers ou Tas Arbres équilibrés Structures de données (2012-2013) 3 ah-fsr-v2.0 Arbres (Trees) Introduction Structures

Qu'est-ce qu’un arbre ? Vocabulaire Les arbres sont composés de deux éléments de base : les nœuds (ou vertex), un nœud peut être étiqueté ou non : c'est-à-dire porter une ou plusieurs valeurs, les arcs (ou arêtes) qui relient les nœuds (un arc relie deux nœuds différents), un arc peut être pondéré ou non : c'est-à-dire porter une ou plusieurs valeurs. Vocabulaire De manière informelle, nous définirons un chemin entre deux nœuds comme : un ensemble d'arcs permettant de relier

arbres binaires sont constitués de nœuds pouvant donner 0, 1 ou 2 enfants, on a au maximum 2 branches qui partent d'un élément. On associe à chaque nœud, une clé, un sous-arbre gauche (SAG) et un sous-arbre droit (SAD). On va utiliser les classes suivantes : L'attribut file est privé, pas les autres. Compléter les instructions suivantes permettant de construire l'arbre au-dessus. a = Arbre('A') a.SAG = Arbre('B') a.SAG.SAG = ….. Nœud ATTRIBUTS : - cle

II-A - Arbres enracinés II-B - Terminologie II-C - Arité d'un arbre II-D - Taille et hauteur d'un arbre. II-E - Arbre localement complet, dégénéré, complet. III - Implémentation IV - Les fonctions de base sur la manipulation des arbres. V - Algorithmes de base sur les arbres binaires V-A - Calcul de la hauteur d'un arbre V-B - Calcul du nombre de noeud V-C - Calcul du nombre de feuilles V-D - Nombre de noeud internes VI - Parcours d'un arbre VI-A - Parcours en profondeur VI-B - Parcours en largeur (ou

nbre total d’opérations est proportionnel au nbre d’opérations fondamentales. Complexité des algorithmes 11 exemples : Problème recherche d’un élément dans une liste multiplication des matrices réelles addition des entiers binaires Opération fondamentale comparaison entre l’élément et les entrées de la liste multiplication scalaire opération binaire Complexité des algorithmes 12 Le temps de l’exécution dépend de la taille de l’entrée. On veut considérer seulement la taille essentielle