1. Accueil
  2. Java
  3. Sources Java
  4. Sources Maths et Algorithmes
  5. Arbre bicolore, arbre avl, skiplist

Arbre bicolore, arbre avl, skiplist

5/5 (9 avis)

Vue 15 386 fois - Téléchargée 2 154 fois

Télécharger le projet
Commenter

Description

regroupe 3 petits projets d'algorithmiques classiques : les arbres équilibrés AVL, arbre Bicolore et les SkipList. Chaque projet contient une belle interface graphique.

Les AVL et Bicolore : l'interface affiche graphiquement l'arbre. On peut ajouter ou supprimmer des noeuds, l'équilibrage de l'arbre se fait automatiquement. Il est a noté que pour les Bicolores, seule l'insertion est possible. Vous pouvez essayer d'implanter la suppression. L'interface est assez belle et intuitive, elle permet de comprendre aisement le fonctionnement des arbres équilibrés.

Les SkipList : les skiplist sont des listes dont le cout de recherche est en moyenne, linéaire. La recherche est donc optimisée. Le programme Java permet de comparer graphiquement les differences de cout de recherche d'un élement dans une skiplist et dans une linkedlist (liste chainée classique) en fonction de la taille de la liste.

Pour éxecuter/compiler les projets :
chaque projet possede un script Windows compiler.bat et run.bat qui permet de compiler/executer le projet. Sous UNIX, ouvrez ces scripts et regardez les instructions effectuées.

NOTE: dans le zip, seuls les sources JAVA sont présents. Vous devez les compiler. Les sources ont été testés sous JAVA 1.5 sans problème

Conclusion :


Bugs connus :
-bug parfois dans l'insertion d'un noeud dans l'arbre bicolore.
Seul bug connu pour le moment... :D
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire Commentaires
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019
26 mars 2008 à 16:39
Dans AVLNode, la fonction getMaxHeight() n'est pas optimale:
si on connait la valeur du déséquilibre, son seul signe sert à savoir de quel côté est la branche la plus longue. Si le déséquilibre est nul, n'importe quelle brnache peut être choisie.
Bref, pas besoin de résursion, une simple boucle suffit jusqu'à tomber sur une feuille, en suivant simplement à chaque boucle la branche la plus longue déterminée par le déséquilibre!

De plus si le déséquilibre est non nul, on sait qu'on a au moins un noeud fils du côté indiqué par le signe du déséquilibre, il n'est donc pas nécessaire de tester si on est sur une feuille (puisque une feuille a un déséquilibre nul par définition).

Il sufit d'adopter la convention suivante: le déséquilibre sera négatif si l'arbre penche à gauche (sous-arbre plus long à gauche qu'à droite), positif si l'arbre penche à droite (sous-arbre plus long à droite qu'à gauche), nul si l'arbre est équilibré.
Bref, sans aucune récursion (puisqu'on élimine une des deux récursions possibles, il n'en reste qu'une qu'on optimise par une boucle terminale), il suffit de remplacer le code suivant: 
    /** renvoi la hauteur max des 2 branches (recursif!) */
    public  int getMaxHeight()
    {
        if  (isLeaf())  //c'est une feuille, on s'arrete
            return  1;
        
        int hd=0,hg=0;
        if  (gauche!=null)  hg=1+gauche.getMaxHeight();
        if  (droite!=null)  hd=1+droite.getMaxHeight();
        
        if  (hd>hg) return  hd;
        return  hg;
        
    }
[code]
par:
[code
    /** renvoie la hauteur max des 2 branches (recursif!) */
    public  int getMaxHeight()
    {
       int hauteur = 1;
       AVLNode noeud = this;
       while (noeud.deseq != 0) {
           hauteur++;
           if (node.deseq < 0)
               noeud = noeud.gauche;
           else
               noeud = noeud.droite;
      }
      return hauteur;
    }

Evidemment, il faut l'invariant suivant dans toutes les instances de AVLNode:

si gauche est nul, alors :
si droite est nul, alors :
deseq = 0; // feuille
sinon :
deseq > 0; // arbre penché à droite
fin si;
sinon si droite est nul, alors :
deseq < 0; // arbre penché à gauche
sinon
deseq est de signe quelconque: des deux arbres gauche et droite non nuls,
le plus long est indiqué par le signe de deseq;
fin si.

On doit donc créer toutes les feuilles avec deseq=0 dans le constructeur, et mettre à jour le déséquilbre en cas d'insertion à droite ou à gauche, ou suppression d'un noeud dans une branche. Cette fonction accélérée servira facilement à recalculer rapidement et effiacacement ces hauteurs maximales pour savoir laquelle des branches est la plus longue quand il reste deux sous-arbres. Cela ne demandera aucune récursion et ce sera beacuoup plus rapide!
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019
26 mars 2008 à 16:43
oups j'oublie une partie de la condition du while ci-dessus:
[code]
while (noeud != null && noeud.deseq != 0) {...}
[code]
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019
26 mars 2008 à 16:46
en fait le test de nullité est même inutile et indésirable pour parcourir la plus longue branche toute entière:

while (noeud != null) {...}

est suffisant.
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019
26 mars 2008 à 16:53
Ca donne:
[code]
public int getMaxHeight()
{
int hauteur = 0;
AVLNode noeud = this;
while (noeud != null) {
hauteur++;
if (noeud.deseq > 0)
noeud = noeud.droite;
else
noeud = noeud.gauche;
}
return hauteur;
}
[code]
Il n'y a aucune importance sur laquelle des branches est suivie, il suffit juste que ce soit une parmi les branches de longueur maximale. Le long de cette branche, des noeuds peuvent avoir un déséquilibre nul, mais on suit toujours la branche déséquilibrée quand il y en a une, ou sinon une branche arbitraire (ici celle de gauche).
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019
26 mars 2008 à 17:18
Enfin dans le cas où la branche droite est suivie, inutile de tester si le noeud pointé est nul, on sait qu'il ne l'est pas, ce qui réduit le nombre de tests moyen par boucle:

[code]
public int getMaxHeight()
{
int hauteur = 0;
AVLNode noeud = this;
do {
while (noeud.deseq < 0) {
noeud = noeud.gauche;
hauteur++;
}
// Après avoir suivi la branche gauche déséquilibrée on est soit
// sur une feuille (plus rien non plus à droite), ou sur un noeud
// équilibré avec deux branches à droite et à gauche, ou avec
// seulement une branche à gauche.
hauteur++;
// boucler arbitrairement par la branche droite (deseq >= 0) si elle
// existe (le test ici détecte si on était sur une feuille où on a
// nécessairement deseq == 0)
} while ((noeud = noeud.droite) != null);
return hauteur;
}
[code]
Cette version évite aussi de tester la nullité du premier noeud (on sait que "this" n'est pas null).
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (tucobouch)