Explication de la Rouge-Noir arbre en fonction de la mise en œuvre de TreeMap en JAVA

J'ai été en passant par le code source de TreeMap dans JAVA.
Conformément à la JAVA doc:

Rouge-Noir à base de bois NavigableMap mise en œuvre. La carte est triée selon l'ordre naturel de ses clés, ou par un Comparateur fournies au moment de la création de la carte, en fonction du constructeur est utilisé.

Cette application donne des garanties log(n) coût du temps pour la containsKey, get, put et les opérations de suppression. Les algorithmes sont des adaptations de ceux de Cormen, Leiserson et Rivest Introduction aux Algorithmes.

Dans le code source, j'ai trouvé que l'Intérieur de la Classe Entrée a été utilisé comme un nœud.

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;
        ....

Comme pour le defination de Rouge-Noir arbre. À partir de Wikipedia, j'ai trouvé:

Rouge–noir arbre est un type d'auto-équilibrage arbre de recherche binaire, une structure de données utilisé en informatique.

L'auto-équilibrage de la charge est fournie par la peinture à chaque nœud avec l'une des deux couleurs (ces dernières sont généralement appelés "rouge" et "noir", d'où le nom de l'arbre) de telle façon que le résultat est peint arbre satisfait certaines propriétés qui ne permet pas à devenir assez déséquilibré. Lorsque l'arbre est modifiée, la nouvelle arborescence est par la suite transformé et repeint pour restaurer la coloration des propriétés. Les propriétés sont conçus de telle manière que cette réorganisation et recoloring peut être effectuée de manière efficace.

J'ai essayé d'analyser le code source mais je ne pouvais pas comprendre ce qui suit:

  1. Suppose que je suis déjà les deux touches "C" et "E" dans l'Arbre, et ensuite je suis ajoutant des "D". Comment les nœuds seront organisées (à l'Aide d'naturel de la commande).

  2. Comment est-à auto-équilibrage de l'Arbre est mis en œuvre dans le code source java.

J'ai essayé de chercher pour le détail de la mise en oeuvre TreeMap, mais a été incapable de trouver un article comme le la suite de l'article j'ai trouvé pour le HashMap

Depuis hier, je suis accroché sur cet Arbre 🙁 quelqu'un Peut-il svp m'aider à descendre...

  • Avez-vous vu la JSE sources? Tout est clair là-bas.
InformationsquelleAutor Zeeshan | 2014-01-24
  1. 45

    1. L'objectif de la TreeMap est d'avoir un arbre de clés où les touches, qui sont inférieurs à ceux de la société mère clés sont à gauche et les touches plus élevé que le parent est la clé vers la droite. Donc, si vous ajoutez C, puis E, vous aurez cet arbre:

      C
 \
  E

      Si vous ajoutez ensuite D, d'abord, vous aurez:

      C
 \
  E
 /
D

      Mais cet arbre est déséquilibrée et, par conséquent, les recherches seraient plus lent. Ainsi, l'arbre est rééquilibré. Après l'équilibrage, l'arbre devient maintenant beaucoup plus efficace:

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

    2. Rééquilibrage prend place à l'intérieur de la fixAfterInsertion() méthode, qui vérifie si les rouge-noir propriétés de l'arbre sont encore maintenues après l'insertion. Et, si elle ne le fait pas, elle rééquilibre l'arbre effectue rotateLeft() ou rotateRight() sur la délinquance de la direction générale afin de rétablir l'équilibre. Puis il se déplace vers le haut de l'arbre et en vérifie l'équilibre et ainsi de suite jusqu'à ce qu'il atteigne le nœud racine.

    Il existe plusieurs ressources autour de l'internet qui expliquent les Arbres Rouge-Noir dans la profondeur. Mais, je pense que la meilleure façon de comprendre le processus est à la suite d'un tutoriel animé comme ceci: http://www.csanimated.com/animation.php?t=Red-black_tree

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

    • J'ai essayé de trouver comment est l'itération d'un TreeMap fait en interne, mais havnt été en mesure de le trouver en ligne. Pouvez-vous s'il vous plaît aidez-moi à comprendre ce que la traversée de l'algorithme est utilisée pour parcourir le Rouge noir de l'arbre présent en interne.
    • La traversée est assez simple: prendre à la racine d'un noeud comme noeud courant, si la valeur que vous recherchez est le noeud courant, le retourner, sinon, si la valeur est inférieure à celle du nœud actuel, à rendre la gauche de l'élément du nœud actuel et le répète, si la valeur est plus élevée que le noeud courant, faire le bon élément du nœud actuel et répétez.
    InformationsquelleAutor EmirCalabuch