FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC

Développement d'applications avec le langage Panoramic
 
AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  GroupesGroupes  Connexion  
Derniers sujets
» API Windows
par Klaus Aujourd'hui à 3:21

» KGF.dll - demandes ou suggestions de modifications ou ajouts
par pascal10000 Hier à 17:49

» Cartes de voeux, menus, etc.
par JL35 Hier à 17:48

» Mah-Jong européen new-look
par jjn4 Hier à 15:48

» a l'aide klaus
par Minibug Hier à 11:42

» KGF_dll - nouvelles versions
par Minibug Hier à 1:48

» bug SYNEDIT_TARGET_IS_OBJECT
par Jack Hier à 0:16

» Jukebox : Serge Reggiani
par papydall Sam 9 Déc 2017 - 5:58

» Ecouter la radio fm sur votre pc
par pascal10000 Sam 9 Déc 2017 - 3:42

» anomalie
par Klaus Sam 9 Déc 2017 - 3:21

» hommage
par Jicehel Ven 8 Déc 2017 - 11:29

» Logiciel de soutien scolaire en langues.
par Pedro Alvarez Ven 8 Déc 2017 - 10:43

» carte son
par Klaus Ven 8 Déc 2017 - 2:37

» mise a jour calculatrice
par joeeee2017 Mer 6 Déc 2017 - 22:19

» j'ai un petit problème
par JL35 Mer 6 Déc 2017 - 21:58

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Décembre 2017
LunMarMerJeuVenSamDim
    123
45678910
11121314151617
18192021222324
25262728293031
CalendrierCalendrier

Partagez | 
 

 Arbre binaire de recherche (AVL)

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Arbre binaire de recherche (AVL)   Mar 22 Nov 2011 - 19: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.



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:


"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)



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"



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" :



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 :



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...

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...

Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Invité
Invité



MessageSujet: Re: Arbre binaire de recherche (AVL)   Mar 22 Nov 2011 - 19:41

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.
@+
Revenir en haut Aller en bas
Jicehel

avatar

Nombre de messages : 5863
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Arbre binaire de recherche (AVL)   Mar 22 Nov 2011 - 19:53

Superbe tuto, bon courage Nardo, je test ce soir si je peux Smile
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Ven 2 Déc 2011 - 20:28

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)
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Jicehel

avatar

Nombre de messages : 5863
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Arbre binaire de recherche (AVL)   Ven 2 Déc 2011 - 23:25

Gros boulot Nardo Smile
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Sam 3 Déc 2011 - 18:27

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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Dim 4 Déc 2011 - 17:31

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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
JL35



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

MessageSujet: Re: Arbre binaire de recherche (AVL)   Dim 4 Déc 2011 - 17:52

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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Lun 5 Déc 2011 - 6:42

Ç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

Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Mar 6 Déc 2011 - 21:15

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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Jicehel

avatar

Nombre de messages : 5863
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Arbre binaire de recherche (AVL)   Mar 6 Déc 2011 - 21:37

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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Mer 7 Déc 2011 - 17:22

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...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Arbre binaire de recherche (AVL)   Sam 10 Déc 2011 - 2:54

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...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Contenu sponsorisé




MessageSujet: Re: Arbre binaire de recherche (AVL)   

Revenir en haut Aller en bas
 
Arbre binaire de recherche (AVL)
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Arbre binaire de recherche (AVL)
» [tuto]Arbre binaire
» [Résolu] une anime sous forme d'un arbre de recherche
» recherche d'une police de caractère
» [Résolu] Recherche d'un BON aspirateur de sites + formulaire informat

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC :: PANORAMIC :: Vos projets-
Sauter vers: