Appendice A
Rappels algorithmiques
Nous donnons dans cette annexe certains des algorithmes relatifs aux structures de
données et problèmes que nous avons étudiés dans ce livre : les algorithmes de
parcours pour les arbres binaires, les algorithmes de recherche et de mise à jour
pour les arbres binaires de recherche, les arbres-B et les tries, les algorithmes de tri
radix et de tri rapide, enfin les algorithmes de manipulation de tas, incluant le tri par
tas.
Les arbres qui apparaissent en algorithmique, et donc tous les arbres de ce
chapitre, sont marqués, ou en d’autres termes leurs nœuds contiennent une ou
plusieurs valeurs, que nous appellerons le plus souvent « clés » dans cette annexe.
Pour plus de détails ou pour des algorithmes complémentaires, nous renvoyons la
lectrice et le lecteur aux nombreux livres existants sur l’algorithmique ; pour notre
part nous avons souvent utilisé, notamment pour des raisons historiques, les livres
de Knuth [156], de Froidevaux, Gaudel et Soria [111], de Sedgewick [231] et de
Cormen, Leiserson et Rivest [50, 51].
Conventions Nous avons choisi de présenter les algorithmes en un langage de
haut niveau, que nous espérons facilement compréhensible par toute personne
familière ou non de langages de programmation, et aisé à traduire en tout langage
de programmation. Nous indiquons ci-dessous nos principales conventions.
– L’affectation est notée par =, le test d’égalité par ==, et le test de non-égalité
par ! =.
– Une fonction renvoie une ou plusieurs valeurs ; une procédure ne renvoie pas de
valeur ; toutes les deux peuvent modifier leurs paramètres.
– Les paramètres sont passés par référence.
– Une fonction ou procédure récursive apparaît explicitement dans la liste des
fonctions qu’elle appelle.
– L’arbre vide est désigné par None.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
399
Rappels algorithmiques
Nous donnons dans cette annexe certains des algorithmes relatifs aux structures de
données et problèmes que nous avons étudiés dans ce livre : les algorithmes de
parcours pour les arbres binaires, les algorithmes de recherche et de mise à jour
pour les arbres binaires de recherche, les arbres-B et les tries, les algorithmes de tri
radix et de tri rapide, enfin les algorithmes de manipulation de tas, incluant le tri par
tas.
Les arbres qui apparaissent en algorithmique, et donc tous les arbres de ce
chapitre, sont marqués, ou en d’autres termes leurs nœuds contiennent une ou
plusieurs valeurs, que nous appellerons le plus souvent « clés » dans cette annexe.
Pour plus de détails ou pour des algorithmes complémentaires, nous renvoyons la
lectrice et le lecteur aux nombreux livres existants sur l’algorithmique ; pour notre
part nous avons souvent utilisé, notamment pour des raisons historiques, les livres
de Knuth [156], de Froidevaux, Gaudel et Soria [111], de Sedgewick [231] et de
Cormen, Leiserson et Rivest [50, 51].
Conventions Nous avons choisi de présenter les algorithmes en un langage de
haut niveau, que nous espérons facilement compréhensible par toute personne
familière ou non de langages de programmation, et aisé à traduire en tout langage
de programmation. Nous indiquons ci-dessous nos principales conventions.
– L’affectation est notée par =, le test d’égalité par ==, et le test de non-égalité
par ! =.
– Une fonction renvoie une ou plusieurs valeurs ; une procédure ne renvoie pas de
valeur ; toutes les deux peuvent modifier leurs paramètres.
– Les paramètres sont passés par référence.
– Une fonction ou procédure récursive apparaît explicitement dans la liste des
fonctions qu’elle appelle.
– L’arbre vide est désigné par None.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
399