Arbres de recherche, tas et files de priorité

Cours · informatique (MP2I/MPI), chapitre 11 · MP2I et MPI · le début du chapitre, la suite sur Adloun

Un tas binaire et le tableau qui le représente : chaque parent est plus petit que ses enfants.

11.1 Deux invariants, deux structures

Le chapitre précédent s'est achevé sur une inégalité : la hauteur d'un arbre à $n$ nœuds est comprise entre $Θ (lo g n)$ et $n - 1$ . Comme toutes les opérations coûtent $O (h)$ , il ne suffit pas d'avoir un arbre : il faut y maintenir un invariant qui l'empêche de dégénérer, et qui réponde à la question qu'on lui pose.

Ce chapitre présente deux invariants, et ils sont différents parce que les questions le sont.

	Arbre binaire de recherche	Tas
Invariant	gauche $<$ racine $<$ droit	racine $\leq$ ses deux fils
Question	« $x$ est-il présent ? »	« quel est le minimum ? »
Forme	quelconque, à équilibrer	toujours complet

Un tas ne sait pas chercher un élément quelconque ; un arbre de recherche ne donne pas son minimum en $O (1)$ . Le chapitre chap:abstraction l'annonçait : une structure ne répond bien qu'aux questions pour lesquelles elle est faite.

11.2 L'arbre binaire de recherche

Définition 11.1Invariant d'ABR

Un arbre binaire étiqueté par un ensemble totalement ordonné est un arbre binaire de recherche si, en tout nœud d'étiquette $e$ :

toutes les étiquettes du sous-arbre gauche sont $< e$ ;
toutes celles du sous-arbre droit sont $> e$ .

Le programme note « l'importance de munir l'ensemble des clés d'un ordre total » : sans comparabilité de deux clés quelconques, la descente n'a pas de sens.

AttentionL'invariant porte sur tout le sous-arbre, pas sur les fils

C'est la faute classique. L'arbre ci-dessous vérifie la condition en chaque nœud pris avec ses deux fils immédiats, et n'est pourtant pas un ABR :

$9 > 3$ le place bien à droite de $3$ , mais il est dans le sous-arbre gauche de $8$ , où tout doit être $< 8$ . Une recherche de $9$ partirait à droite et ne le trouverait jamais.

◆Théorème 11.2Le parcours infixe d'un ABR est trié

Pour tout arbre binaire de recherche $a$ , la liste infixe a est strictement croissante.

Démonstration

Par induction structurelle. Pour $Vide$ , la liste vide est triée.

Soit $a = N œ ud (g, e, d)$ un ABR. Alors $g$ et $d$ en sont aussi, donc par hypothèse d'induction infixe g et infixe d sont triées. Le parcours infixe rend leur concaténation avec $e$ au milieu. Or toutes les étiquettes de $g$ sont $< e$ et toutes celles de $d$ sont $> e$ : la liste obtenue est donc croissante à la jonction comme à l'intérieur de chaque morceau.

ImportantUne caractérisation qui donne un test

Ce théorème fournit la manière la plus sûre de vérifier qu'un arbre est un ABR : parcourir en infixe et contrôler que la suite croît. C'est en $Θ (n)$ , et cela teste l'invariant global, là où une vérification nœud par nœud laisserait passer le contre-exemple ci-dessus.

11.2.1 Rechercher, insérer


(* Renvoie true si x figure dans l'ABR a. Complexité : O(h). *)
let rec appartient x = function
  | Vide -> false
  | Noeud (g, e, d) ->
      if x = e then true
      else if x < e then appartient x g       (* tout ce qui est > e est à droite *)
      else appartient x d

(* Renvoie l'ABR obtenu en insérant x ; si x y figure déjà, renvoie a inchangé. *)
let rec insere x = function
  | Vide -> Noeud (Vide, x, Vide)             (* on insère TOUJOURS en feuille *)
  | Noeud (g, e, d) as a ->
      if x = e then a
      else if x < e then Noeud (insere x g, e, d)
      else Noeud (g, e, insere x d)

Exercices du chapitre

Le test local ne suffit pas corrigé
Chercher dans un tas coûte $Ω (n)$ corrigé
Fusionner deux tas : réinsérer ou reconstruire ? corrigé
Le $k$ -ième plus petit en $O (h)$ corrigé
Une file de priorité sur des couples, et la diminution de clé corrigé
Problème — La suppression dans un ABR, et la dégradation qu'elle provoque corrigé

La suite du cours · Tous les exercices du chapitre