Introduction aux algorithmes et aux structures de données

On peut vérifier cette correction de manière empirique, en testant concrètement l'algorithme (il faut alors l'implémenter et trouver suffisamment d'instances du problème), ou de manière formelle, mathématique. On se focalisera sur cette deuxième approche.

Une assertion est une relation entre les variables qui est vraie à un moment dans l'exécution. Notamment, on compte les pré- et postconditions (conditions que doivent remplir les données d'entrée et de sortie) kitxmlcodeinlinelatexdvp{P}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp{Q}finkitxmlcodeinlinelatexdvp.

Ainsi, un code sera correct si le triplet de Hoare kitxmlcodeinlinelatexdvp{P} code {Q}finkitxmlcodeinlinelatexdvp est vrai. Pour vérifier cette propriété, on insère des assertions kitxmlcodeinlinelatexdvpP_{n}finkitxmlcodeinlinelatexdvp décrivant l'état des variables à chaque étape du programme et on vérifiera que cette suite de triplet est correcte :

Pour les boucles, on mettra en évidence une assertion particulière, kitxmlcodeinlinelatexdvp{I}finkitxmlcodeinlinelatexdvp , l'invariant de boucle, qui décrit l'état du programme pendant l'exécution. Cet invariant est vrai après l'initialisation de la boucle, après chaque itération (kitxmlcodeinlinelatexdvp\text{{I et B} code {I}}finkitxmlcodeinlinelatexdvp est vrai) et à la sortie de la boucle (kitxmlcodeinlinelatexdvp\text{{I et non B} fin {I}}finkitxmlcodeinlinelatexdvp est vrai). En général, l'algorithme découle de l'invariant, de l'idée de base à la conception.

Une fois qu'on a prouvé que la boucle était correcte, il faut s'assurer qu'elle se termine. On cherchera donc une fonction de terminaison kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp :

• définie sur base des variables de l'algorithme ;
• à valeur naturelle ;
• décroissante suite à l'exécution du corps de la boucle ;
• à valeur positive tant que le gardien de la boucle est vrai.

Ainsi, quand kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp atteindra zéro, on aura infirmé le gardien et la boucle sera terminée.

La preuve par induction se passe en deux étapes :

• cas de base : on montre explicitement que la propriété est vraie pour une série d'instances ;
• cas inductif : on suppose que la propriété est vraie pour les instances précédentes du problème et on montre qu'elle l'est aussi pour l'instance suivante.

Cette manière de procéder est correcte, car le corps des naturels kitxmlcodeinlinelatexdvp\mathbb{N}finkitxmlcodeinlinelatexdvp est bien ordonné par la relation kitxmlcodeinlinelatexdvp\leqfinkitxmlcodeinlinelatexdvp (dans tout sous-ensemble de kitxmlcodeinlinelatexdvp\mathbb{N}finkitxmlcodeinlinelatexdvp, il y a un plus petit élément).

On se contentera d'une analyse asymptotique, en considérant des instances très grandes. Cela simplifiera les calculs : on ne garde que le terme dominant en en ignorant le coefficient. En effet, même en augmentant considérablement la puissance de calcul, cela ne fera pas varier de manière significative le temps d'exécution de l'algorithme.

On utilisera trois notations :

• kitxmlcodeinlinelatexdvpO(g)=\left\{ f\,\Big|\,\exists c>0,\, n_{0}\geq1\,:\,0\leq f(n)\leq c\times g(n),\,\forall n\geq n_{0}\right\}finkitxmlcodeinlinelatexdvp, on définit une borne supérieure asymptotique à la fonction ;
• kitxmlcodeinlinelatexdvp\Omega(g)=\left\{ f\,\Big|\,\exists c>0,\, n_{0}\geq1\,:\,0\leq c\times g(n)\leq f(n),\,\forall n\geq n_{0}\right\}finkitxmlcodeinlinelatexdvp, on définit une borne inférieure asymptotique à la fonction ;
• kitxmlcodeinlinelatexdvp\Theta(g)=\left\{ f\,\Big|\,\exists c_{1}>0,\, c_{2}>0,\, n_{0}\geq1\,:\,0\leq c_{1}\times g(n)\leq f(n)\leq c_{2}\times g(n),\,\forall n\geq n_{0}\right\}finkitxmlcodeinlinelatexdvp, on définit une borne serrée asymptotique à la fonction.

