J'ai été mise en œuvre d'un LLRB paquet qui doit être en mesure de fonctionner dans les deux modes, Bas-2-3 ou de Haut en Bas 2-3-4 décrit par Sedgewick (code - amélioration du code, bien que ne traitant qu'avec 2-3 arbres ici, grâce à RS pour un pointeur).
Sedgewick fournit une description très claire de l'arbre des opérations pour les 2-3 mode, même si il passe beaucoup de temps à parler de l'2-3-4 mode. Il montre aussi comment une simple modification de l'ordre de la couleur de retournement lors de l'insertion peut modifier le comportement de l'arbre (split sur le chemin vers le bas pour 2-3-4 ou split sur le chemin pour 2-3):
private Node insert(Node h, Key key, Value value)
{
if (h == null)
return new Node(key, value);
// Include this for 2-3-4 trees
if (isRed(h.left) && isRed(h.right)) colorFlip(h);
int cmp = key.compareTo(h.key);
if (cmp == 0) h.val = value;
else if (cmp < 0) h.left = insert(h.left, key, value);
else h.right = insert(h.right, key, value);
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
// Include this for 2-3 trees
if (isRed(h.left) && isRed(h.right)) colorFlip(h);
return h;
}
Cependant, il glisse sur la suppression dans 2-3-4 LLRBs avec les éléments suivants:
Le code sur la page suivante est la mise en œuvre complète de supprimer() pour LLRB 2-3 arbres. Il est basé sur l'inverse de l'approche utilisée pour les insérer dans le haut-vers le bas 2, 3 et 4 arbres: nous avons effectuer des rotations et de la couleur de la retourne sur le chemin vers le bas le chemin de recherche pour assurer que la recherche ne s'arrête pas sur un 2-noeud, de sorte que nous pouvons simplement de supprimer le nœud dans le bas. Nous utilisons la méthode de correction() pour partager le code pour la couleur flip et les rotations suivant les appels récursifs dans l'insert() code. Avec fixUp(), nous pouvons laisser de droite liens rouges et asymétrique à 4 nœuds le long du chemin de recherche, sûr que ces conditions seront fixées sur le chemin jusqu'à l'arbre. (L'approche est également efficace 2-3-4 arbres, mais nécessite une rotation lorsque le droit nœud hors du chemin de recherche est un 4-nœud.)
Son delete() fonction:
private Node delete(Node h, Key key)
{
if (key.compareTo(h.key) < 0)
{
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, key);
}
else
{
if (isRed(h.left))
h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
if (key.compareTo(h.key) == 0)
{
h.val = get(h.right, min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right, key);
}
return fixUp(h);
}
Mon de mise en œuvre de l'entretient correctement LLRB 2-3 invariants pour tous les arbres des opérations sur 2-3 arbres, mais échoue pour une sous-classe de la côté droit les suppressions sur les arbres 2-3-4 (à défaut de ces suppressions résultat de droit en s'appuyant noeuds rouges, mais la boule de neige à l'arbre de déséquilibre et enfin un déréférencement de pointeur null). À partir d'une enquête de l'exemple de code qui traite de LLRB arbres et inclut des options pour la construction d'arbres en soit le mode, il semble qu'aucun correctement met en œuvre la suppression d'un 2-3-4 LLRB (c'est à dire qu'aucun n'a le supplément de rotation fait allusion, par exemple, Sedgewick java ci-dessus et ici).
J'ai du mal à comprendre exactement ce qu'il entend par "extra rotation lorsque le droit nœud hors du chemin de recherche est un 4-nœud"; on suppose que c'est une rotation à gauche, mais où et quand?
Si je tourne à gauche en passant vers le haut passé un 4-nœud équivalent (c'est à dire RR nœud) ou d'un droit en s'appuyant 3-nœud équivalent (BR nœud), soit avant l'appel de correction() ou à la fin de la correction de la fonction, je reçois toujours le même invariant de la contradiction.
Voici l'arbre des états de la plus petite à défaut d'exemples que j'ai trouvé (séquentiel généré par l'insertion d'éléments de 0 à la valeur maximale).
La première paire d'arbres montre la transition de l'invariant conforme de l'état avant la suppression de l'élément de 15 à cassé évidemment de l'état après.
La seconde est essentiellement le même que ci-dessus, mais avec la suppression de 16 de 0..16 (suppression de l'15 résultats dans la même topologie). Notez que l'invariant contradiction parvient à traverser le nœud racine.
La clé va être de comprendre comment revenir sur les violations générées lors de la marche en bas de l'arbre pour le nœud cible. Les deux arbres de montrer comment le premier arbre au-dessus de l'air après une promenade vers le bas, la gauche et la droite respectivement (sans suppression et avant de marcher jusqu'à fixUp()).
Après la tentative de suppression '-1', sans correction:
Après la tentative de suppression '16', sans correction:
Essayer tourner à gauche sur le chemin de retour vers le haut quand le nœud n'a qu'un rouge à droite de l'enfant semble être une partie de la solution, mais elle ne traite pas correctement avec les deux red droit des enfants dans une rangée, précédant le présent avec un flipColor lorsque les deux enfants sont rouge semble améliorer la situation, mais laisse encore certains invariants violé.
Si j'ai plus de vérifier si le droit de l'enfant d'un droit de l'enfant est rouge quand son frère est noir et tourner à gauche si c'est vrai que je n'échouera une fois, mais à ce point je me sens comme je suis besoin d'une nouvelle théorie plutôt qu'une nouvelle epicycle.
Des idées?
Pour référence, mon application est disponible ici (Non, ce n'est pas Java).
Suivi:
Partie de la raison qui m'a intéressé dans ce a été de confirmer la demande par beaucoup que 2-3 LLRB arbres sont plus efficaces que les 2-3-4 LLRB arbres. Mon analyse comparative a confirmé l'existence de ce pour l'insertion et la suppression (2-3 sont environ 9% plus rapide), mais je trouve que la récupération est très légèrement plus rapide pour les arbres 2-3-4.
Les temps suivants sont représentatifs et cohérent à travers les pistes:
BU23:
BenchmarkInsert 1000000 1546 ns/op
BenchmarkDelete 1000000 1974 ns/op
BenchmarkGet 5000000 770 ns/op
TD234:
BenchmarkInsert 1000000 1689 ns/op
BenchmarkDelete 1000000 2133 ns/op
BenchmarkGet 5000000 753 ns/op
La première colonne est banc nom, le second est le nombre d'opérations, le troisième est le résultat. De référence sur i5M 2.27.
J'ai eu un coup d'oeil à la branche longueurs pour les 2-3 arbre et les arbres 2-3-4 et il y a peu que pour expliquer la récupération de la différence (distance moyenne de la racine au nœud et S. D. de 1000 arbres avec 10000 insertions aléatoires):
Means:
TD234 leafs BU23 leafs
12.88940 12.84681
TD234 all BU23 all
11.79274 11.79163
StdDev:
TD234 leafs BU23 leafs
1.222458 1.257344
TD234 all BU23 all
1.874335 1.885204
