Implantations des arbres binaires

Dans cette section, pour implanter les arbres binaires, nous étudions les notions Scheme de Sexpressions et de vecteurs.

Ainsi, nous pourrons implanter les arbres binaires de deux façons différentes. Noter que nous ne comparerons pas les performances de ces implantations, une telle étude étant hors du programme de ce cours.
Notion de Sexpression
Considérons l'expression Scheme, (- (+ (- 95) 5) (+ 10 3)). Cela ressemble à une liste (de trois éléments) de type LISTE[a], le premier élément étant -, le second élément étant (+ (- 95) 5) et le dernier élément étant (+ 10 3); à nouveau, (+ (- 95) 5) ressemble à une liste de type LISTE[a] (de trois éléments), le premier élément étant +, le second élément étant (- 95) et le dernier élément étant 5; à nouveau, (- 95) ressemble à une liste (de deux éléments)... Mais ce ne sont pas des listes de type LISTE[a] puisque les éléments ne sont pas de même type. Ce sont des Sexpressions.

Définition
Formellement, on peut définir les Sexpressions par

<Sexpression>	->	<atome>
		`LISTE[`<Sexpression>`]`

<atome>	->	<Nombre>
		<bool>
		<string>
		<Symbole>

(<Nombre>, <bool>, <string> et <Symbole> sont définis dans la carte de référence)

Spécification des fonctions primitives
Tout d'abord, nous devons pouvoir savoir si une Sexpression est un atome ou une liste de Sexpressions. Pour ce faire, il existe en Scheme la fonction list?:

;;; list?: Valeur -> bool ;;; (list? v) rend #t ssi v est une liste (éventuellement vide)

Les autres fonctions de base sont les fonctions que nous avons déjà vues (car, cdr, pair?...).

Une implantation des arbres binaires à l'aide des Sexpressions
La notion de Sexpression permet d'implanter efficacement -- en Scheme -- les arbres binaires (ainsi que tous les types d'arbres). En effet:

lorsque l'arbre est vide, on peut le représenter par la liste vide (qui est également la Sexpression vide);
lorsque l'arbre n'est pas vide, on peut le représenter par une liste contenant l'étiquette de la racine et les deux Sexpressions qui représentent ses sous-arbres immédiats. Notez que l'on a six ordres possibles (d'abord l'étiquette puis le sous arbre gauche et enfin le sous-arbre droit ou le sous-arbre gauche puis l'étiquette et enfin le sous-arbre droit...). Ces six possibilités sont aussi valables les unes que les autres. Il faut en choisir une et s'en souvenir pour toutes les fonctions qui opèrent sur les arbres non vides. Ci-dessous, nous donnons une implantation écrite en mettant systématiquement l'étiquette de la racine en premier et le sous-arbre gauche avant le sous-arbre droit. La compréhension de cette implantation est facile, aussi nous la donnons telle quelle, sans explication.

;;;; Implantation des arbres binaires à l'aide des Sexpressions. Pour les arbres ;;;; non vides, on met systématiquement l'étiquette de la racine en premier et ;;;; le sous-arbre gauche avant le sous-arbre droit. ;;;;;;;;;;;;;;; Constructeurs ;;; ab-noeud : a * ArbreBinaire[a] * ArbreBinaire[a] -> ArbreBinaire[a] ;;; (ab-noeud e B1 B2) rend l'arbre binaire formé de la racine d'étiquette ;;; «e», du sous-arbre gauche «B1» et du sous-arbre droit «B2». (define (ab-noeud e B1 B2) (list e B1 B2)) ;;; ab-vide : -> ArbreBinaire[a] ;;; (ab-vide) rend l'arbre binaire vide. (define (ab-vide) '()) ;;;;;;;;;;;;;; Reconnaisseurs ;;; ab-noeud? : ArbreBinaire[a] -> bool ;;; (ab-noeud? B) rend vrai ssi «B» n'est pas l'arbre vide. (define (ab-noeud? B) (pair? B)) ;;; ab-vide? : ArbreBinaire[a] -> bool ;;; (ab-vide? B) rend vrai ssi «B» est l'arbre vide. (define (ab-vide? B) (not (ab-noeud? B))) ;;;;;;;;;;;;;;;;; Accesseurs ;;; ab-etiquette : ArbreBinaire[a] -> a ;;; (ab-etiquette B) rend l'étiquette de la racine de l'arbre «B» ;;; ERREUR lorsque «B» ne satisfait pas ab-noeud? (define (ab-etiquette B) (car B)) ;;; ab-gauche : ArbreBinaire[a] -> ArbreBinaire[a] ;;; (ab-gauche B) rend le sous-arbre gauche de «B» ;;; ERREUR lorsque B ne satisfait pas ab-noeud? (define (ab-gauche B) (cadr B)) ;;; ab-droit : ArbreBinaire[a] -> ArbreBinaire[a] ;;; (ab-droit B) rend le sous-arbre droit de «B» ;;; ERREUR lorsque «B» ne satisfait pas ab-noeud? (define (ab-droit B) (caddr B))

