Arbre binaire de recherche (AVL)

Sujet: Arbre binaire de recherche (AVL) Mar 22 Nov 2011 - 17:29

Bonjour,

Je suis en train d'écrire une bibliothèque de fonctions de gestion d'arbre binaire de recherche.

Je n'ai pas la prétention de donner un cours d'informatique, certains d'entre vous connaissent déjà les arbres binaires de recherche Wink

et il existe une foule de tuto très bien écrits sur ce sujet.

Ce petit "tuto" s'adresse surtout à ceux qui n'en on jamais entendu parlé et qui ont la flemme de faire des recherches, peut être que cela éveillera la curiosité de certains Wink

A la fin (pour ceux qui sont pressés), se trouve ma petite bibliothèque en cours de développement... Wink

Un enregistrement est composé de trois champs :
- une clé,
- un fils gauche,
- un fils droit.

Arbre binaire de recherche (AVL) Pic0

Le fils gauche [FG] correspond à l'indice d'un élément inférieur à la clé.
Le fils droit [FD] correspond à l'indice d'un élément supérieur à la clé.

Prenons un exemple : Nous allons réaliser une liste de caractères.
Au départ je n'ai pas d'enregistrement. J'insère un élément contenant la valeur "D". Cette valeur (clé) pourrait être un prénom, un n°de tel, le nom d'un animal,etc...

Je me retrouve avec ceci:
Arbre binaire de recherche (AVL) Pic1

"D" est le premier élément de notre arbre, il possède l'indice 1. Par définition cet enregistrement est la racine de notre arbre.

Comme il n'y a pas d'autres éléments en dessous, les fils gauche et droit sont à zéro.

J'insère une nouvelle lettre : "B" (indice 2).