On peut utiliser une analyse asymptotique plus précise que les notations introduites précédemment : par exemple, kitxmlcodeinlinelatexdvp2\, n=O\left(n^{2}\right)finkitxmlcodeinlinelatexdvp, alors que, asymptotiquement, la différence entre les deux fonctions est énorme. Avec la notation kitxmlcodeinlinelatexdvpOfinkitxmlcodeinlinelatexdvp, seules quelques constantes kitxmlcodeinlinelatexdvpcfinkitxmlcodeinlinelatexdvp peuvent convenir pour satisfaire kitxmlcodeinlinelatexdvp0\leq f\left(n\right)\leq c\, g\left(n\right)finkitxmlcodeinlinelatexdvp. En notation kitxmlcodeinlinelatexdvpofinkitxmlcodeinlinelatexdvp, cette relation est valable pour toute constante kitxmlcodeinlinelatexdvpc>0finkitxmlcodeinlinelatexdvp.

On introduit donc les notations suivantes.

• kitxmlcodeinlinelatexdvpo\left(g\right)=\left\{ f\,\Big|\,\forall c>0,\exists n_{0}>0:0\leq f\left(n\right)<c\, g\left(n\right),\forall n\geq n_{0}\right\} finkitxmlcodeinlinelatexdvp ; notamment, cela implique que kitxmlcodeinlinelatexdvp\lim\limits _{n\to\infty}\dfrac{f\left(n\right)}{g\left(n\right)}=0finkitxmlcodeinlinelatexdvp.
• kitxmlcodeinlinelatexdvp\omega\left(g\right)=\left\{ f\,\Big|\,\forall c>0,\exists n_{0}>0:0\leq c\, g\left(n\right)<f\left(n\right),\forall n\geq n_{0}\right\} finkitxmlcodeinlinelatexdvp ; notamment, cela implique que kitxmlcodeinlinelatexdvp\lim\limits _{n\to\infty}\dfrac{f\left(n\right)}{g\left(n\right)}=\inftyfinkitxmlcodeinlinelatexdvp.

Un arbre est un graphe dirigé constitué d'un ensemble de nœuds reliés par des arcs. Ce graphe est connexe et acyclique. S'il est non vide, alors il possède un nœud distingué et unique, la racine. Un chemin est une séquence de nœuds dont toute paire consécutive est un arc de l'arbre. La hauteur d'un arbre est la distance entre la feuille la plus éloignée et la racine.

Un arbre ordonné est un arbre dans lequel l'ensemble des fils de chacun de ses nœuds est ordonné.

Un arbre est dit binaire si chacun de ses nœuds possède au plus deux fils (un gauche et un droit, le gauche précédent le droit).

Un arbre est dit parfait ou complet si toutes ses feuilles sont à la même distance de la racine.

Un arbre binaire entier ou propre (full ou proper) est un arbre binaire dans lequel tous les nœuds internes possèdent exactement deux fils. Pour ces arbres, on dispose de quelques propriétés :

• le nombre de nœuds externes est égal au nombre de nœuds internes plus une unité ;
• le nombre de nœuds internes est égal à kitxmlcodeinlinelatexdvp\frac{n-1}{2}finkitxmlcodeinlinelatexdvp, où kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est le nombre de nœuds ;
• le nombre de nœuds à la profondeur (niveau) kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp est inférieur ou égal à kitxmlcodeinlinelatexdvp2^{i}finkitxmlcodeinlinelatexdvp ;
• la hauteur de l'arbre est inférieure ou égale au nombre de ses nœuds internes.

On peut lier la hauteur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp et le nombre de nœuds kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp pour un arbre binaire entier par

De manière équivalente,

Un arbre binaire complet (aussi dit tas) est un arbre binaire tel que, notant kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp la hauteur de l'arbre :

• pour tout kitxmlcodeinlinelatexdvpi\in[0\,;\, h-1]finkitxmlcodeinlinelatexdvp, il y a exactement kitxmlcodeinlinelatexdvp2^{i}finkitxmlcodeinlinelatexdvp nœuds à la profondeur kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp ;
• une feuille a une profondeur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp ou kitxmlcodeinlinelatexdvph-1finkitxmlcodeinlinelatexdvp ;
• les feuilles de profondeur maximale sont tassées sur la gauche.

Un tas binaire est un arbre binaire complet tel que :

