ArbreAVL: B-Insertion (Personnelle)

Soyez le premier à donner votre avis sur cette source.

Vue 754 fois - Téléchargée 104 fois

Description

Bonjour,

En mettant au point le programme "ArbreAVL: B-Insertion (AmélioréBis)", j'avais fait des "impressions intermédiaires" de quelques variables.
A ma grande surprise, j'ai alors constaté que les hauteurs des nœuds "hgt" évoluaient systématiquement par incrémentation ou décrémentation.

J'ai donc pu remplacer les appels à
int Hgt(Node *n) {
  return MAX((n->sml) ? n->sml->hgt : 0, (n->big) ? n->big->hgt : 0) + 1;
}
par de simples incréments.
(A part le premier:
   n->hgt = Hgt(n);
substitué par
   P->hgt = max(sh, bh) + 1;
).

Ecrivons la fonction int Hgt(Node *n) ci dessus de manière plus conventionnelle et plus facilement traductible en d'autres langages que C ou C++:
int Hgt(Node *n) {
  int sh, bh;
  if (n->sml != 0) sh = n->sml->hgt; else sh = 0;
  if (n->big != 0) bh = n->big->hgt; else bh = 0;
  return max(sh, bh);
}
on constate qu'elle est en fait assez "compliquée", c'est-à-dire relativement "lente".

Ce changement m'a semblé assez important et original pour qualifier ce code d'insertion AVL de "personnel":
Node *Insert(Node *P, int k) { // insert new Node(k) in subtree P
  if (P == 0) return new Node(k);
  if (k < P->key) P->sml = Insert(P->sml, k);
  else if (k > P->key) P->big = Insert(P->big, k);
  else return P; // double

  Node *Q, *R;
  int sh = (P->sml) ? P->sml->hgt : 0, bh = (P->big) ? P->big->hgt : 0;
  P->hgt = max(sh, bh) + 1;

  if (bh + 1 < sh) {
    Q = P->sml;        //     ┌── Q                       ┌── Q
    if (k > Q->key) {  //  (k)│   │                       │   │
      R = Q->big;      //     │   │   ┌── s               │   └── s
      Q->big = R->sml; //     │   └── R        ===>    ── R
      R->sml = Q;      //     │       └── b               │   ┌── b
      Q->hgt -= 1;     //  ── P                           └── P 

    } else R = Q;      //  (k)                         (k)
    P->sml = R->big;   //     ┌── R            ===>    ── R
    R->big = P;        //     │   └──Z                    │   ┌── Z
                       //  ── P                           └── P
  } else if (bh > sh + 1) {
    Q = P->big;        //  ── P                           ┌── P
    if (k < Q->key) {  //     │       ┌── s               │   └── s
      R = Q->sml;      //     │   ┌── R        ===>    ── R
      Q->sml = R->big; //     │   │   └── b               │   ┌── b
      R->big = Q;      //  (k)│   │                       │   │
      Q->hgt -= 1;     //     └── Q                       └── Q

    } else R = Q;      //  ── P                           ┌── P
    P->big = R->sml;   //     │   ┌── Z                   │   └── Z
    R->sml = P;        //     └── R            ===>    ── R
                       //  (k)                         (k)
  } else  return P; // returns the new root

  P->hgt -= 2;
  R->hgt = P->hgt + 1;
  return R;
}

La comparaison sous
   CodeS-SourceS: ArbreAVL: C-Insertion-Performance
montre que cette fois, l'amélioration est plus nette.
 
 
Bonne lecture ...
 

Liens

CodeS-SourceS: ArbreAVL: A-Insertion (GeeksforGeeks)
CodeS-SourceS: ArbreAVL: A-Insertion (GitHub)
CodeS-SourceS: ArbreAVL: A-Insertion TheCrazyProgrammer)
CodeS-SourceS: ArbreAVL: B-Insertion (Classique)
CodeS-SourceS: ArbreAVL: B-Insertion (Amélioré)
CodeS-SourceS: ArbreAVL: B-Insertion (AmélioréBis)
CodeS-SourceS: ArbreAVL: C-Insertion-Performance
CodeS-SourceS: RBTree: C-Insertion-Performance
 

Codes Sources

A voir également

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.