Donc je compare "B" avec "D" : c'est inférieur donc j'indique que "B" se trouve à gauche de "D" (dans le fils gauche de "D" je met l'indice de "B" soit 2)

Arbre binaire de recherche (AVL) Pic2

L'enregistrement "B" est ce que l'on appelle une feuille

Faisons maintenant la même chose avec la lettre F (indice 3):
F est supérieur à D donc on crée le lien sur le fils droit de "D"

Arbre binaire de recherche (AVL) Pic3

Jusque là tout va bien...

Insérons une nouvelle lettre : "C" (indice 4)
On compare "C" avec "D" c'est inférieur, mais l'emplacement à gauche n'est pas libre, donc on va comparer avec la lettre qui suit : "B"
"C" est supérieur à "B" et son fils droit est libre donc on crée le lien entre "B".Filsdroit et la nouvelle lettre "C" :

Arbre binaire de recherche (AVL) Pic4

On répète autant de fois que l'on veut...

Quel est l’intérêt d'un tel système ?

Imaginons cette arborescence :

Arbre binaire de recherche (AVL) Pic6

Si je dois chercher par exemple "Eric", je vais d'abord comparer avec "Denis" -> c'est supérieur, donc tout ce qui se trouve à gauche de "Denis" ne sera pas testé ! On compare ensuite avec "Fabrice" -> c'est inférieur, donc tout ce qui se trouve à droite de "Fabrice" ne sera pas testé ! On regarde à gauche, on compare et on a trouvé !!!

Dans cet exemple, au pire, on aura 3 comparaisons maxi pour une liste de 7 prénoms.

Imaginez maintenant que vous avez une liste de 1000 éléments...
A la première comparaison, vous éliminez 500 enregistrements d'un coup ! et ainsi de suite...

L'exemple ci-dessus est le cas idéal, c'est à dire que votre arborescence est équilibrée : il y a autant de fils à droite qu'à gauche de la racine et chaque nœud (enregistrement intermédiaire) est complet.

Suivant l'ordre d'insertion vous pouvez très bien obtenir une liste d'éléments chainé tous à gauche ou à droite... dans le cas ci-dessous, le système n'offre plus aucun intérêt...
Arbre binaire de recherche (AVL) Pic7

Heureusement qu'il existe des mécanismes d'auto-équilibrage de l'arborescence (à base de rotation des éléments) au moment de l'insertion d'un élément, c'est ce que nous appelons des arbres auto-équilibrés. C'est un peu compliqué à expliquer mais je vous renvoie à Google pour ceux qui veulent plus d'info...

Pour ma librairie, je me suis basé sur les arbres auto-équilibrés de type AVL.

Pour l'instant j'ai mis en place les procédures de base pour insérer, rechercher, trier un arbre binaire classique (non-équilibré).

La procédure d'insertion avec auto-équilibrage est en cours d'écriture...mais cela vous donne déjà une idée de la bête... Wink

Code:: HIDE 0:HEIGHT 0,500:WIDTH 0,SCREEN_X-50:TOP 0,SCREEN_Y/3:LEFT 0,50
DIM DEBUG:DEBUG=0
DIM LST_KEY:LST_KEY=100
DIM LST_RESULT: LST_RESULT=101
DIM PILE:PILE=102

DIM RACINE:RACINE=1
DIM NB_MAX:NB_MAX=100
DIM NB_CHAMPS:NB_CHAMPS=4

DIM CLE:CLE=0
DIM GAUCHE:GAUCHE=1
DIM DROITE:DROITE=2
DIM BAL:BAL=3

DLIST LST_KEY
DLIST LST_RESULT

IF DEBUG = 0
DLIST PILE
ELSE
LIST PILE:FORM 1:PARENT PILE,1:LEFT 1, LEFT(0)+WIDTH(0)
END_IF

DIM NB_PILE:NB_PILE=50

'
' 0 : cle
' 1 : gauche
' 2 : droite
' 3 : balance

DIM Arbre(NB_MAX,NB_CHAMPS-1),retour

LABEL ABR_Insert
LABEL ABR_Profondeur
LABEL ABR_Recherche
LABEL ABR_GetIndice
LABEL ABR_Hauteur
LABEL ABR_ParcoursInfixe
LABEL AVL_RotD
LABEL AVL_RotG

LABEL CreateObject
LABEL PILE_Clr
LABEL STRCMP

SHOW 0
ITEM_ADD PILE,"Test"
DIM A$

' Cet ordre correspond pour l'instant à un arbre équilibré :

DATA "Philippe","Hervé","William","Denis","Laurent","Thierry","Yvan","Bernard","Françoise","Jean","Nicolas"
DATA "Roger","Vincent","Xavier","Zoé","Albert","Céline","Etienne","Gilles","Isabelle","Kevin"
DATA "Martine","Odile","Quentin","Sophie","Ursule"
DATA "###"
'
' [P]
' _____________/ \_____________
' [H] [W]
' _____/ \_____ _____/ \_____
' [D] [L] [T] [Y]
' / \ / \ / \ / \
' [B] [F] [J] [N] [R] [V] [X] [Z]
' / \ / \ / \ / \ / \ /
' [A] [C] [E] [G] [I] [K] [M] [O] [Q] [S] [U]
'
' [01]
' _________________/\_________________
' [02] [03]
' _______/\_______ _______/\_______
' [04] [05] [06] [07]
' __/\__ __/\__ __/\__ __/\__
' [08] [09] [10] [11] [12] [13] [14] [15]
' /\ /\ /\ /\ /\ /
' [16][17] [18][19] [20][21] [22][23] [24][25] [26]

DIM I

PRINT "--- INSERTION -----------------------------------------"
PRINT "RACINE:";RACINE

READ A$
PRINT "Insertion de :"
WHILE A$<>"###"
PRINT A$;",";
ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,A$:GOSUB ABR_Insert
READ A$
END_WHILE

' FOR I=1 TO COUNT(LST_KEY)
' print Arbre(I,CLE);" ";Arbre(I,GAUCHE);" ";Arbre(I,DROITE);
' IF I=RACINE:PRINT " *":ELSE:PRINT:END_IF
' NEXT I

PRINT:PRINT "-------------------------------------------------------------"
ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Albert":GOSUB ABR_Recherche
PRINT "Recherche('Albert')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr

ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Zoé":GOSUB ABR_Recherche
PRINT "Recherche('Zoé')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr

ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Thierry":GOSUB ABR_Recherche
PRINT "Recherche('Thierry')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr

ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Sabine":GOSUB ABR_Recherche
PRINT "Recherche('Sabine')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr

PRINT
ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Hervé":GOSUB ABR_GetIndice
retour = VAL(ITEM_READ$(PILE,COUNT(PILE))): GOSUB PILE_Clr
PRINT "GetIndice('Hervé')=";retour
PRINT

ITEM_ADD PILE,STR$(retour)
PRINT "Hauteur('";ITEM_READ$(LST_KEY,retour);"')=";: GOSUB ABR_Hauteur
PRINT ITEM_READ$(PILE,COUNT(PILE)):GOSUB PILE_Clr

PRINT: PRINT "ROTATION_DROITE(";RACINE;") -> ";
ITEM_ADD PILE,STR$(RACINE):GOSUB AVL_RotD
RACINE = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
PRINT "RACINE:";RACINE
' FOR I=1 TO COUNT(LST_KEY)
' print Arbre(I,CLE);Arbre(I,GAUCHE);Arbre(I,DROITE);
' IF I=RACINE:PRINT " *":ELSE:PRINT:END_IF
' NEXT I
PRINT

ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Albert":GOSUB ABR_Recherche
PRINT "Recherche('Albert')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr
ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Zoé":GOSUB ABR_Recherche
PRINT "Recherche('Zoé')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr
ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"Thierry":GOSUB ABR_Recherche
PRINT "Recherche('Thierry')=";ITEM_READ$(PILE,COUNT(PILE));: GOSUB PILE_Clr
PRINT " -->En ";ITEM_READ$(PILE,COUNT(PILE));" comparaison(s)":GOSUB PILE_Clr
PRINT

' ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"H":GOSUB ABR_GetIndice
' retour = VAL(ITEM_READ$(PILE,COUNT(PILE)))
' PRINT "GetIndice('H')=";retour: GOSUB PILE_Clr

ITEM_ADD PILE,STR$(retour)
PRINT "Hauteur('";ITEM_READ$(LST_KEY,retour);"')=";: GOSUB ABR_Hauteur
PRINT ITEM_READ$(PILE,COUNT(PILE)):GOSUB PILE_Clr
PRINT

PRINT "ROTATION_GAUCHE(";RACINE;") -> ";
ITEM_ADD PILE,STR$(RACINE):GOSUB AVL_RotG
RACINE = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
PRINT "RACINE:";RACINE
PRINT
' FOR I=1 TO COUNT(LST_KEY)
' print Arbre(I,CLE);Arbre(I,GAUCHE);Arbre(I,DROITE);
' IF I=RACINE:PRINT " *":ELSE:PRINT:END_IF
' NEXT I

' ITEM_ADD PILE,STR$(RACINE):ITEM_ADD PILE,"H":GOSUB ABR_GetIndice
' retour = VAL(ITEM_READ$(PILE,COUNT(PILE)))
' PRINT "GetIndice('H')=";retour: GOSUB PILE_Clr

ITEM_ADD PILE,STR$(retour)
PRINT "Hauteur('";ITEM_READ$(LST_KEY,retour);"')=";: GOSUB ABR_Hauteur
PRINT ITEM_READ$(PILE,COUNT(PILE)):GOSUB PILE_Clr
PRINT

IF VARIABLE("Parcours_id")=1
Parcours_id=RACINE:CLEAR LST_RESULT
END_IF
GOSUB ABR_ParcoursInfixe
FOR I=1 TO COUNT(LST_RESULT)
PRINT ITEM_READ$(LST_KEY,Arbre(VAL(ITEM_READ$(LST_RESULT,I)),CLE));",";
NEXT I
PRINT

END

' ******************************************************************************
' ******************************************************************************

ABR_Hauteur:
IF VARIABLE("ABR_Hauteur_id")=0
DIM ABR_Hauteur_id,ABR_Hauteur_max,ABR_Hauteur_cpt
ABR_Hauteur_id=-1
END_IF
if ABR_Hauteur_id=-1
ABR_Hauteur_id=VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
end_if
if Arbre(ABR_Hauteur_id, GAUCHE)<>0
ABR_Hauteur_cpt=ABR_Hauteur_cpt+1
ABR_Hauteur_max=max(ABR_Hauteur_max,ABR_Hauteur_cpt)
ITEM_ADD PILE, STR$(ABR_Hauteur_id) : ' Sauvegarde dans la pile
ABR_Hauteur_id=Arbre(ABR_Hauteur_id, GAUCHE) : GOSUB ABR_Hauteur
' Restitution du contexte
ABR_Hauteur_id= ITEM_READ$(PILE, COUNT(PILE)) : GOSUB PILE_Clr
END_IF
IF Arbre(ABR_Hauteur_id, DROITE)<>0
ABR_Hauteur_cpt=ABR_Hauteur_cpt+1
ABR_Hauteur_max=max(ABR_Hauteur_max,ABR_Hauteur_cpt)
ITEM_ADD PILE, STR$(ABR_Hauteur_id)
ABR_Hauteur_id=Arbre(ABR_Hauteur_id, DROITE)
GOSUB ABR_Hauteur
ABR_Hauteur_id= ITEM_READ$(PILE, COUNT(PILE)): GOSUB PILE_Clr
END_IF
ABR_Hauteur_cpt=ABR_Hauteur_cpt-1
IF ABR_Hauteur_cpt=-1
ITEM_ADD PILE,STR$(ABR_Hauteur_max)
ABR_Hauteur_max=0
ABR_Hauteur_cpt=0
END_IF
RETURN

ABR_GetIndice:
IF VARIABLE("ABR_GetIndice_id")=0
DIM ABR_GetIndice_id : ABR_GetIndice_id=-1
DIM ABR_GetIndice_key$,ABR_GetIndice_value
DIM ABR_GetIndice_return
END_IF
IF ABR_GetIndice_id < 0
ABR_GetIndice_key$= ITEM_READ$(PILE,COUNT(PILE)):GOSUB PILE_Clr
END_IF
ABR_GetIndice_id = VAL(ITEM_READ$(PILE,COUNT(PILE))) : GOSUB PILE_Clr
IF ABR_GetIndice_id = 0 : ' Si on est arrivé sur une terminaison : c'est qu'on a pas trouvé !
ABR_GetIndice_return = 0 : ABR_GetIndice_id=-1
ELSE : ' comparaison des clés
ITEM_ADD PILE,ABR_GetIndice_key$
ITEM_ADD PILE,ITEM_READ$(LST_KEY, Arbre(ABR_GetIndice_id, 0))
GOSUB STRCMP
ABR_GetIndice_value = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
SELECT ABR_GetIndice_value
CASE -1: ITEM_ADD PILE,Arbre(ABR_GetIndice_id,GAUCHE):GOSUB ABR_GetIndice
CASE 1 : ITEM_ADD PILE,Arbre(ABR_GetIndice_id,DROITE):GOSUB ABR_GetIndice
CASE 0 : ABR_GetIndice_return=ABR_GetIndice_id:ABR_GetIndice_id=-1
END_SELECT
END_IF
if ABR_GetIndice_id=-1
ITEM_ADD PILE,STR$(ABR_GetIndice_return)
ABR_GetIndice_id=-2
end_if
RETURN

ABR_Insert:
IF VARIABLE("ABR_Insert_id")=0
DIM ABR_Insert_id:ABR_Insert_id=-1
DIM ABR_Insert_str$,ABR_Insert_value
END_IF
IF ABR_Insert_id=-1
ABR_Insert_str$=ITEM_READ$(PILE,COUNT(PILE)): GOSUB PILE_Clr
END_IF
ABR_Insert_id=VAL(ITEM_READ$(PILE,COUNT(PILE))): GOSUB PILE_Clr

IF COUNT(LST_KEY)=0
ITEM_ADD LST_KEY,ABR_Insert_str$: Arbre(ABR_Insert_id,CLE)=COUNT(LST_KEY)
Arbre(ABR_Insert_id,GAUCHE)=0:Arbre(ABR_Insert_id,DROITE)=0
ABR_Insert_id=-1
ELSE
ITEM_ADD PILE,ABR_Insert_str$:ITEM_ADD PILE,ITEM_READ$(LST_KEY,Arbre(ABR_Insert_id,CLE)): GOSUB STRCMP
ABR_Insert_value = VAL(ITEM_READ$(PILE,COUNT(PILE))) : GOSUB PILE_Clr: ' pour STRCMP
SELECT ABR_Insert_value
CASE -1
IF Arbre(ABR_Insert_id,GAUCHE)=0
ITEM_ADD LST_KEY,ABR_Insert_str$
Arbre(ABR_Insert_id,GAUCHE)=COUNT(LST_KEY)
Arbre(COUNT(LST_KEY),CLE)=COUNT(LST_KEY)
Arbre(COUNT(LST_KEY),GAUCHE)=0:Arbre(COUNT(LST_KEY),DROITE)=0
ABR_Insert_id=-1
ELSE
ITEM_ADD PILE,STR$(Arbre(ABR_Insert_id,GAUCHE)):GOSUB ABR_Insert
END_IF
CASE 0
RETURN : ' pas de doublon pour l'instant
CASE 1
IF Arbre(ABR_Insert_id,DROITE)=0
ITEM_ADD LST_KEY,ABR_Insert_str$
Arbre(ABR_Insert_id,DROITE)=COUNT(LST_KEY)
Arbre(COUNT(LST_KEY),CLE)=COUNT(LST_KEY)
Arbre(COUNT(LST_KEY),GAUCHE)=0:Arbre(COUNT(LST_KEY),DROITE)=0
ABR_Insert_id=-1
ELSE
ITEM_ADD PILE,STR$(Arbre(ABR_Insert_id,DROITE)):GOSUB ABR_Insert
END_IF
END_SELECT
END_IF

RETURN

AVL_RotD:
IF VARIABLE("AVL_RotD_Pivot")=0 THEN DIM AVL_RotD_Pivot,AVL_RotD_id
AVL_RotD_id = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
AVL_RotD_pivot= Arbre(AVL_RotD_id,GAUCHE)
Arbre(AVL_RotD_id,GAUCHE)=Arbre(AVL_RotD_pivot,DROITE)
Arbre(AVL_RotD_pivot,DROITE)=AVL_RotD_id
ITEM_ADD PILE,STR$(AVL_RotD_pivot)
RETURN

AVL_RotG:
IF VARIABLE("AVL_RotG_Pivot")=0 THEN DIM AVL_RotG_Pivot,AVL_RotG_id
AVL_RotG_id = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
AVL_RotG_pivot = Arbre(AVL_RotG_id,DROITE)
Arbre(AVL_RotG_id,DROITE)=Arbre(AVL_RotG_pivot,GAUCHE)
Arbre(AVL_RotG_pivot,GAUCHE)=AVL_RotG_id
ITEM_ADD PILE,STR$(AVL_RotG_pivot)
RETURN

' ------------------------------------------------------------------------------
' Calcul de la profondeur d'un noeud
' ------------------------------------------------------------------------------
' La racine a une profondeur de 0, ses fils ont une profondeur de 1,
' ses petits fils ont n eprofondeur de 2, etc...
' retour = Profondeur(indice_noeud)
' ------------------------------------------------------------------------------
ABR_Profondeur:
IF VARIABLE("ABR_Profondeur_id")=0 THEN DIM ABR_Profondeur_id
ABR_Profondeur_id = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
ITEM_ADD PILE,ITEM_READ$(LST_KEY,Arbre(ABR_Profondeur_id,CLE)):GOSUB ABR_Recherche
ABR_Profondeur_id = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
IF ABR_Profondeur_id=1
' on récupère le nb de comparaison
ABR_Profondeur_id = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
ABR_Profondeur_id=ABR_Profondeur_id-1 : ' profondeur
ELSE
GOSUB PILE_Clr
ABR_Profondeur_id=-1
END_IF
ITEM_ADD PILE,STR$(ABR_Profondeur_id)
RETURN

' ------------------------------------------------------------------------------
' Recherche d'un élément dans un arbre
' ------------------------------------------------------------------------------
' resultat, nb_comparaisons = ABR_Recherche(noeud)
' Note : Renvoie 2 valeurs.
' ------------------------------------------------------------------------------
ABR_Recherche:
IF VARIABLE("Recherche_id")=0
DIM Recherche_id : Recherche_id=-1
DIM Recherche_key$,Recherche_value
DIM Recherche_return,Recherche_Nb
END_IF
IF Recherche_id<0 : ' si 1er passage
Recherche_key$ = ITEM_READ$(PILE,COUNT(PILE)): GOSUB PILE_Clr
Recherche_Nb = 0
END_IF
Recherche_id = VAL(ITEM_READ$(PILE,COUNT(PILE))) : GOSUB PILE_Clr
IF Recherche_id = 0 :' Si on est arrivé sur une terminaison : on a pas trouvé !
Recherche_return = 0 : Recherche_id=-1
ELSE : ' comparaison des clés
ITEM_ADD PILE,Recherche_key$: ITEM_ADD PILE,ITEM_READ$(LST_KEY, Arbre(Recherche_id, 0))
Recherche_Nb = Recherche_Nb + 1 : GOSUB STRCMP
Recherche_value = VAL(ITEM_READ$(PILE,COUNT(PILE))):GOSUB PILE_Clr
SELECT Recherche_value
CASE -1: ITEM_ADD PILE,Arbre(Recherche_id,GAUCHE):GOSUB ABR_Recherche
CASE 1: ITEM_ADD PILE,Arbre(Recherche_id,DROITE):GOSUB ABR_Recherche
CASE 0: Recherche_return=1:Recherche_id=-1
END_SELECT
END_IF
IF Recherche_id = -1 : ' on empile le résultat
ITEM_ADD PILE,STR$(Recherche_Nb): ITEM_ADD PILE,STR$(Recherche_return)
Recherche_id=-2
END_IF
RETURN

' ------------------------------------------------------------------------------
' ------------------------------------------------------------------------------
' Parcours dans l'ordre de la clé.
' Retour dans LST_RESULT
' ------------------------------------------------------------------------------
ABR_ParcoursInfixe:
IF VARIABLE("Parcours_id")=0
DIM Parcours_id: Parcours_id=RACINE
END_IF
IF Arbre(Parcours_id, GAUCHE)<>0
ITEM_ADD PILE, STR$(Parcours_id) : Parcours_id = Arbre(Parcours_id, GAUCHE)
GOSUB ABR_ParcoursInfixe
Parcours_id = ITEM_READ$(PILE, COUNT(PILE)) : GOSUB PILE_Clr
END_IF
ITEM_ADD LST_RESULT,STR$(Parcours_id)
IF Arbre(Parcours_id, DROITE)<>0
ITEM_ADD PILE, STR$(Parcours_id)
Parcours_id=Arbre(Parcours_id, DROITE)
GOSUB ABR_ParcoursInfixe
Parcours_id= ITEM_READ$(PILE, COUNT(PILE)): GOSUB PILE_Clr
END_IF
RETURN

' ------------------------------------------------------------------------------
' Supression du dernier élément de la pile
' ------------------------------------------------------------------------------
PILE_Clr:
ITEM_DELETE PILE,COUNT(PILE)
RETURN

' ------------------------------------------------------------------------------
' Comparaison de chaine de caractère
' ------------------------------------------------------------------------------
' Retour = STRCMP(S1,S2)
' -1:inferieure 0:egale 1:superieure
' ------------------------------------------------------------------------------
STRCMP:
IF VARIABLE("STRCMP_s1$")=0
DIM STRCMP_s1$,STRCMP_s2$,STRCMP_return
END_IF
DLIST 200
STRCMP_s2$=ITEM_READ$(PILE,COUNT(PILE)):GOSUB PILE_Clr:ITEM_ADD 200,STRCMP_s2$
STRCMP_s1$=ITEM_READ$(PILE,COUNT(PILE)):GOSUB PILE_Clr:ITEM_ADD 200,STRCMP_s1$
SORT 200
STRCMP_return=1
IF STRCMP_s1$=STRCMP_s2$
STRCMP_return=0
ELSE
IF STRCMP_s1$=ITEM_READ$(200,1) THEN STRCMP_return=-1
END_IF
DELETE 200
ITEM_ADD PILE,STRCMP_return
RETURN

' ------------------------------------------------------------------------------
' Recherche de n° d'objet disponible
' ------------------------------------------------------------------------------
' retour = CreateObject()
' ------------------------------------------------------------------------------
CreateObject:
IF VARIABLE("CreateObject_id")=0 THEN DIM CreateObject_id
CreateObject_id=1
WHILE OBJECT_EXISTS(CreateObject_id)=1 : CreateObject_id = CreateObject_id +1 : END_WHILE
ITEM_ADD PILE,STR$(CreateObject_id)
RETURN

PS: Pour l'instant, ce programme est un programme de test. Quand cela sera au point je ferai un petit programme de démo...

Invité

C'est intéressant, mais je pense que tu es d'accord que pour l'instant j'ai tête pleine avec ce que j'ai en cours. Mais je regarderais un jour de calme.
@+

Sujet: Re: Arbre binaire de recherche (AVL) Mar 22 Nov 2011 - 17:53

Superbe tuto, bon courage Nardo, je test ce soir si je peux Smile

J'ai pratiquement fini ma librairie, il me manque la possibilité de supprimer un élément.
(C'est pas si évident que ça... drunken

)

Donc voilà la librairie : AVL_LIB.bas

Code:: LABEL LIB_AVL_END

' ==============================================================================
' A V L
' Arbre binaire de recherche auto-équilibré
' Auteur : Nardo26 version: 1.0.0 date:02/12/11
' ==============================================================================

' ==============================================================================
' CONSTANTES
' ==============================================================================
DIM AVL_PILE : AVL_PILE = 1000 : ' n° de la liste servant de Pile à la librairie
DIM AVL_KEY : AVL_KEY = 1001 : ' n° de la liste contenant les mots clés
DIM AVL_RESULT : AVL_RESULT = 1002 : ' n° de la liste contenant les mots clés triés par ordre alphabétique

DIM AVL_CLE : AVL_CLE = 0 : ' clé
DIM AVL_GAUCHE : AVL_GAUCHE = 1 : ' fils gauche (inferieur)
DIM AVL_DROITE : AVL_DROITE = 2 : ' fils droit (superieur)
DIM AVL_DESEQ : AVL_DESEQ = 3 : ' Déséquilibre
DIM AVL_DEBUG : AVL_DEBUG = 0 : ' no comment ;)

DIM AVL_NBMAX : AVL_NBMAX = 530 : ' nb maxi d'éléments gérés
DIM AVL_NCHAMPS: AVL_NCHAMPS= 4 : ' nb de champs par élément (cle,gauche,droite,desequilibre)
DIM AVL_RACINE : AVL_RACINE = 1 : ' racine de l'arbre

' ==============================================================================
' Procédures validées
' ==============================================================================

' procédures "publiques"
LABEL AVL_Init
LABEL AVL_Ajouter : ' Insertion d'un élément
LABEL AVL_Recherche : ' Recherche d'un élément
LABEL AVL_ParcoursInfixe: ' Renvoi les clés triées dans la liste AVL_RESULT

' procédures internes
LABEL AVL_RotD : ' Equilibrage - Rotation droite
LABEL AVL_RotG : ' Equilibrage - Rotation gauche
LABEL AVL_RotDG : ' Equilibrage - Rotation droite/gauche
LABEL AVL_RotGD : ' Equilibrage - Rotation gauche/droite
LABEL AVL_Affiche : ' Affichage de l'arbre
LABEL AVL_CreateObject : ' Recherche d'un n° d'objet libre
LABEL AVL_STRCMP : ' Comparaison de chaine
LABEL AVL_PILE_Clr : ' Gestion de la pile - suppression du dernier élément de la pile

' Procédures obsolètes
LABEL ABR_Hauteur : ' Renvoi la hauteur d'un noeud
LABEL ABR_Profondeur : ' Renvoi la profondeur d'un élément
LABEL ABR_Insert : ' Insertion d'un élément
LABEL ABR_RechercheIter : ' Recherche d'un élément (méthode itéractive)

' Init de la pile
IF AVL_DEBUG = 0
DLIST AVL_PILE
ELSE
LIST AVL_PILE
' Formulaire d'affichage de la pile.
DIM AVL_DBG_Form : GOSUB AVL_CreateObject : AVL_DBG_Form = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
FORM AVL_DBG_Form : PARENT AVL_PILE, AVL_DBG_Form : HEIGHT AVL_PILE, SCREEN_Y-50:CAPTION AVL_DBG_Form,"PILE"
' Calcul de durée d'execution d'une portion de code
DIM DBG_TIME
END_IF
ITEM_ADD AVL_PILE, "Haut de pile"

GOTO LIB_AVL_END

' ******************************************************************************
' ******************************************************************************
' ** FIN DE DECLARATION DE LA LIBRAIRIE **
' ******************************************************************************
' ******************************************************************************
AVL_Init:
DIM AVL_Arbre(AVL_NBMAX, AVL_NCHAMPS-1)
' liste des résultats
IF OBJECT_EXISTS(AVL_RESULT)=0 THEN DLIST AVL_RESULT
IF OBJECT_EXISTS(AVL_KEY)= 0 THEN DLIST AVL_KEY
RETURN

' ==============================================================================
' Rotation droite
' ==============================================================================
AVL_RotD:
DIM AVL_RotD_Pivot, AVL_RotD_id
AVL_RotD_id = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_RotD_pivot = AVL_Arbre(AVL_RotD_id, AVL_GAUCHE)
AVL_Arbre(AVL_RotD_id, AVL_GAUCHE) = AVL_Arbre(AVL_RotD_pivot, AVL_DROITE)
AVL_Arbre(AVL_RotD_pivot, AVL_DROITE) = AVL_RotD_id
ITEM_ADD AVL_PILE, STR$(AVL_RotD_pivot)
FREE AVL_RotD_Pivot : FREE AVL_RotD_id
RETURN

' ==============================================================================
' Rotation gauche
' ==============================================================================
AVL_RotG:
DIM AVL_RotG_Pivot, AVL_RotG_id
AVL_RotG_id = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_RotG_pivot = AVL_Arbre(AVL_RotG_id, AVL_DROITE)
AVL_Arbre(AVL_RotG_id, AVL_DROITE) = AVL_Arbre(AVL_RotG_pivot, AVL_GAUCHE)
AVL_Arbre(AVL_RotG_pivot, AVL_GAUCHE) = AVL_RotG_id
ITEM_ADD AVL_PILE, STR$(AVL_RotG_pivot)
FREE AVL_RotG_Pivot : FREE AVL_RotG_id
RETURN

' ==============================================================================
' Rotation Droite-Gauche
' ==============================================================================
AVL_RotDG:
DIM AVL_RotDG_id
AVL_RotDG_id = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
' rotation droite du fils droit
ITEM_ADD AVL_PILE, STR$(AVL_Arbre(AVL_RotDG_id, AVL_DROITE)) : GOSUB AVL_RotD
AVL_Arbre(AVL_RotDG_id, AVL_DROITE) = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
' rotation gauche de l'ensemble du noeud
ITEM_ADD AVL_PILE, STR$(AVL_RotDG_id) : GOSUB AVL_RotG
FREE AVL_RotDG_id
RETURN

' ==============================================================================
' Rotation Gauche-Droite
' ==============================================================================
AVL_RotGD:
DIM AVL_RotGD_id
AVL_RotGD_id = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
' rotation gauche du fils gauche
ITEM_ADD AVL_PILE, STR$(AVL_Arbre(AVL_RotGD_id, AVL_GAUCHE)) : GOSUB AVL_RotG
AVL_Arbre(AVL_RotGD_id, AVL_GAUCHE)= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
' rotation droite de l'ensemble du noeud
ITEM_ADD AVL_PILE, STR$(AVL_RotGD_id) : GOSUB AVL_RotD
FREE AVL_RotGD_id
RETURN

' ==============================================================================
' Ajout + gestion du déséquilibre d'un élément dans l'arbre AVL
' ==============================================================================
AVL_Ajouter:
IF VARIABLE("AVL_Ajouter_str$") = 0
DIM AVL_Ajouter_str$, AVL_Ajouter_id, AVL_Ajouter_value
DIM AVL_Ajouter_A, AVL_Ajouter_AA, AVL_Ajouter_P, AVL_Ajouter_PP
END_IF

AVL_Ajouter_str$ = ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr

' Création de l'élément
ITEM_ADD AVL_KEY, AVL_Ajouter_str$
AVL_Ajouter_id = COUNT(AVL_KEY)
AVL_Arbre(AVL_Ajouter_id, AVL_CLE) = AVL_Ajouter_id
AVL_Arbre(AVL_Ajouter_id, AVL_GAUCHE) = 0 : AVL_Arbre(AVL_Ajouter_id, AVL_DROITE) = 0
AVL_Arbre(AVL_Ajouter_id, AVL_DESEQ) = 0

IF COUNT(AVL_KEY)=1 THEN RETURN
AVL_Ajouter_A = AVL_RACINE : AVL_Ajouter_AA = 0 : AVL_Ajouter_P = AVL_RACINE : AVL_Ajouter_PP = 0
' Descente à la recherche de la feuille, en mémorisant le dernier noeud
' pointé par A dont le désequilibre est +/- 1
WHILE AVL_Ajouter_P <>0
IF AVL_Arbre(AVL_Ajouter_P, AVL_DESEQ)<>0 THEN AVL_Ajouter_A = AVL_Ajouter_P : AVL_Ajouter_AA = AVL_Ajouter_PP
AVL_Ajouter_PP =AVL_Ajouter_P
' comparaison des clés
ITEM_ADD AVL_PILE, AVL_Ajouter_str$ : ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(AVL_Ajouter_P, AVL_CLE)) : GOSUB AVL_STRCMP
AVL_Ajouter_value = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr : ' pour AVL_STRCMP
IF AVL_Ajouter_value <=0
AVL_Ajouter_P=AVL_Arbre(AVL_Ajouter_P, AVL_GAUCHE)
ELSE
AVL_Ajouter_P=AVL_Arbre(AVL_Ajouter_P, AVL_DROITE)
END_IF
END_WHILE
' Adjonction
ITEM_ADD AVL_PILE, AVL_Ajouter_str$ : ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(AVL_Ajouter_PP, AVL_CLE)) : GOSUB AVL_STRCMP
AVL_Ajouter_value = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr : ' pour AVL_STRCMP
IF AVL_Ajouter_value <=0
AVL_Arbre(AVL_Ajouter_PP, AVL_GAUCHE)=AVL_Ajouter_id
ELSE
AVL_Arbre(AVL_Ajouter_PP, AVL_DROITE)=AVL_Ajouter_id
END_IF
' Modification du déséquilibre sur le chemin de AVL_Ajouter_A à AVL_Ajouter_id
AVL_Ajouter_P = AVL_Ajouter_A
WHILE AVL_Ajouter_P <>AVL_Ajouter_id