• à chaque nœud est associée une clé ;
• la clé de chaque nœud est supérieure ou égale à celle de ses fils (la propriété d'ordre du tas).

Un tas (un arbre binaire complet kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp entrées et de hauteur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp) dispose des propriétés suivantes :

• kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est supérieur ou égal à la taille de l'arbre complet de hauteur kitxmlcodeinlinelatexdvph-1finkitxmlcodeinlinelatexdvp plus une unité, soit kitxmlcodeinlinelatexdvp2^{h}finkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est inférieur ou égal à la taille de l'arbre complet de hauteur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp, soit kitxmlcodeinlinelatexdvp2^{h+1}-1finkitxmlcodeinlinelatexdvp.

On peut également écrire

Pour un tas kitxmlcodeinlinelatexdvpHfinkitxmlcodeinlinelatexdvp, on définit les opérations suivantes :

• kitxmlcodeinlinelatexdvpH.heapSizefinkitxmlcodeinlinelatexdvp : le nombre de clés de kitxmlcodeinlinelatexdvpHfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpBuildMaxHeap(A)finkitxmlcodeinlinelatexdvp : construire un tas à partir du tableau kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpHeapInsert(H,\, key)finkitxmlcodeinlinelatexdvp : insérer la valeur kitxmlcodeinlinelatexdvpkeyfinkitxmlcodeinlinelatexdvp dans le tas kitxmlcodeinlinelatexdvpHfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpHeapExtractMax(H)finkitxmlcodeinlinelatexdvp : récupérer la clé maximale.

On peut représenter un tas de manière compacte par un tableau A : la racine de l'arbre est le premier élément, on peut accéder relativement aux autres éléments par ces quelques fonctions (elles renvoient l'indice à consulter).

• kitxmlcodeinlinelatexdvpParent(i)=\left\lfloor \frac{i}{2}\right\rfloor finkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpLeft(i)=2\times ifinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpRight(i)=2\times i+1finkitxmlcodeinlinelatexdvp.

La propriété d'ordre du tas impose ainsi kitxmlcodeinlinelatexdvp\forall i,\, A[Parent(i)]\geq A[i]finkitxmlcodeinlinelatexdvp.

On peut alors implémenter les quelques méthodes du tas.

kitxmlcodeinlinelatexdvpMaxHeapifyfinkitxmlcodeinlinelatexdvp considère que les deux sous-arbres du nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp sont des tas et réarrange l'arbre pour qu'il soit un tas (il fait descendre l'élément kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp jusqu'à ce que l'arbre respecte la propriété d'ordre). Ensuite, on appelle récursivement l'algorithme du côté de l'élément qui a été déplacé (le cas échéant). Vu le lien entre la hauteur de l'arbre et le nombre de nœuds, on a une complexité de kitxmlcodeinlinelatexdvp\Theta(h)=\Theta(\log n)finkitxmlcodeinlinelatexdvp.

l = Left(i)
r = Right(i)

if l <= A.heapSize and A[l] > A[i]
	largest = l
else
	largest = i

if r <= A.heapSize and A[r] > A[largest]
	largest = r

if largest 6= i
	swap(A[i];A[largest])
	MaxHeapify(A; largest)

kitxmlcodeinlinelatexdvpBuildMaxHeapfinkitxmlcodeinlinelatexdvp construit un tas à partir d'un tableau : à partir du premier nœud qui a un successeur (gauche, s'il n'y en a qu'un), on réorganise le tas et on remonte jusqu'à la racine. On effectue kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp appels à kitxmlcodeinlinelatexdvpMaxHeapifyfinkitxmlcodeinlinelatexdvp, d'où une complexité de kitxmlcodeinlinelatexdvpO(n\,\log n)finkitxmlcodeinlinelatexdvp ; une analyse plus fine sur un arbre binaire parfait atteint kitxmlcodeinlinelatexdvpO\left(\log n\right)finkitxmlcodeinlinelatexdvp.

A.heapSize = A.length
for i = (round down A.length/2) downto 1
	MaxHeapify(A, largest)

Pour l'insertion dans un tas, on insère l'élément à la fin (soit avec une clé infiniment négative), puis on le déplace jusqu'à la clé voulue.

A.heapSize = A.heapSize + 1
A[A.heapSize] = - infinity
HeapIncreaseKey(A, A.heapSize, key)

if key < A[i]
	error new key is smaller than current key
A[i] = key
while i > 1 and A[Parent(i)] < A[i]
	swap(A[i], A[Parent(i)])
	i = Parent(i)

On peut également récupérer le maximum et l'éliminer du tas assez facilement (kitxmlcodeinlinelatexdvpO\left(1\right)finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpO\left(n\right)finkitxmlcodeinlinelatexdvp, respectivement : lecture et réorganisation).

return A[1]

if A:heapSize < 1
	error \heap under
max = A[1]
A[1] = A[A.heapSize]
A:heapSize = A.heapSize - 1
MaxHeapify(A, 1) // rebuild the heap
return max

À partir d'un tas, on récupère la racine, l'élément le plus élevé de tout le tas, on la remplace par le dernier élément. On place cette racine à la fin du tableau et on ne considère plus cette case comme partie du tas. On réordonne donc le reste du tableau comme un tas puis on recommence. Tout comme la construction d'un tas, cet algorithme a une complexité de kitxmlcodeinlinelatexdvp\Theta(n\,\log n)finkitxmlcodeinlinelatexdvp.