Notion de Vecteur
Les listes, que nous avons vues dans les cours précédents, permettent de rassembler plusieurs valeurs avec la possibilité d'extraire immédiatement la première valeur (en utilisant car); mais si l'on veut extraire le i^eme élément de la liste (i étant variable), on doit écrire une fonction qui parcourt cette dernière (en utilisant la fonction cdr).

Les vecteurs² sont des structures de données Scheme qui permettent d'agréger plusieurs valeurs -- les composants du vecteur -- avec la possibilité d'extraire immédiatement l'une de ces valeurs.

Plus précisément, un vecteur est caractérisé par des indices, une longueur et des composants:

la longueur du vecteur est le nombre de ses composants,
ses composants sont indicés par les entiers naturels compris entre 0 (inclus) et sa longueur (exclue);
ainsi, le premier composant du vecteur est celui d'indice 0, le deuxième composant est celui d'indice 1... et le dernier composant est celui ayant comme indice sa longueur moins un.

Notons qu'il existe un vecteur particulier, le vecteur vide, dont la longueur est nulle et qui ne contient aucun composant.

Remarque: sous Drscheme, l'affichage de la valeur d'un vecteur commence par le caractère #, continue par la longueur du vecteur et se termine par, entre parenthèses, la liste des valeurs des composants du vecteur.

Spécification des fonctions primitives
Constructeur

La fonction vector, qui peut avoir un nombre quelconque d'arguments, rend un vecteur dont les composants sont ses arguments, dans l'ordre où ils sont donnés:

;;; vector : Valeur ... -> Vecteur ;;; (vector x0 ...) rend le vecteur dont le premier composant (celui d'indice 0) est ;;; «x0», dant le deuxième composant est «x1»... ;;; (vector) rend le vecteur vide (de longueur 0 et qui ne contient aucune valeur)

Exemple

(vector 'a 'b 'c) -> #3(a b c)

Accesseurs

;;; vector-length : Vecteur -> nat ;;; (vector-length V) rend la longueur de «V», c'est-à-dire son nombre de composants

Exemple

(vector-length (vector 'a 'b 'c)) -> 3

Rappelons que le dernier indice d'un vecteur V est égal à (- (vector-length V) 1).

Nous avons dit que la caractéristique d'un vecteur était de pouvoir accéder immédiatement à un composant d'un indice donné. Ceci se fait grâce à la fonction vector-ref:

;;; vector-ref : Vecteur * nat -> Valeur ;;; (vector-ref V k) rend le composant d'indice «k» du vecteur «V» ;;; ERREUR lorsque «k» n'appartient pas à l'intervalle [0 .. (vector-length V)[

Exemples

(vector-ref (vector 'a 'b 'c) 0) -> a

(vector-ref (vector 'a 'b 'c) 2) -> c

(vector-ref (vector 'a 'b 'c) 3) rend une erreur (vector-ref: index 3 out of range [0, 2] for vector: #3(a b c))

Fonctions de conversion

Comme nous l'avons dit, les listes et les vecteurs représentent des suites d'éléments (mais les fonctions de base sont très différentes). Aussi existe-t-il deux fonctions, vector->list et list->vector, qui permettent de passer d'une structure de données à l'autre:

;;; vector->list : Vecteur -> LISTE[Valeur] ;;; (vector->list V) rend la liste des composants du vecteur «V»

Exemple

(vector->list (vector 'a 'b 'c)) -> (a b c)

;;; list->vector : LISTE[Valeur] -> Vecteur ;;; (list->vector L) rend le vecteur ayant comme premier composant le premier ;;; élément de la liste «L», comme deuxième composant le deuxième élément de la liste «L»...

Exemple

(list->vector '(a b c)) -> #3(a b c)

Une implantation des arbres binaires à l'aide des vecteurs
On peut implanter les arbres binaires en utilisant des vecteurs:

l'arbre vide est représenté par le vecteur vide,
un arbre non-vide est représenté par un vecteur de longueur trois ayant comme composants l'étiquette de la racine de l'arbre -- par exemple en indice 0 --, la représentation du sous-arbre gauche -- par exemple en indice 1 -- et la représentation du sous-arbre droit -- par exemple en indice 2.

Constructeurs

La fonction ab-noeud est implantée en utilisant la fonction vector:

;;; ab-noeud : a * ArbreBinaire[a] * ArbreBinaire[a] -> ArbreBinaire[a] ;;; (ab-noeud e B1 B2) rend l'arbre binaire formé de la racine d'étiquette ;;; «e», du sous-arbre gauche «B1» et du sous-arbre droit «B2». (define (ab-noeud e B1 B2) (vector e B1 B2))

La fonction ab-vide est implantée par le vecteur vide en utilisant aussi la fonction vector (mais sans argument):

;;; ab-vide : -> ArbreBinaire[a] ;;; (ab-vide) rend l'arbre binaire vide. (define (ab-vide) (vector))

Reconnaisseurs

Pour savoir si un arbre est, ou n'est pas, vide il suffit de comparer la longueur du vecteur à 0:

;;; ab-vide? : ArbreBinaire[a] -> bool ;;; (ab-vide? B) rend vrai ssi «B» est l'arbre vide. (define (ab-vide? B) (= (vector-length B) 0)) ;;; ab-noeud? : ArbreBinaire[a] -> bool ;;; (ab-noeud? B) rend vrai ssi «B» n'est pas l'arbre vide. (define (ab-noeud? B) (> (vector-length B) 0))

Accesseurs

Pour les accesseurs, on utilise la fonction vector-ref, l'étiquette étant en indice 0, le sous-arbre gauche en indice 1 et le sous-arbre droit en indice 2:

;;; ab-etiquette : ArbreBinaire[a] -> a ;;; (ab-etiquette B) rend l'étiquette de la racine de l'arbre «B» ;;; ERREUR lorsque «B» ne satisfait pas ab-noeud? (define (ab-etiquette B) (vector-ref B 0)) ;;; ab-gauche : ArbreBinaire[a] -> ArbreBinaire[a] ;;; (ab-gauche B) rend le sous-arbre gauche de «B» ;;; ERREUR lorsque B ne satisfait pas ab-noeud? (define (ab-gauche B) (vector-ref B 1)) ;;; ab-droit : ArbreBinaire[a] -> ArbreBinaire[a] ;;; (ab-droit B) rend le sous-arbre droit de «B» ;;; ERREUR lorsque «B» ne satisfait pas ab-noeud? (define (ab-droit B) (vector-ref B 2))