ITEM_ADD AVL_PILE, AVL_Ajouter_str$ : ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(AVL_Ajouter_P, AVL_CLE)) : GOSUB AVL_STRCMP
AVL_Ajouter_value = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr : ' pour AVL_STRCMP
IF AVL_Ajouter_value <= 0
AVL_Arbre(AVL_Ajouter_P, AVL_DESEQ)=AVL_Arbre(AVL_Ajouter_P, AVL_DESEQ)+1
AVL_Ajouter_P =AVL_Arbre(AVL_Ajouter_P, AVL_GAUCHE)
ELSE
AVL_Arbre(AVL_Ajouter_P, AVL_DESEQ)=AVL_Arbre(AVL_Ajouter_P, AVL_DESEQ)-1
AVL_Ajouter_P =AVL_Arbre(AVL_Ajouter_P, AVL_DROITE)
END_IF
END_WHILE
IF ABS(AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ))<2 THEN RETURN
' DESEQUILIBRE DE 2
IF AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ)=2
SELECT AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)
CASE 1
' Rotation droite:
ITEM_ADD AVL_PILE, STR$(AVL_Ajouter_A) : GOSUB AVL_RotD : AVL_Ajouter_A = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ)=0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=0
CASE -1
' Rotation gauche-droite:
ITEM_ADD AVL_PILE, STR$(AVL_Ajouter_A) : GOSUB AVL_RotGD : AVL_Ajouter_A = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
SELECT AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ)
CASE 1 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=-1
CASE -1 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=1 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=0
CASE 0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=0
END_SELECT
AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ) = 0
END_SELECT
' DESEQUILIBRE DE -2 (cas symétrique du cas +2)
ELSE
SELECT AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)
CASE -1
' Rotation gauche:
ITEM_ADD AVL_PILE, STR$(AVL_Ajouter_A) : GOSUB AVL_RotG : AVL_Ajouter_A = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ)=0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=0
CASE 1
' Rotation droite-gauche:
ITEM_ADD AVL_PILE, STR$(AVL_Ajouter_A) : GOSUB AVL_RotDG : AVL_Ajouter_A = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
SELECT AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ)
CASE -1 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=1
CASE 1 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=-1 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=0
CASE 0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_DROITE), AVL_DESEQ)=0 : AVL_Arbre(AVL_Arbre(AVL_Ajouter_A, AVL_GAUCHE), AVL_DESEQ)=0
END_SELECT
AVL_Arbre(AVL_Ajouter_A, AVL_DESEQ) = 0
END_SELECT
END_IF
IF AVL_Ajouter_AA = 0
AVL_RACINE = AVL_Ajouter_A
ELSE
ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(AVL_Ajouter_A, AVL_CLE))
ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(AVL_Ajouter_AA, AVL_CLE))
GOSUB AVL_STRCMP : AVL_Ajouter_value = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr : ' pour AVL_STRCMP
IF AVL_Ajouter_value <= 0
AVL_Arbre(AVL_Ajouter_AA, AVL_GAUCHE)=AVL_Ajouter_A
ELSE
AVL_Arbre(AVL_Ajouter_AA, AVL_DROITE)=AVL_Ajouter_A
END_IF
END_IF
RETURN

