ArbreAVL: B-Insertion (Classique)

Télécharger le projet
Commenter

Description

Bonjour,

Les implémentations téléchargées et complétées avec des interfaces jusqu'ici se ressemblent assez et sont en fait très "classiques" (voir Liens: CodeS-SourceS).

J'ai écrit (presque "pompé" sur GeeksforGeeks) une version personnelle à ma manière, c'est-à-dire un peu plus condensée.
Elle se trouve dans le fichier Node.cpp, importé par Classique.cpp: 
// ArbreAVL: A-Insertion (Personnelle Classique)

int Hgt(Node *nod) {return (nod) ? nod->hgt : 0;}

Node *RotBig(Node *y) {
    struct Node *x = y->sml;
    struct Node *xb = x->big;
    x->big = y;
    y->sml = xb;
    y->hgt = MAX(Hgt(y->sml), Hgt(y->big)) + 1;
    x->hgt = MAX(Hgt(x->sml), Hgt(x->big)) + 1;
    return x;
}

struct Node *RotSml(struct Node *x) {
    struct Node *y = x->big;
    struct Node *ys = y->sml;
    y->sml = x;
    x->big = ys;
    x->hgt = MAX(Hgt(x->sml), Hgt(x->big)) + 1;
    y->hgt = MAX(Hgt(y->sml), Hgt(y->big)) + 1;
    return y;
}

int Balance(Node *nod) {
  return (nod) ? Hgt(nod->sml) - Hgt(nod->big) : 0;
}

Node *Insert(Node *nod, int k) { // insert new Node(k) in subtree nod
  if (nod) {
    if (k < nod->key) nod->sml = Insert(nod->sml, k);
    else if (k > nod->key) nod->big = Insert(nod->big, k);
    else return nod; // double
  } else return new Node(k);
  nod->hgt = 1 + MAX(Hgt(nod->sml), Hgt(nod->big));
  int bal = Balance(nod);
  if (bal > 1 && k < nod->sml->key) return RotBig(nod);
  if (bal < -1 && k > nod->big->key) return RotSml(nod);
  if (bal > 1 && k > nod->sml->key)
    {nod->sml = RotSml(nod->sml); return RotBig(nod);}
  if (bal < -1 && k < nod->big->key)
    {nod->big = RotBig(nod->big); return RotSml(nod);}
  return nod; // returns the new root
}

L'interface ajoutée permet de se persuader que ces routines ont l'air de bien fonctionner.
Bien entendu qu'après chaque insertion, l'arbre AVL courant est testé à l'aide de la fonction int Height() du fichier Node.h.

Mais ne copiez pas encore le code ci-dessus, car dans un prochain article, nous allons y apporter quelques "améliorations".
Essayez d'en trouver déjà maintenant !
 
 
Bonne lecture ...
 

Liens

WikipédiA: Arbre AVL
WikipediA: AVL tree
CodeS-SourceS: ArbreAVL: A-Insertion (GeeksforGeeks)
CodeS-SourceS: ArbreAVL: A-Insertion (GitHub)
CodeS-SourceS: ArbreAVL: A-Insertion (TheCrazyProgrammer)
 
Télécharger le projet

Codes Sources

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 (William VOIROL)