BuildMaxHeap(A)
for i = A.length downto 2
	swap(A[i], A[1])
	A.heapSize = A.heapSize - 1
	MaxHeapify(A, 1)

V-A-1-a. Liste liée▲

V-A-1-b. Vecteur trié▲

Un arbre est constitué de nœuds, accessibles les uns par rapport aux autres selon leur position ; les données sont associées à ces nœuds. Son interface est constituée de :

• kitxmlcodeinlinelatexdvpparent(T,n)finkitxmlcodeinlinelatexdvp : renvoie le parent de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp, sauf si kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est la racine ;
• kitxmlcodeinlinelatexdvpchildren(T,n)finkitxmlcodeinlinelatexdvp : renvoie une structure de données des fils de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpleft(T,n)finkitxmlcodeinlinelatexdvp : renvoie le fils gauche de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre binaire kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpright(T,n)finkitxmlcodeinlinelatexdvp : renvoie le fils droit de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre binaire kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvproot(T)finkitxmlcodeinlinelatexdvp : renvoie la racine de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpisRoot(T,n)finkitxmlcodeinlinelatexdvp : renvoie vrai si de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est la racine de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpisInternal(T,n)finkitxmlcodeinlinelatexdvp : renvoie vrai si de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est un nœud interne de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpisExternal(T,n)finkitxmlcodeinlinelatexdvp : renvoie vrai si de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est un nœud externe de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpgetData(T,n)finkitxmlcodeinlinelatexdvp : renvoie les données associées à l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
• kitxmlcodeinlinelatexdvpsize(T)finkitxmlcodeinlinelatexdvp : renvoie le nombre de nœuds de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp.

V-B-2-a. Vecteur▲

V-B-2-b. Structure liée▲

On va descendre dans l'arbre avant d'aller visiter les nœuds voisins.

V-B-3-a. Parcours infixe (en ordre)▲

if x != nil
	InorderTreeWalk(x.left)
	walk(x.key)
	InorderTreeWalk(x.left)

V-B-3-b. Parcours préfixe (en préordre)▲

if x != nil
	walk(x.key)
	InorderTreeWalk(x.left)
	InorderTreeWalk(x.left)

V-B-3-c. Parcours postfixe (en postordre)▲

if x != nil
	InorderTreeWalk(x.left)
	InorderTreeWalk(x.left)
	walk(x.key)

V-B-3-d. Complexité▲

On visite le nœud le plus proche de la racine qui n'a pas été visité, soit d'abord la racine, puis ses enfants, les nœuds du deuxième niveau et ainsi de suite. On peut l'implémenter à l'aide d'une file avec une complexité en temps de kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp :

Q = new empty queue
Enqueue(Q, x)
while not QueueEmpty(Q)
	y = Dequeue(Q)
	walk(y.key)
	if y.left != NIL
		Enqueue(Q, y.left)
	if y.right != NIL
		Enqueue(Q, y.right)

Une recherche (récursive terminale ou itérative) dans un tel arbre aura une complexité kitxmlcodeinlinelatexdvpO(h)finkitxmlcodeinlinelatexdvp.

if x == NIL or k == x.key
	return x
if k < x.key
	return TreeSearch(x.left, k)
else
	return TreeSearch(x.right, k)

x = T.root
while x != NIL and k != x:key
	if k < x.key
		x = x.left
	else
		x = x.right
return x

Au vu de la propriété d'arbre binaire de recherche, la clé minimale est stockée dans le nœud le plus à gauche et la clé maximale dans le nœud le plus à droite.

while x.left != NIL
	x = x.left
return x

while x.right != NIL
	x = x.right
return x

On veut, à partir d'un nœud kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, trouver le nœud contenant la valeur de clé suivante, selon un ordre arithmétique. Si le sous-arbre de droite du nœud existe, alors le successeur en est le minimum. Sinon, il s'agit du premier ancêtre kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp tel que kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp est dans le sous-arbre de gauche de kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp.

if x.right != NIL
	return TreeMinimum(x.right)
y = x.parent
while y != NIL and x == y.right
	x = y
	y = y.parent
return y

Pour insérer un élément, on recherche sa clé dans l'arbre et on l'insère là où la recherche s'est arrêtée dans le cas où elle n'existe pas encore.

y = NIL
x = T.root
while x != nil
	y = x
	if z.key < x.key
		x = x.left
	else
		x = x.right
z.parent = y
if y == NIL
	// Tree T was empty
	T.root = z
elseif z.key < y.key
	y. left = z
else
	y.right = z