' ==============================================================================
' Parcours de l'arbre dans l'ordre de la clé.
' Retour dans AVL_RESULT
' ==============================================================================
AVL_ParcoursInfixe:
IF VARIABLE("ABR_ParcoursInfixe_entry")=0
DIM ABR_ParcoursInfixe_entry : ABR_ParcoursInfixe_entry= COUNT(AVL_PILE)
DIM Parcours_id : Parcours_id =AVL_RACINE
CLEAR AVL_RESULT
END_IF
IF AVL_Arbre(Parcours_id, AVL_GAUCHE)<>0
ITEM_ADD AVL_PILE, STR$(Parcours_id) : Parcours_id =AVL_Arbre(Parcours_id, AVL_GAUCHE)
GOSUB AVL_ParcoursInfixe
Parcours_id = ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
END_IF
ITEM_ADD AVL_RESULT, ITEM_READ$(AVL_KEY,AVL_Arbre(Parcours_id,AVL_CLE))
IF AVL_Arbre(Parcours_id, AVL_DROITE)<>0
ITEM_ADD AVL_PILE, STR$(Parcours_id) : Parcours_id =AVL_Arbre(Parcours_id, AVL_DROITE)
GOSUB AVL_ParcoursInfixe
Parcours_id = ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
END_IF
IF COUNT(AVL_PILE)=ABR_ParcoursInfixe_entry
FREE Parcours_id : FREE ABR_ParcoursInfixe_entry
END_IF
RETURN

