Cours algorithmique, arbres et graphes

Arbres binaires parfaits et quasi-parfaits

Rappelons qu’un arbre binaire est complet lorsque ses nœuds internes ont leurs deux descendants. On appelle arbre binaire parfait un arbre binaire ayant 2h −1 nœuds où h est sa hauteur. Un arbre binaire parfait est complet. À profondeur p ≤ h−1 on a 2p nœuds. Si p = h−1 ces nœuds sont les feuilles de l’arbre.
Arbre binaire quasi-parfait. Ordonnons les nœuds d’un arbre binaire parfait selon leur profondeur puis de gauche à droite. En premier on a la racine, puis ensuite ses deux fils (de profondeur 1), le gauche, puis le droit, ensuite les nœuds de profondeur 2, d’abord les fils du fils gauche de la racine, le gauche puis le droit, puis les fils du fils droit de la racine etc.
Si on supprime un nombre quelconque de nœuds, en partant des derniers pour cet ordre, on obtient ce qu’on appelle un arbre binaire quasi-parfait . Voici un exemple d’arbre quasi-parfait où les nœuds sont numérotés dans l’ordre, en commençant à zéro. On ne représente pas les éléments contenus dans les nœuds.

Tas et files de priorité

Un tas est une structure de donnée basée sur les arbres binaires quasi-parfaits, qui réalise efficacement les files de priorité, c’est à dire avec de bons résultats de complexité algorithmique sur les opérations fondamentale : ajout, retrait, modification de la priorité d’un élément se font en O(logN).
Définition Un tas max (respectivement tas min ), également appelé maximier (resp.mini
mier ), est un arbre binaire quasi-parfait tel que tout nœud différent de la racine possède une clé (ou priorité) plus petite (resp. plus grande) que celle de son parent (T[i] ≤ T[Parent(i)]). Les deux notions, tas max et tas min, sont symétriques, il suffit d’inverser l’ordre des clés pour passer de l’une à l’autre. On travaille ici avec des tas max.
Propriétés:
Première conséquence de la définition de tas : dans un tas max non vide, l’élément de clé maximum est toujours à la racine. Tout sous-arbre obtenu à partir d’un tas en sélectionnant un nœud et tous ses descendants est encore un tas.
Remarque .Un tableau trié en ordre décroissant est un tas max. Mais il existe plusieurs manières différentes de structurer une liste d’éléments donnée sous la forme d’un tas. Pour la suite, concernant l’implantation en C, on se donne une macro pour le pré-processeur pour simplifier l’adressage des éléments d’un arbre quasi-parfait cette macro ne marche que si l’arbre est noté x). On se donne également une fonction d’échange similaire à celle des tableaux.
/* Macro pour simplifier l’accès aux tableau. */ #define x(indice) (x->tab[indice]) /* Exemple : x(i/2) sera remplacé par (x->tab[i/2]) */
void echangetas(arbrebqp_t x, int i, int j){ element_t e; e = x(i); x(i) = x(j); x(j) = e; }