-
Cours :
- Bases de données 1
- Bases de données 2
- Bases de données 3
- Bases de données 4
- Bases de données 5
- Programmation orientée objet
- cours 6
transparents : pdf, html - planche de TD/TP 6 (pdf)
- cours 6
- Programmation évènementielle
- Structures de données : listes, piles, files
- cours 8
transparents : pdf, html - planche de TD/TP 8 (pdf)
- cours 8
- Structures de données : arbres et ABR
- cours 9
transparents : pdf, html - planche de TD/TP 9 (pdf)
- cours 9
- Structures de données : graphes
- cours 10
transparents : pdf, html - planche de TD/TP 10 (pdf)
- cours 10
Structures de données : arbres
Exemples d’utilisation des arbres
Arbre syntaxique d’une expression arithmétique
Arbre syntaxique analysant une phrase
Arbre généalogique
Arbre lexicographique (ou en parties communes, ou dictionnaire)
Arbre de décision
Arbre de versions git
Arbre phylogénétique
Arbre phylogénétique
Définitions d’un arbre enraciné
Définition ensembliste
Un arbre est un ensemble organisé de nœuds :
- chaque nœud a un unique parent,
- sauf un seul nœud, la racine, qui n’a pas de parent.
Les nœuds ayant un nœud p comme parent sont appelés les enfants de p.
Les feuilles sont les nœuds qui n’ont pas d’enfants.
Définition récursive
Un arbre est constitué :
- d’un nœud p, sa racine,
- et d’une suite de sous-arbres (a1, a2, …, ak) (avec k non fixé a priori).
Les racines des arbres a1, a2, …, ak sont les enfants de p.
Les mots des arbres
Parcours
Parcourir un arbre (ou un graphe…), c’est visiter la totalité des nœuds de celui-ci, dans un certain ordre, pour appliquer un éventuel traitement: affichage, évaluation, recherche…
Parcours en profondeur
Parcours en largeur
Arbres binaires
Définition
Chaque nœud a au plus 2 enfants : l’enfant gauche et l’enfant droit
Hauteur et taille d’un arbre binaire
Arbre binaire complet de hauteur h (hauteur = nombre de niveaux):
- à la profondeur p on a 2p nœuds
- le nombre total de nœuds est donc Σi = 0h − 12i = 2h − 1
Un arbre quelconque de hauteur h contient au plus 2h − 1 nœuds.
Parcours en profondeur d’un arbre binaire
Parcours préfixe : traitement du nœud avant les sous-arbres
Parcours infixe : traitement du nœud entre les deux sous-arbres
Parcours postfixe : traitement du nœud après les sous-arbres
Structure de données abstraite : ensemble dynamique
Structure de données abstraite : ensemble dynamique
- Recherche d’un élément dans un ensemble
- Insertion d’un nouvel élément
- Suppression d’un élément
- Test du vide de l’ensemble
Interface :
set.contains(element) # true or false
set.insert(element) # modifies set
set.suppress(element) # modifies set
set.isempty() # true or false
Première implémentation : liste triée dans le cas où les éléments sont comparables
- Recherche d’un élément dans un ensemble: recherche dichotomique
O(log (n))
- Insertion d’un nouvel élément: recherche puis décalage
O(n)
- Suppression d’un élément: recherche puis décalage
O(n)
- Test du vide de l’ensemble: test de longueur
O(1)
Seconde implémentation : arbre binaire de recherche dans le cas où les éléments sont comparables
Arbre binaire étiqueté par les éléments tel que pour tout nœud p d’étiquette x:
- toutes les étiquettes de l’enfant gauche de p sont inférieures à x
- toutes les étiquettes de l’enfant droit de p sont supérieures à x
Algorithmes et complexité: bloc 5 !
Troisième implémentation : table de hachage dans le cas d’éléments hachables
Principe :
- appliquer une fonction de hachage (ou dispersion) permettant d’associer à chaque élément un indice i dans un intervalle restreint de valeurs
- ranger l’élément dans la case d’indice i d’une liste (appelée table de hachage)
- en cas de collision (deux éléments à insérer de même fonction de hachage), on stocke une liste d’éléments dans la case d’indice i
Structures utilisée pour les dictionnaires Python