' ==============================================================================
' Recherche d'un élément dans un arbre
' ==============================================================================
' resultat, nb_comparaisons = AVL_Recherche("clé")
' Renvoi 0 si pas trouvé sinon renvoi l'indice de AVL_KEY
' Note : Renvoie 2 valeurs.
' ------------------------------------------------------------------------------
AVL_Recherche:
' Si 1er passage :
IF VARIABLE("ABR_Recherche_return")=0
DIM ABR_Recherche_value, ABR_Recherche_return
DIM ABR_Recherche_Nb , ABR_Recherche_key$, ABR_Recherche_id
ABR_Recherche_key$ = ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
ITEM_ADD AVL_PILE, STR$(AVL_RACINE)
ABR_Recherche_Nb =0
END_IF
ABR_Recherche_id = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
IF ABR_Recherche_id =0 : ' Si on est arrivé sur une terminaison : on a pas trouvé !
ABR_Recherche_return =0 : ABR_Recherche_id=-1
ELSE : ' comparaison des clés
ITEM_ADD AVL_PILE, ABR_Recherche_key$ : ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(ABR_Recherche_id, 0))
GOSUB AVL_STRCMP
ABR_Recherche_Nb =ABR_Recherche_Nb +1
ABR_Recherche_value = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
SELECT ABR_Recherche_value
CASE -1 : ITEM_ADD AVL_PILE, AVL_Arbre(ABR_Recherche_id, AVL_GAUCHE) : GOSUB AVL_Recherche
CASE 1 : ITEM_ADD AVL_PILE, AVL_Arbre(ABR_Recherche_id, AVL_DROITE) : GOSUB AVL_Recherche
CASE 0 : ABR_Recherche_return =ABR_Recherche_id : ABR_Recherche_id=-1
END_SELECT
END_IF
IF VARIABLE("ABR_Recherche_return")=0 THEN RETURN
ITEM_ADD AVL_PILE, STR$(ABR_Recherche_Nb) : ITEM_ADD AVL_PILE, STR$(ABR_Recherche_return)
FREE ABR_Recherche_value : FREE ABR_Recherche_return : FREE ABR_Recherche_Nb
FREE ABR_Recherche_key$ : FREE ABR_Recherche_id
RETURN

