ARBRE BICOLORE, ARBRE AVL, SKIPLIST
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
halimazouaou Messages postés 2 Date d'inscription samedi 4 juin 2016 Statut Membre Dernière intervention 4 juin 2016 - 4 juin 2016 à 20:37
halimazouaou Messages postés 2 Date d'inscription samedi 4 juin 2016 Statut Membre Dernière intervention 4 juin 2016 - 4 juin 2016 à 20:37
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/36106-arbre-bicolore-arbre-avl-skiplist
https://codes-sources.commentcamarche.net/source/36106-arbre-bicolore-arbre-avl-skiplist
4 juin 2016 à 20:37
13 janv. 2013 à 19:12
once again, thnks thks tucobosh :)
28 déc. 2008 à 13:12
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
9 avril 2008 à 22:29
extrait: private TreeNode root; //racineTreeNode root
il me semble que cette classe est définie nulle part.
26 mars 2008 à 17:18
[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).
26 mars 2008 à 16:53
[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).
26 mars 2008 à 16:46
while (noeud != null) {...}
est suffisant.
26 mars 2008 à 16:43
[code]
while (noeud != null && noeud.deseq != 0) {...}
[code]
26 mars 2008 à 16:39
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!