Trois cas particuliers sont à considérer : un seul fils ou deux fils. S'il n'y a pas de fils, il suffit de supprimer toute référence au nœud. Le but est toujours de garder la propriété d'arbre binaire de recherche. Pour supprimer le nœud kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp :

• s'il n'a qu'un seul fils : le remplacer par celui-ci ;

• s'il a deux fils : rechercher le successeur kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp :

  • si kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est le fils droit de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, remplacer kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp par kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp et conserver le fils droit de kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp,
  • sinon, kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est dans le sous-arbre droit de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp sans en être la racine ; on remplace kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp par son propre fils droit et on remplace kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp par kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp.

if u.parent == NIL
	T.root = v
elseif u == u.parent.left
	u.parent.left = v
else
	u.parent.right = v
if v != NIL
	v.parent = u.parent

if z.left == NIL
	Transplant(T, z, z.right)
elseif z.right == NIL
	Transplant(T, z, z.left)
else // z has two children
	y = TreeSuccessor(z)
	if y.parent != z
		Transplant(T, y, y.right)
		y.right = z.right
		y.right.parent = y
	// Replace z by y
	Transplant(T, z, y)
	y.left = z.left
	y.left.parent = y

Un tri dans l'ordre croissant correspond à un parcours infixe de l'arbre binaire de recherche. Sa complexité en temps est identique à celle du tri rapide, bien que sa complexité en espace soit plus importante, étant donné la structure sous-jacente.

T = new empty binary search tree
for i = 1 to n
	TreeInsert(T;A[i])
InorderTreeWalk(T:root)

On étudiera ici les arbres AVL (Adelson-Velskii-Landis), qui ont la propriété d'être H-équilibrés. Leur invariant est, pour tout sous-arbre kitxmlcodeinlinelatexdvpT'finkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp,

Les hauteurs des deux sous-arbres d'un nœud diffèrent au plus d'une unité. Un tel arbre aura une hauteur bornée par

Précisément, on peut prouver que

Un arbre AVL (Adelson-Velskii-Landis) est un arbre binaire de recherche H-équilibré. En tant qu'arbre binaire de recherche, on peut utiliser l'algorithme des arbres binaires de recherche pour la recherche ; il aura une complexité de kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp, vu la propriété.

Pour l'insertion, on procèdera comme pour un arbre binaire classique) ; ensuite, on rétablira l'invariant au besoin à l'aide de rotations.

V-D-2-a. Rotations▲

Ces rotations sont implémentées à l'aide des algorithmes suivants.

Rotation gauche : LeftRotate(x)

Sélectionnez

r = x.right
x.right = r.left
r.left = x
return r

Rotation droite : RightRotate(x)

Sélectionnez

r = x.left
x.left = r.right
r.right = x
return r

V-D-2-b. Équilibrage▲

V-D-2-c. Tri▲

On suppose que chaque élément est associé à une clé unique tirée d'un univers pas trop grand, kitxmlcodeinlinelatexdvpU=\{1\ldots m-1\}finkitxmlcodeinlinelatexdvp. Le dictionnaire est alors implémenté par le tableau kitxmlcodeinlinelatexdvpT[0\ldots m-1]finkitxmlcodeinlinelatexdvp, chaque position correspondant à une clé de l'univers. Si le dictionnaire contient un élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp avec la clé kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp, alors kitxmlcodeinlinelatexdvpT[k]finkitxmlcodeinlinelatexdvp contient un pointeur vers kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp. Sinon, kitxmlcodeinlinelatexdvpT[k]finkitxmlcodeinlinelatexdvp est un pointeur nul.