' ==============================================================================
' Affichage de l'arbre :
' 4
' |--6
' [4] | |-- 7
' / \ == > | |-- 5
' [2] [6] |--2
' / \ / \ |-- 3
' [1] [3] [5] [7] |-- 1
' ==============================================================================
AVL_Affiche:
IF VARIABLE("AVL_Affiche_hauteur")=0
DIM AVL_Affiche_hauteur, AVL_Affiche_i, AVL_Affiche_prof, AVL_Affiche_id
DIM AVL_Affiche_form : GOSUB AVL_CreateObject : AVL_Affiche_form= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
FORM AVL_Affiche_form : HEIGHT AVL_Affiche_form, SCREEN_Y-50
DIM AVL_Affiche_list : GOSUB AVL_CreateObject : AVL_Affiche_list= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
MEMO AVL_Affiche_list : PARENT AVL_Affiche_list, AVL_Affiche_form
WIDTH AVL_Affiche_list, WIDTH(AVL_Affiche_form)-10
HEIGHT AVL_Affiche_list, HEIGHT(AVL_Affiche_form)-70
BAR_BOTH AVL_Affiche_list
DIM AVL_Affiche_str$
END_IF
AVL_Affiche_prof = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_Affiche_id= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_Affiche_str$=""
IF AVL_Affiche_prof<>0
FOR AVL_Affiche_i=0 TO AVL_Affiche_prof-1
AVL_Affiche_str$=AVL_Affiche_str$+" "
NEXT AVL_Affiche_i
AVL_Affiche_str$ =AVL_Affiche_str$+"|___ "
END_IF
AVL_Affiche_str$ =AVL_Affiche_str$+ ITEM_READ$(AVL_KEY, AVL_Arbre(AVL_Affiche_id, AVL_CLE))
ITEM_ADD AVL_Affiche_list, AVL_Affiche_str$
IF AVL_Arbre(AVL_Affiche_id, AVL_DROITE)<>0
' sauvegarde du contexte
ITEM_ADD AVL_PILE, STR$(AVL_Affiche_id)
ITEM_ADD AVL_PILE, STR$(AVL_Affiche_prof)
' appel
ITEM_ADD AVL_PILE, STR$(AVL_Arbre(AVL_Affiche_id, AVL_DROITE)) : ITEM_ADD AVL_PILE, STR$(AVL_Affiche_prof+1)
GOSUB TEST_Affiche
' restitution du contexte
AVL_Affiche_prof = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_Affiche_id= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
END_IF
IF AVL_Arbre(AVL_Affiche_id, AVL_GAUCHE)<>0
' sauvegarde du contexte
ITEM_ADD AVL_PILE, STR$(AVL_Affiche_id)
ITEM_ADD AVL_PILE, STR$(AVL_Affiche_prof)
' appel
ITEM_ADD AVL_PILE, STR$(AVL_Arbre(AVL_Affiche_id, AVL_GAUCHE)) : ITEM_ADD AVL_PILE, STR$(AVL_Affiche_prof+1)
GOSUB TEST_Affiche
' restitution du contexte
AVL_Affiche_prof = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
AVL_Affiche_id= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
END_IF
RETURN

' ==============================================================================
' Recherche d'un élément dans un arbre
' méthode itéractive:
' ==============================================================================
ABR_RechercheIter:
DIM ABR_RechercheIter_id, ABR_RechercheIter_return, ABR_RechercheIter_Nb
ABR_RechercheIter_id = AVL_RACINE
ABR_RechercheIter_return =1 : ABR_RechercheIter_Nb =0
WHILE (ABR_RechercheIter_return <>0) AND (ABR_RechercheIter_id <>0)
ITEM_ADD AVL_PILE, ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : ' lecture de s1
ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(ABR_RechercheIter_id, AVL_CLE)) : ' lecture de s2
GOSUB AVL_STRCMP : ABR_RechercheIter_Nb =ABR_RechercheIter_Nb +1
' retour de comparaison
ABR_RechercheIter_return = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
SELECT ABR_RechercheIter_return
CASE -1 : ABR_RechercheIter_id =AVL_Arbre(ABR_RechercheIter_id, AVL_GAUCHE)
CASE 1 : ABR_RechercheIter_id =AVL_Arbre(ABR_RechercheIter_id, AVL_DROITE)
END_SELECT
END_WHILE
GOSUB AVL_PILE_Clr : ' suppression de s1 dans la pile
ITEM_ADD AVL_PILE, STR$(ABR_RechercheIter_Nb) : ' ajout du résultat
ITEM_ADD AVL_PILE, STR$(ABR_RechercheIter_id) : ' ajout du résultat
FREE ABR_RechercheIter_id : FREE ABR_RechercheIter_return : FREE ABR_RechercheIter_Nb
RETURN

' ==============================================================================
' Retourne la hauteur d'un noeud
' ==============================================================================
ABR_Hauteur:
IF VARIABLE("ABR_Hauteur_entry")=0
DIM ABR_Hauteur_entry, ABR_Hauteur_id, ABR_Hauteur_max, ABR_Hauteur_cpt
ABR_Hauteur_id= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
ABR_Hauteur_entry=ABR_Hauteur_id
END_IF

IF AVL_Arbre(ABR_Hauteur_id, AVL_GAUCHE)<>0
ABR_Hauteur_cpt=ABR_Hauteur_cpt+1
ABR_Hauteur_max= MAX(ABR_Hauteur_max, ABR_Hauteur_cpt)
ITEM_ADD AVL_PILE, STR$(ABR_Hauteur_id) : ' Sauvegarde dans la pile
ABR_Hauteur_id=AVL_Arbre(ABR_Hauteur_id, AVL_GAUCHE) : GOSUB ABR_Hauteur
' Restitution du contexte
ABR_Hauteur_id= ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
END_IF
IF AVL_Arbre(ABR_Hauteur_id, AVL_DROITE)<>0
ABR_Hauteur_cpt=ABR_Hauteur_cpt+1
ABR_Hauteur_max= MAX(ABR_Hauteur_max, ABR_Hauteur_cpt)
ITEM_ADD AVL_PILE, STR$(ABR_Hauteur_id)
ABR_Hauteur_id=AVL_Arbre(ABR_Hauteur_id, AVL_DROITE) : GOSUB ABR_Hauteur
ABR_Hauteur_id= ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
END_IF
ABR_Hauteur_cpt=ABR_Hauteur_cpt-1
IF ABR_Hauteur_cpt=-1
ITEM_ADD AVL_PILE, STR$(ABR_Hauteur_max)
ABR_Hauteur_max=0
ABR_Hauteur_cpt=0
END_IF
IF ABR_Hauteur_id =ABR_Hauteur_entry
FREE ABR_Hauteur_entry : FREE ABR_Hauteur_id : FREE ABR_Hauteur_max : FREE ABR_Hauteur_cpt
END_IF
RETURN

' ==============================================================================
' Retourne la profondeur d'un noeud
' h = Profondeur("Clé")
' ==============================================================================
ABR_Profondeur:
DIM ABR_Profondeur_return, ABR_Profondeur_val
GOSUB AVL_Recherche
ABR_Profondeur_val = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
ABR_Profondeur_return = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
IF ABR_Profondeur_val =0 THEN ABR_Profondeur_return=0
ITEM_ADD AVL_PILE, STR$(ABR_Profondeur_return-1)
FREE ABR_Profondeur_return : FREE ABR_Profondeur_val
RETURN

' ==============================================================================
' Insertion d'une nouvelle clé dans l'arbre Binaire de Recherche
' Cette méthode ne gère pas le déséquilibre de l'arbre !!!
' ==============================================================================
ABR_Insert:
IF VARIABLE("ABR_Insert_id")=0
DIM ABR_Insert_id : ABR_Insert_id=-1
DIM ABR_Insert_str$, ABR_Insert_value
END_IF
IF ABR_Insert_id=-1
ABR_Insert_str$= ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
END_IF
ABR_Insert_id= VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr

IF COUNT(AVL_KEY)=0
ITEM_ADD AVL_KEY, ABR_Insert_str$ : AVL_Arbre(ABR_Insert_id, AVL_CLE)= COUNT(AVL_KEY)
AVL_Arbre(ABR_Insert_id, AVL_GAUCHE)=0 : AVL_Arbre(ABR_Insert_id, AVL_DROITE)=0
ABR_Insert_id=-1
ELSE
ITEM_ADD AVL_PILE, ABR_Insert_str$ : ITEM_ADD AVL_PILE, ITEM_READ$(AVL_KEY, AVL_Arbre(ABR_Insert_id, AVL_CLE)) : GOSUB AVL_STRCMP
ABR_Insert_value = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr : ' pour AVL_STRCMP
SELECT ABR_Insert_value
CASE -1
IF AVL_Arbre(ABR_Insert_id, AVL_GAUCHE)=0
ITEM_ADD AVL_KEY, ABR_Insert_str$
AVL_Arbre(ABR_Insert_id, AVL_GAUCHE)= COUNT(AVL_KEY)
AVL_Arbre(COUNT(AVL_KEY), AVL_CLE)= COUNT(AVL_KEY)
AVL_Arbre(COUNT(AVL_KEY), AVL_GAUCHE)=0 : AVL_Arbre(COUNT(AVL_KEY), AVL_DROITE)=0
ABR_Insert_id=-1
ELSE
ITEM_ADD AVL_PILE, STR$(AVL_Arbre(ABR_Insert_id, AVL_GAUCHE)) : GOSUB ABR_Insert
END_IF
CASE 0
RETURN : ' pas de doublon pour l'instant
CASE 1
IF AVL_Arbre(ABR_Insert_id, AVL_DROITE)=0
ITEM_ADD AVL_KEY, ABR_Insert_str$
AVL_Arbre(ABR_Insert_id, AVL_DROITE)= COUNT(AVL_KEY)
AVL_Arbre(COUNT(AVL_KEY), AVL_CLE)= COUNT(AVL_KEY)
AVL_Arbre(COUNT(AVL_KEY), AVL_GAUCHE)=0 : AVL_Arbre(COUNT(AVL_KEY), AVL_DROITE)=0
ABR_Insert_id=-1
ELSE
ITEM_ADD AVL_PILE, STR$(AVL_Arbre(ABR_Insert_id, AVL_DROITE)) : GOSUB ABR_Insert
END_IF
END_SELECT
END_IF
RETURN

' ==============================================================================
' Supression du dernier élément de la pile
' ==============================================================================
AVL_PILE_Clr:
IF VARIABLE("PILE_MAX")=0 THEN DIM PILE_MAX
PILE_MAX = MAX(PILE_MAX, COUNT(AVL_PILE))
ITEM_DELETE AVL_PILE, COUNT(AVL_PILE)
RETURN

' ==============================================================================
' Comparaison de chaine de caractère
' ==============================================================================
' Retour = AVL_STRCMP(S1,S2)
' -1:inferieure 0:egale 1:superieure
' ------------------------------------------------------------------------------
AVL_STRCMP:
DIM STRCMP_s1$, STRCMP_s2$, STRCMP_return : ' déclaration des variables temporaires
STRCMP_s2$ = ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
STRCMP_s1$ = ITEM_READ$(AVL_PILE, COUNT(AVL_PILE)) : GOSUB AVL_PILE_Clr
' IF AVL_DEBUG = 1 THEN PRINT " -->compare(";STRCMP_s1$;",";STRCMP_s2$;")"
IF (STRCMP_s1$ =STRCMP_s2$)
STRCMP_return =0
ELSE
' création de notre liste temporaire
DIM STRCMP_lst : GOSUB AVL_CreateObject
STRCMP_lst = VAL(ITEM_READ$(AVL_PILE, COUNT(AVL_PILE))) : GOSUB AVL_PILE_Clr
DLIST STRCMP_lst
STRCMP_return =1
ITEM_ADD STRCMP_lst, STRCMP_s1$ : ITEM_ADD STRCMP_lst, STRCMP_s2$ : SORT STRCMP_lst
IF STRCMP_s1$ = ITEM_READ$(STRCMP_lst, 1) THEN STRCMP_return =-1
DELETE STRCMP_lst : FREE STRCMP_lst
END_IF
ITEM_ADD AVL_PILE, STRCMP_return
FREE STRCMP_s1$ : FREE STRCMP_s2$ : FREE STRCMP_return
RETURN

