RBTree: B-Insertion (Optimisation)
Description
Bonjour,
En introduisant les résultats de mon propre code "RBTree: B-Insertion (Personnelle)" dans "C-Insertion-Performance", j'ai remarqué qu'il améliorait les temps d'exécution de quelques %.
Un autre avantage est qu'il n'utilise pas le pointeur parent dans chaque nœud (comme Sedgewick).
Par contre, l'arbre résultant n'est pas très régulier, c'est-à-dire que sa hauteur (Height) et sa hauteur en nœuds noirs (HeightBlack) sont grandes par rapport aux logiciels classiques.
Alors, je me suis remis à "l'ouvrage", en considérant cette fois la notion d'oncle.
En effet, en "ratissant" plus large dès le début, on risque de retrouver un résultat plus régulier à la fin.
Je m'approche donc de la l'algorithme classique, mais sans utiliser les rotations:
Faites un essai avec l'interface en compilant Optimisation.cpp.
La "représentation graphique" sur la console montre que l'arbre résultant semble plus régulier.
Avec des tests "sérieux", je vais prochainement mettre à jour l'article évolutif RBTree: C-Insertion-Performance.
Bonne lecture …
CodeS-SourceS: RBTree: A-Insertion (GitHub)
CodeS-SourceS: RBTree: A-Insertion (Sedgewick)
CodeS-SourceS: RBTree: B-Insertion (Personnelle)
CodeS-SourceS: RBTree: C-Insertion-Performance
En introduisant les résultats de mon propre code "RBTree: B-Insertion (Personnelle)" dans "C-Insertion-Performance", j'ai remarqué qu'il améliorait les temps d'exécution de quelques %.
Un autre avantage est qu'il n'utilise pas le pointeur parent dans chaque nœud (comme Sedgewick).
Par contre, l'arbre résultant n'est pas très régulier, c'est-à-dire que sa hauteur (Height) et sa hauteur en nœuds noirs (HeightBlack) sont grandes par rapport aux logiciels classiques.
Alors, je me suis remis à "l'ouvrage", en considérant cette fois la notion d'oncle.
En effet, en "ratissant" plus large dès le début, on risque de retrouver un résultat plus régulier à la fin.
Je m'approche donc de la l'algorithme classique, mais sans utiliser les rotations:
struct RBNode { // RBNode.h
RBNode *sml, *big; // ┌─> sml: smaller
int key; // Diagramme: ──> nod
bool black; // └─> big: bigger
// ...
};
struct RBTree { // RBTree.h
RBNode *root = 0;
// ...
RBNode *Insert(int key) { // insert new RBNode(key) dans root
int idx = 0;
RBNode *arr[128], *r = root, *p, *g, *u; // p: parent; g: grandparent; u: uncle
if (root) do {
arr[idx++] = r;
if (key < r->key)
{if (r->sml) {r = r->sml; continue;} else break;}
if (key > r->key)
{if (r->big) {r = r->big; continue;} else break;}
return 0; // key == r->key: double, already inserted
} while (1);
RBNode *k = new RBNode(key), *n = k; // n, k: new RBNode(key)
while (idx > 0) {
p = arr[--idx];
if (n->key < p->key) p->sml = n; else p->big = n;
if (p->black||n->black) return k; // parent black or n black
if (idx > 0) g = arr[--idx]; else break; // no grandparent
u = (p == g->sml) ? g->big: g->sml;
if (u != 0 && u->black == false) { // uᴿ
g->black = false; // ┌── nᴿ ┌── nᴿ
p->black = true; // ┌── pᴿ ====> ── pᴮ
u->black = true; // ── gᴮ (4 possibilities) └── gᴿ
n = g; // └── uᴿ └── uᴮ
} else if (p == g->sml) { // uᴮ pᴿ < gᴮ
if (n == p->sml) { // nᴿ < pᴿ
g->black = false; // ┌── nᴿ ┌── nᴿ
g->sml = p->big; // ┌── pᴿ ── pᴮ
p->black = true; // │ └── x ====> │ ┌── x
p->big = g; // ── gᴮ └── gᴿ
n = p; // └── uᴮ └── uᴮ
} else { // pᴿ < nᴿ
g->black = false; // ┌── pᴿ ┌── pᴿ
g->sml = n->big; // │ │ ┌── x │ └── x
p->big = n->sml; // │ └── nᴿ ====> ── nᴮ
n->black = true; // │ └── y │ ┌── y
n->sml = p; // ── gᴮ └── gᴿ
n->big = g; // └── uᴮ └── uᴮ
}
} else { // uᴮ gᴮ < pᴿ
if (n == p->big) { // pᴿ < nᴿ
g->black = false; // ┌── uᴮ ┌── uᴮ
g->big = p->sml; // ── gᴮ ┌── gᴿ
p->black = true; // │ ┌── x ====> │ └── x
p->sml = g; // └── pᴿ ── pᴮ
n = p; // └── nᴿ └── nᴿ
} else { // nᴿ < pᴿ
g->black = false; // ┌── uᴮ ┌── uᴮ
g->big = n->sml; // ── gᴮ ┌── gᴿ
p->sml = n->big; // │ ┌── x │ └── x
n->black = true; // │ ┌── nᴿ ====> ── nᴮ
n->big = p; // │ │ └── y │ ┌── y
n->sml = g; // └── pᴿ └── pᴿ
}
} // RBNode z in a diagramme ► zᴮ: z black; zᴿ: z red; z: z any color
} // while (idx > 0)
root = n; n->black = true; return k;
} // By William VOIROL, Switzerland, CodeS-SourceS: 15 jan 2019.
// ...
};
Faites un essai avec l'interface en compilant Optimisation.cpp.
La "représentation graphique" sur la console montre que l'arbre résultant semble plus régulier.
Avec des tests "sérieux", je vais prochainement mettre à jour l'article évolutif RBTree: C-Insertion-Performance.
Bonne lecture …
Liens
CodeS-SourceS: RBTree: A-Insertion (GeeksforGeeks)CodeS-SourceS: RBTree: A-Insertion (GitHub)
CodeS-SourceS: RBTree: A-Insertion (Sedgewick)
CodeS-SourceS: RBTree: B-Insertion (Personnelle)
CodeS-SourceS: RBTree: C-Insertion-Performance
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.