On a ainsi un dictionnaire à accès en temps constant, ainsi que la suppression et la recherche. Sa taille sera constante (kitxmlcodeinlinelatexdvp\Theta(\#U)finkitxmlcodeinlinelatexdvp), il ne pourra pas retenir plusieurs éléments avec la même clé. Si l'ensemble des clés utilisées est très inférieur à l'univers, alors on gaspille beaucoup de place.

On utilise un tableau kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp de taille largement inférieure à la taille de l'univers. On placera l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp de clé kitxmlcodeinlinelatexdvpx.keyfinkitxmlcodeinlinelatexdvp à la position kitxmlcodeinlinelatexdvph(x.key)finkitxmlcodeinlinelatexdvp, où kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp est une fonction de hachage qui établit un lien entre l'univers kitxmlcodeinlinelatexdvpUfinkitxmlcodeinlinelatexdvp et l'ensemble des clés de kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp.

Cependant, on a un risque de collision : deux clés distinctes ont la même image par la fonction de hachage. Par le principe des tiroirs, cela se produit toujours lorsqu'on a plus d'éléments à stocker que la taille du tableau. Selon le paradoxe des anniversaires, c'est même très probable, même si la fonction de hachage répartit les clés de manière uniforme.

Deux solutions pour éviter les collisions : une fonction de hachage qui répartit de manière uniforme les clés ou un tableau de taille suffisante. Dans chaque cas, en cas de remplissage suffisant, la probabilité de collision restera élevée. Deux approches résolvent définitivement ce problème : l'adressage ouvert et l'adressage fermé.

Idéalement, une fonction de hachage devrait être facile à calculer (en temps constant) et satisfaire l'hypothèse de hachage uniforme, ce qui n'est pas forcément facile à obtenir (on ne connaît généralement pas la distribution des clés et elles ne sont pas forcément indépendantes). Une telle fonction suppose que la clé est un nombre naturel (sinon, il faut la coder : par exemple, pour une chaîne de caractères, prendre la valeur ASCII de chaque caractère, la pondérer par kitxmlcodeinlinelatexdvp128^{i}finkitxmlcodeinlinelatexdvp et sommer).

V-E-3-a. Méthode de division▲

V-E-3-b. Méthode de multiplication▲

Simplement, on stocke les éléments qui ont le même hash dans une liste (doublement) liée. On aura une insertion (en début de liste) en temps constant, une suppression linéaire pour une liste liée ou constante pour une liste doublement liée, une recherche linéaire du nombre d'éléments dans la liste, du moins dans le pire cas.

Afin d'étudier la complexité dans le cas moyen, on définit le facteur de charge

où kitxmlcodeinlinelatexdvpmfinkitxmlcodeinlinelatexdvp est la taille du tableau et kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp le nombre d'éléments stockés. On supposera le hachage parfaitement uniforme : pour toute clé kitxmlcodeinlinelatexdvpk\in Ufinkitxmlcodeinlinelatexdvp, on a

On considérera également que la fonction de hachage kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp a une complexité temporelle kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp et que l'on insère les éléments en début de liste.

Ainsi, dans le cas moyen, que la recherche soit positive ou non, on aura une complexité temporelle de kitxmlcodeinlinelatexdvp\Theta(1+\alpha)finkitxmlcodeinlinelatexdvp (kitxmlcodeinlinelatexdvp\alphafinkitxmlcodeinlinelatexdvp pouvant être aussi bien inférieur à l'unité ou très grand, en fonction du remplissage). Si on a

soit si kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp croît au moins linéairement avec la taille du tableau, on aura

Toutes les opérations seront kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp en moyenne.

V-E-4-a. Critique▲

On stocke tous les éléments dans le tableau : une fois celui-ci rempli, on ne peut plus ajouter d'élément. Pour insérer une clé kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp, on sonde toutes les autres cases à partir de kitxmlcodeinlinelatexdvph(k,0)finkitxmlcodeinlinelatexdvp en suivant une fonction de sondage kitxmlcodeinlinelatexdvph(k,i)finkitxmlcodeinlinelatexdvp.

La fonction de hachage est ainsi définie sur kitxmlcodeinlinelatexdvpU\times[0\,;m-1]finkitxmlcodeinlinelatexdvp et telle que

est une permutation de kitxmlcodeinlinelatexdvp[0\,;m-1]finkitxmlcodeinlinelatexdvp.

Pour supprimer, on ne peut pas simplement mettre un pointeur nul à l'endroit qui vient d'être libéré, on ne saurait jamais si on doit poursuivre la recherche. On utilise donc une valeur spéciale : lors de la recherche, on sait qu'on devra continuer ; lors d'une insertion, la case est considérée vide. Ainsi, le temps de recherche ne dépend plus du facteur de charge, mais de la charge maximale de la table.

Une stratégie de sondage efficace donnera un hachage uniforme : chacune des permutations de kitxmlcodeinlinelatexdvp[0\,;1]finkitxmlcodeinlinelatexdvp a la même probabilité de correspondre à une clé. Cela est cependant dur à garantir, on se satisfera généralement du fait que l'on a une permutation.

• Sondage linéaire : facile à implémenter, on se limite à aller voir la case suivante ; on crée ainsi un fort effet de grappe, pas d'uniformité ; on a la fonction

  kitxmlcodelatexdvph(k,i)=\bigg(h(k)+i\bigg)\mod m.finkitxmlcodelatexdvp

• Sondage quadratique : à l'aide de deux constantes bien choisies (pour garder la propriété de permutation), on effectue un parcours quadratique de la table ; l'effet de grappe est toujours présent, bien que moins marqué ; on a la fonction

  kitxmlcodelatexdvph(k,i)=\bigg(h(k)+c_{1}\, i+c_{2}\, i^{2}\bigg)\mod m.finkitxmlcodelatexdvp

• Double hachage : on utilise deux fonctions de hachage différentes, à bien choisir pour garder la permutation ; le résultat sera très proche de l'uniformité, bien meilleur que les techniques précédentes ; on aura la fonction

  kitxmlcodelatexdvph(k,i)=\bigg(h(k)+i\, h'(k)\bigg)\mod m.finkitxmlcodelatexdvp

V-E-5-a. Critique▲

Une table de hachage est facile à implémenter, la seule solution disponible pour des clés non ordonnées, a des recherche et insertion très rapides en moyenne, mais gaspille de l'espace en faible facteur de charge ; dans le pire cas, les performances ne sont pas garanties.

Un arbre binaire de recherche (équilibré ou non ; ABR ou AVL) aura des performances garanties, ne gaspillera pas de mémoire, supportera plus d'opérations car les clés sont ordonnées, bien que l'accès et l'insertion soient plus lents en moyenne.

On parcourt les sommets par ordre croissant de distance par rapport au sommet argument kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp : on visite kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp, puis ses voisins, puis les voisins des voisins, etc., jusqu'à avoir parcouru tous les sommets accessibles.

On devra retenir les sommets déjà visités pour éviter de partir en boucle infinie. De même, on doit retenir les sommets visités dont on n'a pas encore visité les voisins. Aussi, on devra retenir la distance d'un sommet kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp : elle sera finie si le sommet kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp a été visité. La file (structure LIFO) contiendra les sommets qui ont été visités, mais pas leurs voisins.

Chaque sommet sera visité au plus une fois (sa distance à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp sera alors finie et il ne sera plus parcouru). La boucle principale s'exécutera kitxmlcodeinlinelatexdvp|V|finkitxmlcodeinlinelatexdvp fois, la boucle interne kitxmlcodeinlinelatexdvp|E|finkitxmlcodeinlinelatexdvp fois en tout. La complexité totale sera de kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp.

for each vertex u in G.V n fsg
	u.d = infinity
s.d = 0
Q = new create empty Queue
Enqueue(Q, s)
while not QueueEmpty(Q)
	u = Dequeue(Q)
	for each v in G.Adj[u]
		if v.d = 1
			v.d = u.d + 1
			Enqueue(Q, v)

On part d'un sommet et on suit toutes les arêtes incidentes sans les mettre en attente ; on revient en arrière dès que le sommet visité n'a plus de sommet adjacent.

On retient les sommets visités ; chacun sera empilé au plus une fois.

La boucle principale s'exécutera kitxmlcodeinlinelatexdvp|V|finkitxmlcodeinlinelatexdvp fois, la boucle interne kitxmlcodeinlinelatexdvp|E|finkitxmlcodeinlinelatexdvp fois en tout. La complexité totale sera de kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp.

for each vertex u in G.V n fsg
	u.visited = False
S = new create empty stack
Push(S, s)
while not StackEmpty(Q)
	u = Pop(S)
	if u.visited == False
		u.visited = True
		for each v in G.Adj[u]
			if v.visited == False
				Push(S, v)

for each vertex u in G.V
	u.visited = False
DFSRec(G, s)

s.visited = True
for each v in G.Adj[s]
	if v.visited == False
		DFSRec(G, v)

VII-D-1-a. Propriété de sous-structure optimale▲

VII-D-1-b. Cycles▲

VII-D-1-c. Inégalité triangulaire▲

D'un graphe dirigé kitxmlcodeinlinelatexdvpGfinkitxmlcodeinlinelatexdvp et pondéré par la fonction de poids kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp, d'un sommet kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp (l'origine), on veut imposer à chaque sommet deux attributs : la plus grande distance de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à ce nœud (kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp) et le prédécesseur dans un plus court chemin (kitxmlcodeinlinelatexdvpv.\pifinkitxmlcodeinlinelatexdvp), pour former l'arbre des plus courts chemins partant de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp et reconstruire la solution optimale (par la propriété de sous-structure optimale, cette information est suffisante : on connaît un nœud, on y ajoute le chemin le plus court pour le nœud précédent et on a le chemin total ; par application récursive, on trouve le chemin optimal).

Par force brute, la résolution n'est pas forcément aisée : si on essaie tous les chemins possibles dans un graphe, on risque de tomber sur un cycle ; or, dans ce cas, le nombre de chemins est infini ! De même, on peut avoir un nombre de chemins exponentiel par rapport au nombre de sommets et d'arêtes (si on a kitxmlcodeinlinelatexdvpO\left(n\right)finkitxmlcodeinlinelatexdvp nœuds et que presque tous ont un degré deux, on aura kitxmlcodeinlinelatexdvpO\left(2^{n}\right)finkitxmlcodeinlinelatexdvp chemins, d'où la complexité de l'algorithme dans ce cas précis ; dans le pire cas, on peut monter à une complexité de kitxmlcodeinlinelatexdvpO\left(n^{n}\right)finkitxmlcodeinlinelatexdvp, si chaque nœud a un degré kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp, soit pour un graphe hyperconnexe).

VII-D-2-a. Schéma général d'un algorithme▲

// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

while there is one edge (u, v) such that v.d > u.d + w(u; v)
	Pick one edge (u,v)
	// Relaxation
	if v.d > u.d + G.w(u; v)
		v.d = u.d + w(u; v)
		v.p = u

VII-D-2-b. Algorithme de Bellman-Ford▲

// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for i=1 to |G:V| - 1
	for each edge (u, v) in G.E
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for i=1 to |G:V| - 1
	for each edge (u, v) in G.E
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

for each edge (u, v) in G.E
	if v.d > u.d + w(u, v)
		return False
return true

// Initialisation
L = TopSort(G)
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for each vertex u, taken in their order in L
	for each vertex v in G.Adj[u]
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

VII-D-2-c. Parcours en largeur▲

for each vertex u in G.V\{s}
	u.d = 1
s.d = 0
Q = new empty Queue

Enqueue(Q, s)
while not QueueEmpty(Q)
	u = Dequeue(Q)
	for each v in G:Adj[u]
		if v.d = 1
			v.d = u.d + 1
			Enqueue(Q, v)

VII-D-2-d. Algorithme de Dijkstra▲

// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0
S = empty set
Q = new empty min priority queue from G.V

while not QueueEmpty(Q)
	u = QueueExtractMin(Q)
	S = union of S and {u}
	for each v 2 G:Adj[u]
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u
			QueueSetPriority(v, v.d)

D'un graphe dirigé kitxmlcodeinlinelatexdvpGfinkitxmlcodeinlinelatexdvp et de sa fonction de poids kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp, on cherche à produire une matrice kitxmlcodeinlinelatexdvpDfinkitxmlcodeinlinelatexdvp de taille kitxmlcodeinlinelatexdvpn\times nfinkitxmlcodeinlinelatexdvp, où

VII-D-3-a. Réutilisation des algorithmes de Bellman-Ford ou Dijkstra▲

VII-D-3-b. Algorithme de Floyd-Marshall▲

D[0] = W
for k = 1 to n
	let D[k] = (d[k][i][j]) be a new n * n matrix
	for i = 1 to n
		for j = 1 to n
			d[k][i][j] = min{d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]}
return D[n]

Un arbre couvant minimal est un sous-ensemble d'arêtes du graphe initial ; ainsi, on part avec un ensemble kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp vide auquel on ajoute des arêtes en respectant l'invariant qu'il existe un arbre couvrant minimal qui contienne ces arêtes. À cette fin, on définit la notion d'arête sûre : une arête kitxmlcodeinlinelatexdvp\left(u,v\right)finkitxmlcodeinlinelatexdvp sera sûre pour kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp si et seulement s'il existe un arbre couvrant minimal qui contient les arêtes de kitxmlcodeinlinelatexdvpA\cup\left\{ \left(u,v\right)\right\}finkitxmlcodeinlinelatexdvp.

On se retrouve donc avec l'algorithme générique suivant, il faudra encore caractériser plus avant les arêtes sûres.

A = empty set
while A is not a spanning tree
	find an edge (u, v) that is safe for A
	A = union of A and {(u, v)}
return A

Avec kitxmlcodeinlinelatexdvpS\subsetneq Afinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpA\subseteq Efinkitxmlcodeinlinelatexdvp, on définit la coupure kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp comme une partition des sommets en deux ensembles disjoints kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpV\setminus Sfinkitxmlcodeinlinelatexdvp, l'arête traverse d'une coupure kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp comme une arête dont une extrémité est dans kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp et l'autre dans kitxmlcodeinlinelatexdvpV\setminus Sfinkitxmlcodeinlinelatexdvp. Une coupure respecte kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp si et seulement s'il n'y a pas d'arête dans kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp qui traverse la coupure.

VII-E-3-a. Propriété des choix gloutons optimaux▲

VII-E-4. Algorithme de Kruskal▲

A = empty set
P = empty set
for each vertex v 2 G:V
	P = union of P and {{v}}
for each (u, v) in G.E taken into nondecreasing order of weight
	P1 = subset in P containing u
	P2 = subset in P containing v
	if P1 != P2
		A = union of A and {(u, v)}
		P = P1 merged with P2
return A