' ==============================================================================
' Recherche de n° d'objet disponible
' ==============================================================================
' retour = AVL_CreateObject()
' ------------------------------------------------------------------------------
AVL_CreateObject:
DIM CreateObject_id : CreateObject_id =1
WHILE OBJECT_EXISTS(CreateObject_id)=1 : CreateObject_id =CreateObject_id +1 : END_WHILE
ITEM_ADD AVL_PILE, STR$(CreateObject_id) : FREE CreateObject_id
RETURN
LIB_AVL_END:

et l'exemple d'utilisation de la librairie: demo_lib.bas

Code:: #include "AVL_LIB.bas"

AVL_NBMAX=300 : ' nb d'éléments max

' les 4 lignes ci-dessous sont optionnelles
AVL_KEY=201 : ' n° de notre liste contenant les éléments
AVL_RESULT=200 : ' n° de la liste contenant les éléments triés
LIST AVL_KEY : ' on déclare en list pour pouvoir les visualiser
LIST AVL_RESULT

' on construit notre interface
HEIGHT AVL_KEY,HEIGHT(0)-70:TOP AVL_KEY,20
LEFT AVL_RESULT,WIDTH(AVL_KEY):HEIGHT AVL_RESULT,HEIGHT(AVL_KEY):TOP AVL_RESULT,20
ALPHA 1:CAPTION 1,"Initiale":LEFT 1,20:TOP 1,5
ALPHA 2:CAPTION 2,"Triée":LEFT 2,150:TOP 2,5

' on lance l'init de notre système
GOSUB AVL_Init

' ******************************************************************************
' début du test :
' ******************************************************************************
DIM pseudo$,i
DIM nb_comp,bTrouve

' Insertion d'éléments
DATA "Jack","Klaus","Nardo26","jjn4","jean_debord"
DATA "jpcr","Jicehel","ygeronimi","Nicolas"
DATA "JL35","cosmos70","659_minifly","sergeauze"
DATA "wiwi60","EWERSON","jimx78","Georges"
DATA "F6DTL","Severin","Jean Claude","Polaris","mimic"
DATA "###"

READ pseudo$
WHILE pseudo$<>"###"
ITEM_ADD AVL_PILE,pseudo$: GOSUB AVL_Ajouter
READ pseudo$
END_WHILE

' on lance le tri : le résultat apparait dans AVL_RESULT
GOSUB AVL_ParcoursInfixe

' Recherche de notre fantome cosmos ;)
ITEM_ADD AVL_PILE,"cosmos70":GOSUB AVL_Recherche
bTrouve=VAL(ITEM_READ$(AVL_PILE,COUNT(AVL_PILE))): GOSUB AVL_PILE_Clr
nb_comp=VAL(ITEM_READ$(AVL_PILE,COUNT(AVL_PILE))): GOSUB AVL_PILE_Clr
if bTrouve<>0
MESSAGE "cosmos70 est bien dans la liste à l'indice "+str$(bTrouve)+" ! (en "+str$(nb_comp)+" comparaisons)"
ELSE
MESSAGE "cosmos70 n'est pas là..."
END_IF

L'avantage d'un tel système: c'est la rapidité pour faire des recherches d'un élément dans une liste...

Un exemple :
J'ai calculé qu'il me faut 7.5ms pour faire une comparaison d'un nom par rapport à un autre.
Admettons que mon PC rame: je compte le double soit 15ms/comp.

En 0.5s j'ai réalisé 33 comparaisons ce qui revient à dire que j'ai parcouru 33 noeuds de mon arbre...
Puisque je descend d'un niveau à chaque comparaison, j'ai un arbre de 33 niveaux .
Un arbre de 33 niveaux contient : (2^33)-1 élements soit : 8 589 934 591 éléments !

En clair: je mets 0.5s pour retrouver 1 élément parmis les 8 589 934 591 autres....
Bon cela reste de la théorie car il y a d'autres facteurs qui ralentissent le système. Mais cela donne quand même un ordre d'idée... Wink

Reste à faire :
- La suppression
- Le chargement et la sauvegarde
- envisager de ne pas avoir en RAM les éléments et de passer par une table d'index (seek sur fichier)
- Modifier la procédure AVL_ParcoursInfixe (ajout d'un paramètre pour indiquer si on veut dans la liste la clé ou les indices)

Gros boulot Nardo Smile

Merci Jicehel,

Une petite mise à jour :

Ajout de :
- AVL_SaveArbre
- AVL_LoadArbre

Pour ces deux procédures j'ai été obligé de créer une autre librairie que j'ai appelé FIC_LIB.bas
La librairie AVL fonctionne très bien sans, seulement en cas d'absence de FIC_LIB.bas, vous ne pouvez pas faire de chargement/sauvegarde de la base AVL..

L'écriture d'une page sur mon site est en cours d'élaboration.
Vous pouvez quand même charger en attendant les fichiers ICI !

EDIT : Grâce à JL35, plus besoin de FIC_LIB.bas

Petite mise à jour : 1.3.0

- Ajout de n° de version de librairie
- Modif appel aux fct de chargement et de sauvegarde
- Modif appel à la fonction d'affichage
- Mise à jour du programme de démo...

Lien aux fichiers: ICI

Nombre de messages : 7112 Localisation : 77 Date d'inscription : 29/11/2007

Ton tuto est lumineux, je ne me suis pas perdu dans les branches. Ça s'adresse j'imagine à l'exploitation d'une grosse liste de données, je n'en ai pas l'usage pour l'instant, mais c'est bon à savoir.

Ça deviens intéressant sur une certaine quantité de données mais pas trop quand même car on travaille en RAM.

Pour des quantités vraiment importantes, l'idéal serait des arbres 2-3 avec une méthode de hachage pour une gestion sur disque par exemple.

La librairie qu'utilise Jean debord (FBMath) doit certainement s'appuyer sur un système à base d'arbre pour analyser les expressions mathématiques (de même que Panoramic je suppose... )

Pour l'instant le programme est assez confus: la gestion de pile, les pseudo variables locales, tout ça alourdi le code et on perd en lisibilité.

Mais quand Panoramic permettra la création des fonctions, j'en profiterai pour faire un grand nettoyage... et dans ce cas, son utilisation en sera grandement simplifié Wink

Je suis en train de développer une petite démo avec affichage graphique de l'arbre.
Actuellement je gamberge pour faire une zone graphique avec barre de défilement.
D'où l'ouverture d'un autre post... Wink

Je vous passe la démo dans l'état actuel -> ici ! Smile

Quel boulot Nardo !! Ca rend les tests vraiment didactique et on voit bien l'équilibrage. Superbe !! (Bon, arrêtes, on va se sentir minables à force !! (non, je plaisante, continues de nous tirer vers le haut ...))
Vraiment classe

Si ça peut donner des idées à certains, c'est tout bénef ! Wink

Mise à jour de la librairie : 1.4.0
J'ai rajouter une procédure d'affichage sous forme graphique d'un arbre.

Vous pouvez voir la démo : ICI

demo_lib.bas : démo des fct de base
demo_lib2.bas : démo graphique
AVL_LIB.bas : librairie AVL

Pour profiter pleinement de la démo2, il y a aussi le fichier Prenoms3.txt qui permet de créer rapidement un arbre...

Bon soir/jour

Petite mise à jour de la librairie : 1.5.0

- Ajout de AVL_Supprimer (suppression d'un élément dans l'arbre) + debug Divers

Voir demo2.bas Wink

Disponible sur mon site...

» [tuto]Arbre binaire
» Recherche d'une suite de valeurs dans un fichier binaire
» Binaire vous avez dit binaire mais....
» Noob dans un arbre
» Un arbre, un chapeau et rien d'autre.