java - grafico - arbol rojo y negro c++

Explicación de la implementación de TreeMap basada en el árbol Rojo-Negro en JAVA

Question

Estaba revisando el código fuente de TreeMap en JAVA . Según el documento de Java:

Una implementación NavigableMap basada en un árbol rojo-negro. El mapa se clasifica según el orden natural de sus claves, o por un Comparador proporcionado en el momento de la creación del mapa, según el constructor que se utilice.

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones de almacenamiento de clave, obtención, colocación y eliminación. Los algoritmos son adaptaciones de los de Cormen, Leiserson y la Introducción a los algoritmos de Rivest.

En el código fuente encontré que una entrada de clase interna se usaba como un nodo .

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 cuanto a la definición de árbol rojo-negro . De Wikipedia encontré:

Un árbol rojo-negro es un tipo de árbol de búsqueda binaria de equilibrio automático, una estructura de datos utilizada en informática.

El auto-equilibrio se proporciona pintando cada nodo con uno de dos colores (estos se llaman típicamente ''rojo'' y ''negro'', de ahí el nombre de los árboles) de tal manera que el árbol pintado resultante satisface ciertas propiedades que no tienen '' No permita que se desequilibre significativamente. Cuando se modifica el árbol, el nuevo árbol se reorganiza y se vuelve a pintar para restaurar las propiedades de coloración. Las propiedades están diseñadas de tal manera que esta reorganización y cambio de color se puede realizar de manera eficiente.

Intenté analizar el código de fuente pero no pude entender lo siguiente:

1. Supongamos que ya tengo dos teclas "C" y "E" en el árbol y luego agrego "D". Cómo se ordenarán los nodos (utilizando ordenación natural).

2. Cómo se implementa el auto-equilibrio de Árbol en el código fuente de Java.

Intenté buscar la implementación detallada de TreeMap pero no pude encontrar ningún artículo como el siguiente que encontré para HashMap

Desde ayer estoy colgando de este árbol :( ¿Puede alguien ayudarme a bajar ...

Answer 1

1. El objetivo del TreeMap es tener un árbol de claves donde las claves que están más bajas que las claves principales están a la izquierda y las claves más altas que las claves principales están a la derecha. Entonces, si agregas C , luego E , tendrás este árbol:

   C
    /
     E

   Si luego agrega D , inicialmente tendrá:

   C
    /
     E
    /
   D

   Pero este árbol está desequilibrado y, por lo tanto, las búsquedas serían más lentas. Así, el árbol se reequilibra. Después de equilibrarse, el árbol ahora se vuelve mucho más eficiente:

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

2. El reequilibrio tiene lugar dentro del método fixAfterInsertion() , que verifica si las propiedades rojo-negro del árbol aún se mantienen después de la inserción. Y, si no lo hace, entonces reequilibra el árbol ejecutando rotateLeft() o rotateRight() en la rama ofensiva para restaurar el equilibrio. Luego se mueve hacia arriba en el árbol y verifica el balance, y así sucesivamente hasta que llega al nodo raíz.

Hay varios recursos en Internet que explican en profundidad los árboles rojo-negros. Pero, creo que la mejor manera de entender el proceso es seguir un tutorial animado como este: http://www.csanimated.com/animation.php?t=Red-black_tree

No hay nada peculiar en la implementación TreeMap de RBT. Sigue de cerca el pseudocódigo que se encuentra en el libro de CLRS (Cormen, Leiserson, Rivest y Stein), que es lo que hace el 99% de las implementaciones.