Explication de L'implémentation de TreeMap en JAVA basée sur l'arbre rouge et noir

j'ai parcouru le code source de TreeMap JAVA. Conformément à la JAVA doc:

une implémentation NavigableMap basée sur un arbre rouge-noir. La carte est triée selon l'ordre naturel de ses clés, ou par un comparateur fourni au moment de la création de la carte, en fonction du constructeur utilisé.

cette implémentation fournit un log (n) Temps garanti pour les opérations containsKey, get, put et remove. Les algorithmes sont des adaptations de ceux de Cormen, Leiserson et Rivest Introduction aux Algorithmes.

dans le code source j'ai trouvé qu'une classe intérieure Entrée a été utilisé comme un noeud.

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
        ....

en ce qui concerne la défination de Rouge-Noir tree. De Wikipedia j'ai trouvé:

un arbre rouge-noir est un type d'arbre de recherche binaire auto-équilibré, une structure de données utilisée en informatique.

Le l'auto-équilibrage est fourni en peignant chaque noeud avec une des deux couleurs (celles-ci sont typiquement appelées "rouge" et "noir", d'où le nom des arbres) de telle sorte que l'arbre peint résultant satisfait certaines propriétés qui ne permettent pas de devenir significativement déséquilibré. Lorsque l'arbre est modifié, le nouvel arbre est ensuite réarrangé et repeint pour restaurer les propriétés de coloration. Les propriétés sont conçues de manière à ce que ce réarrangement et recoloration puissent être effectués efficacement.

j'ai essayé d'analyser le code source mais je n'ai pas pu comprendre ce qui suit:

  1. supposons que j'ai déjà deux touches "C" et "E"dans l'arbre et que j'ajoute "D". Comment les noeuds seront disposés (en utilisant l'ordre naturel).

  2. comment l'auto-équilibrage de Tree est implémenté dans le code source java.

j'ai essayé de chercher les détails de la mise en œuvre de TreeMap mais j'ai été incapable pour trouver n'importe quel article comme le article suivant j'ai trouvé pour HashMap

depuis hier je suis accroché à cet arbre : (quelqu'un peut s'il vous plaît m'aider à descendre...

20
demandé sur Zeeshan 2014-01-24 14:01:28

1 réponses

  1. le but du TreeMap est d'avoir un arbre de clés où les clés qui sont plus basses que la clé du parent sont à gauche et les clés plus hautes que la clé du parent sont à droite. Donc, si vous ajoutez C, puis E, vous aurez cette arborescence:

    C
 \
  E

    Si vous ajoutez ensuite D, initialement vous aurez:

    C
 \
  E
 /
D

    mais cet arbre est déséquilibré et donc les recherches seraient plus lentes. Ainsi, l'arbre est rééquilibré. Après l'équilibrage, l'arbre maintenant devient beaucoup plus efficace:

    C                     C
 \        rotate       \         rotate         D
  E   --- right --->    D    ---  left --->    / \
 /        around         \       around       C   E
D           E             E        D

  2. le rééquilibrage a lieu à l'intérieur du fixAfterInsertion() méthode qui vérifie si le rouge-noir propriétés de l'arbre sont encore maintenues après l'insertion. Et, s'il ne le fait pas, alors il rééquilibre l'arbre exécutant soit rotateLeft() ou rotateRight() sur la branche incriminée pour rétablir l'équilibre. Puis il remonte l'arbre et vérifie l'équilibre et ainsi de suite jusqu'à ce qu'il atteigne la racine nœud.

il existe plusieurs ressources sur internet qui expliquent en profondeur les arbres rouges et noirs. Mais, je pense que la meilleure façon de comprendre le processus est de suivre un tutoriel animé comme celui-ci:http://www.csanimated.com/animation.php?t=Red-black_tree

Il n'y a rien de particulier dans l' TreeMap mise en oeuvre de la RBT. Il suit de près le pseudo-code donné dans le livre de CLRS (Cormen, Leiserson, Rivest et Stein), qui est ce que 99% des implémentations autour de le faire.

33
répondu EmirCalabuch 2016-02-08 18:07:23