Algorithmique Les arbres Florent Hivert Mél : Florent. Hivert@lri. fr Page personnelle : http://www. lri. frrhivert Algorithmes et structures de données La plupart des bons méthode astucieuse pour orga quatre p g t grâce à une allons étudier grandes classes de structures de données : Les structures de données séquentielles (tableaux) ; Les structures de données linéaires (liste chaînées) ; Les arbres ; Les graphes. 3 de 1 Problème de la recherche On aimerai avoir une structure de donnée où l’insertion et la echerche sont efficace.
Pour les tableaux : insertion en O(n), recherche en O(log(n)) pour les listes : insertion en 0(1), recherche en O(n) binaire, branches gauches, branches droites ; valeurs (ou étiquettes) des nœuds. 4 de Représentations graphiques d’arbres binaires et vocabulaire nœuds 21 4 15 6 branches 9 33 11 3 28 25 5 7 12 valeurs 29 une branche droite 2 OF s sous-arbre droit ; l’arbre vide, notion récursive d’arbre binaire valué (ou étiqueté) ; notion récursive de sous-arbre. de 1 Arbres binaires étendus 9 d 3 OF s équilibre ; chemin issu de la racine, longueur d’un chemin. Arbre binaire de recherche 22 48 31 30 croissance stricte arbre binaire de recherche 4 OF
