Arbre bicolore, arbre avl, skiplist

Soyez le premier à donner votre avis sur cette source.

Vue 14 844 fois - Téléchargée 2 129 fois

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

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
2
Date d'inscription
samedi 4 juin 2016
Statut
Membre
Dernière intervention
4 juin 2016

bravo
Messages postés
1
Date d'inscription
lundi 3 septembre 2007
Statut
Membre
Dernière intervention
13 janvier 2013

A very Coooooooooooool Tooooooooooool... it was very useful to understand my course :),

once again, thnks thks tucobosh :)
Messages postés
3
Date d'inscription
mardi 25 novembre 2008
Statut
Membre
Dernière intervention
29 décembre 2008

Dans la suppression dans l'AVL, quand j'ai déroulé la partie supprimer (la fonction delete) du code AVLTree je voudrais savoir si le "return false" qu'il y'a a chaque fois a la sortie de la fonction delete(AVLNode PP,AVLNode P,int val) et delMin(AVLNode PP,AVLNode P) est correcte?
Ce return signifie que le parent ne doit pas mettre à jour son déséquilibre (on sors de l'appel récursif), le desquilibre ne se modéfie pas qu'au niveau du noued supprimé paske il est probable qu'il y'ai un desequilibre au niveau du noeud pére...etc alors je sais pas peut étre que sa devrais retourné un true pour que le test du if (delete(P,P.getLeft(),val)) ainsi que if (delete(P,P.getRight(),val)) return un true et nous permet de terminer la suite tel que la modéfication du désequi

P.setDeseq(P.getDeseq()-1); //suppression a gauche
return (reequilibre(PP,P)==0) //rééquilibrage si necessaire
et a la fin la fonction retourne un true

Autre chose que signifie "==0"
Merci
Messages postés
1
Date d'inscription
dimanche 27 août 2006
Statut
Membre
Dernière intervention
9 avril 2008

la classe Tree fait référence à la class TreeNode

extrait: private TreeNode root; //racineTreeNode root

il me semble que cette classe est définie nulle part.
Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

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).
Afficher les 9 commentaires

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.