Foros del Web » Programación para mayores de 30 ;) » Java »

Balanceos con Árboles Hash

Estas en el tema de Balanceos con Árboles Hash en el foro de Java en Foros del Web. Hola a todos, empecé a investigar los árboles hash como TreeMap y TreeSet, empecé a implementar el TreeMap casero, tengo el siguiente problema: Las inserciones ...
  #1 (permalink)  
Antiguo 12/06/2018, 20:18
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Balanceos con Árboles Hash

Hola a todos, empecé a investigar los árboles hash como TreeMap y TreeSet, empecé a implementar el TreeMap casero, tengo el siguiente problema:

Las inserciones andan pero cuando quiero pasar de un map a otro se me borra un elemento, esto es lo que me muestra por consola:

run:
* tamaño mapa 1: 5
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 4
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

Este es el código para las inserciones y para mostrar:

Código Java:
Ver original
  1. package treemapsimple;
  2. import java.util.AbstractCollection;
  3. import java.util.AbstractSet;
  4. import java.util.Collection;
  5. import java.util.Comparator;
  6. import java.util.Iterator;
  7. import java.util.Map;
  8. import java.util.Set;
  9. /**
  10.  *
  11.  * @author detectivejd
  12.  * @param <K>
  13.  * @param <V>
  14.  */
  15. public class MyTreeMap<K,V> implements Map<K, V>
  16. {
  17.     private final Comparator<? super K> comparator;
  18.     private final boolean RED   = true;
  19.     private final boolean BLACK = false;
  20.     private Entry<K,V> root;
  21.     private int size;
  22.     public MyTreeMap() {
  23.         clear();
  24.         this.comparator = null;
  25.     }
  26.     public MyTreeMap(Comparator<? super K> xcomparator) {
  27.         clear();
  28.         this.comparator = xcomparator;
  29.     }
  30.     public MyTreeMap(Map<? extends K, ? extends V> m) {
  31.         clear();
  32.         this.comparator = null;
  33.         putAll(m);
  34.     }
  35.     .......
  36.     @Override
  37.     public V put(K key, V value) {
  38.         if(key != null){
  39.             Entry<K,V> t = root;        
  40.             if(t == null){
  41.                 root = new Entry(key, value,null);
  42.                 size = 1;
  43.                 return null;
  44.             }
  45.             int cmp = 0;
  46.             Entry<K,V> parent = null;
  47.             if(comparator != null){
  48.                 while (t != null) {
  49.                     parent = t;
  50.                     cmp = comparator.compare(key,t.key);
  51.                     if(cmp < 0){
  52.                         t = t.left;
  53.                     } else if(cmp > 0) {
  54.                         t = t.right;
  55.                     } else {
  56.                         t.value = value;
  57.                         return value;
  58.                     }
  59.                 }
  60.             } else {
  61.                 while (t != null) {
  62.                     parent = t;
  63.                     Comparable<? super K> k = (Comparable<? super K>) key;
  64.                     cmp = k.compareTo(t.key);
  65.                     if(cmp < 0){
  66.                         t = t.left;
  67.                     } else if(cmp > 0) {
  68.                         t = t.right;
  69.                     } else {
  70.                         t.value = value;
  71.                         return value;
  72.                     }
  73.                 }
  74.             }
  75.             Entry<K,V> e = new Entry(key, value, parent);
  76.             if (cmp < 0)
  77.                 parent.left = e;
  78.             else
  79.                 parent.right = e;
  80.             rbInsertFixup(e);
  81.             size++;
  82.         }
  83.         return null;
  84.     }
  85.     private void rbInsertFixup(Entry<K,V> x) {
  86.         x.color = RED;
  87.         while (x.parent != null && x != root && x.parent.color == RED) {
  88.             if (x.parent == x.parent.parent.left) {
  89.                 // x's parent is a left child.
  90.                 Entry<K,V> y = x.parent.parent.right;
  91.                 if (y != null && y.color == RED) {
  92.                     // Case 1: x's uncle y is red.
  93. //                  System.out.println("rbInsertFixup: Case 1 left");
  94.                     x.parent.color = BLACK;
  95.                     y.color = BLACK;
  96.                     x.parent.parent.color = RED;
  97.                     x = x.parent.parent;
  98.                 } else {
  99.                     if (x == x.parent.right) {
  100.                         // Case 2: x's uncle y is black and x is a right child.
  101.                         // System.out.println("rbInsertFixup: Case 2 left");
  102.                         x = x.parent;
  103.                         leftRotate(x);
  104.                     }
  105.                     // Case 3: x's uncle y is black and x is a left child.
  106.                     //System.out.println("rbInsertFixup: Case 3 left");
  107.                     x.parent.color = BLACK;
  108.                     x.parent.parent.color = RED;
  109.                     rightRotate(x.parent.parent);
  110.                 }
  111.             } else {
  112.                 // x's parent is a right child.  Do the same as when x's
  113.                 // parent is a left child, but exchange "left" and "right."
  114.                 Entry<K,V> y = x.parent.parent.left;
  115.                 if (y != null && y.color == RED) {
  116.                     // Case 1: x's uncle y is red.
  117.                     // System.out.println("rbInsertFixup: Case 1 right");
  118.                     x.parent.color = BLACK;
  119.                     y.color = BLACK;
  120.                     x.parent.parent.color = RED;
  121.                     x = x.parent.parent;
  122.                 } else {
  123.                     if (x == x.parent.left) {
  124.                         // Case 2: x's uncle y is black and x is a left child.
  125.                         // System.out.println("rbInsertFixup: Case 2 right");
  126.                         x = x.parent;
  127.                         rightRotate(x);
  128.                     }
  129.                     // Case 3: x's uncle y is black and x is a right child.
  130.                     // System.out.println("rbInsertFixup: Case 3 right");
  131.                     x.parent.color = BLACK;
  132.                     x.parent.parent.color = RED;
  133.                     leftRotate(x.parent.parent);
  134.                 }
  135.             }
  136.         }
  137.         // The root is always black.
  138.         root.color = BLACK;
  139.     }
  140.     /**
  141.      * Do a right rotation around this node.
  142.     */
  143.     private void rightRotate(Entry<K,V> y) {
  144.         Entry<K,V> x = y.left;
  145.         y.left = x.right;
  146.         if (x.right != null)
  147.             x.right.parent = y;
  148.         x.parent = y.parent;
  149.         if (y.parent == null) {
  150.             root = (Entry)x;
  151.         } else if (y == y.parent.right){
  152.             y.parent.right = x;
  153.         } else {
  154.             x.parent.left = x;
  155.         }
  156.         x.right = y;
  157.         y.parent = x;
  158.     }
  159.     /**
  160.      * Do a left rotation around this node.
  161.     */
  162.     private void leftRotate(Entry<K,V> x) {            
  163.         Entry<K,V> y = x.right;
  164.         x.right = y.left;
  165.         if (y.left != null)
  166.             y.left.parent = x;
  167.         y.parent = x.parent;
  168.         if (x.parent == null) {
  169.             root = (Entry)y;
  170.         } else if (x == x.parent.left) {
  171.             x.parent.left = y;
  172.         } else {
  173.             x.parent.right = y;
  174.         }
  175.         y.left = x;
  176.         x.parent = y;        
  177.     }    
  178.     @Override
  179.     public void putAll(Map<? extends K, ? extends V> m) {
  180.         m.entrySet().forEach((e) -> {
  181.             put(e.getKey(), e.getValue());
  182.         });
  183.     }
  184.     @Override
  185.     public String toString(){
  186.         if (root == null)
  187.             return "";
  188.         else
  189.             return print(root, 0);
  190.     }
  191.     private String print(Entry<K,V> x, int depth) {
  192.         if (x == null)
  193.             return "";
  194.         else
  195.             return print(x.right, depth + 1) +
  196.                 indent(depth) + x.toString() +
  197.                 "\n"+ print(x.left, depth + 1);
  198.            
  199.     }
  200.     private String indent(int s) {
  201.         String result = "";
  202.         for (int i = 0; i < s; i++)
  203.             result += "  ";
  204.         return result;
  205.     }    
  206. }

Y este es el método que estoy probando:

Código Java:
Ver original
  1. Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  2.         Persona.maxIdUp();
  3.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  4.         Persona.maxIdUp();
  5.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  6.         Persona.maxIdUp();
  7.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  8.         Persona.maxIdUp();
  9.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  10.         Persona.maxIdUp();
  11.         Persona p6 = new Persona(Persona.getMaxId(), "Pedro", 16);
  12.         Persona.maxIdUp();
  13.         Persona p7 = new Persona(Persona.getMaxId(), "Deborah", 26);
  14.         Persona.maxIdUp();
  15.         Persona p8 = new Persona(Persona.getMaxId(), "Nelson", 37);
  16.         Persona.maxIdUp();
  17.         Persona p9 = new Persona(Persona.getMaxId(), "Tommy", 22);
  18.         Persona.maxIdUp();
  19.         Persona p10 = new Persona(Persona.getMaxId(), "Manuela", 15);
  20.         Persona.maxIdUp();
  21.         MyTreeMap<Integer,Persona> map = new MyTreeMap();
  22.         map.put(p1.getId(), p1);
  23.         map.put(p2.getId(), p2);
  24.         map.put(p3.getId(), p3);
  25.         map.put(p4.getId(), p4);
  26.         map.put(p5.getId(), p5);
  27.         MyTreeMap<Integer,Persona> map2 = new MyTreeMap(map);
  28.         //map2.put(p6.getId(), p6);
  29.         //map2.put(p7.getId(), p7);
  30.         //map2.put(p8.getId(), p8);
  31.         //map2.put(p9.getId(), p9);
  32.         //map2.put(p10.getId(), p10);
  33.         System.out.println("* tamaño mapa 1: " + map.size());
  34.         System.out.println(map.toString());
  35.         System.out.println("* tamaño mapa 2: " + map2.size());
  36.         System.out.println(map2.toString());
  37.     }

Hace unos días que no le encuentro la vuelta a esto, espero sus respuestas y saludos.

PD: Todavía no lo subí a github.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #2 (permalink)  
Antiguo 13/06/2018, 02:23
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.431
Antigüedad: 9 años, 9 meses
Puntos: 181
Respuesta: Balanceos con Árboles Hash

Yo que tú haría debug aquí

public MyTreeMap(Map<? extends K, ? extends V> m) {
clear();
this.comparator = null;
putAll(m);
}

y también dentro del método putAll

a ver si es ahí donde se hace algo que no debería y se pierde el elemento.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #3 (permalink)  
Antiguo 13/06/2018, 20:47
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Respuesta: Balanceos con Árboles Hash

Hola Fuzzylog, primero que todo gracias por responder y segundo hice lo que me dijiste:

Resulta que el 3er elemento se pierde en sí cuando insertas a p5 en el árbol, en el listado te lo conserva pero se pierde en la estructura del árbol, en estos métodos parece que está el truco:

Código Java:
Ver original
  1. private void rbInsertFixup(Entry<K,V> x) {
  2.         x.color = RED;
  3.         while (x.parent != null && x != root && x.parent.color == RED) {
  4.             if (x.parent == x.parent.parent.left) {
  5.                 // x's parent is a left child.
  6.                 Entry<K,V> y = x.parent.parent.right;
  7.                 if (y != null && y.color == RED) {
  8.                     // Case 1: x's uncle y is red.
  9. //                  System.out.println("rbInsertFixup: Case 1 left");
  10.                     x.parent.color = BLACK;
  11.                     y.color = BLACK;
  12.                     x.parent.parent.color = RED;
  13.                     x = x.parent.parent;
  14.                 } else {
  15.                     if (x == x.parent.right) {
  16.                         // Case 2: x's uncle y is black and x is a right child.
  17.                         // System.out.println("rbInsertFixup: Case 2 left");
  18.                         x = x.parent;
  19.                         rotateLeft(x);
  20.                     }
  21.                     // Case 3: x's uncle y is black and x is a left child.
  22.                     //System.out.println("rbInsertFixup: Case 3 left");
  23.                     x.parent.color = BLACK;
  24.                     x.parent.parent.color = RED;
  25.                     rotateRight(x.parent.parent);
  26.                 }
  27.             } else {
  28.                 // x's parent is a right child.  Do the same as when x's
  29.                 // parent is a left child, but exchange "left" and "right."
  30.                 Entry<K,V> y = x.parent.parent.left;
  31.                 if (y != null && y.color == RED) {
  32.                     // Case 1: x's uncle y is red.
  33.                     // System.out.println("rbInsertFixup: Case 1 right");
  34.                     x.parent.color = BLACK;
  35.                     y.color = BLACK;
  36.                     x.parent.parent.color = RED;
  37.                     x = x.parent.parent;
  38.                 } else {
  39.                     if (x == x.parent.left) {
  40.                         // Case 2: x's uncle y is black and x is a left child.
  41.                         // System.out.println("rbInsertFixup: Case 2 right");
  42.                         x = x.parent;
  43.                         rotateRight(x);
  44.                     }
  45.                     // Case 3: x's uncle y is black and x is a right child.
  46.                     // System.out.println("rbInsertFixup: Case 3 right");
  47.                     x.parent.color = BLACK;
  48.                     x.parent.parent.color = RED;
  49.                     rotateLeft(x.parent.parent);
  50.                 }
  51.             }
  52.         }
  53.         // The root is always black.
  54.         root.color = BLACK;
  55.     }
  56.     /**
  57.      * Do a right rotation around this node.
  58.     */
  59.     private void rotateRight(Entry<K,V> y) {
  60.         if(y != null){
  61.             Entry<K,V> x = y.left;
  62.             y.left = x.right;
  63.             if (x.right != null)
  64.                 x.right.parent = y;
  65.             x.parent = y.parent;
  66.             if (y.parent == null) {
  67.                 root = (Entry)x;
  68.             } else if (y == y.parent.right){
  69.                 y.parent.right = x;
  70.             } else {
  71.                 x.parent.left = x;
  72.             }
  73.             x.right = y;
  74.             y.parent = x;
  75.         }
  76.     }
  77.     /**
  78.      * Do a left rotation around this node.
  79.     */
  80.     private void rotateLeft(Entry<K,V> x) {
  81.         if(x != null){
  82.             Entry<K,V> y = x.right;
  83.             x.right = y.left;
  84.             if (y.left != null)
  85.                 y.left.parent = x;
  86.             y.parent = x.parent;
  87.             if (x.parent == null) {
  88.                 root = (Entry)y;
  89.             } else if (x == x.parent.left) {
  90.                 x.parent.left = y;
  91.             } else {
  92.                 x.parent.right = y;
  93.             }
  94.             y.left = x;
  95.             x.parent = y;
  96.         }        
  97.     }

Y ahí es cuando no me doy cuenta en cómo resolverlos. ¿Cómo resuelvo esta falla?

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #4 (permalink)  
Antiguo 14/06/2018, 05:07
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.431
Antigüedad: 9 años, 9 meses
Puntos: 181
Respuesta: Balanceos con Árboles Hash

Prueba esto:

1. Introducir 2 o 3 elementos en vez de todos los que introduces e ir añadiendo cada vez más elementos a ver si se pierde e imprimir solo el size sin llamar a toString para ninguno de los 2 mapas.

2. Ejecutar solo este código:

System.out.println("* tamaño mapa 2: " + map2.size());
System.out.println(map2.toString());

pero no el equivalente para map1 (Sospecho que map1.toString() puede interferir en el contenido de map2).

Si fuese éste el problema tendrías que revisar el punto de ejecución donde se elimina el elemento del primer map y corregirlo.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #5 (permalink)  
Antiguo 14/06/2018, 19:23
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Respuesta: Balanceos con Árboles Hash

Hola FuzzyLog gracias por responder y le diste al blanco, verás uso este código para probar:

Código Java:
Ver original
  1. private static void insertAllWithClass(){
  2.         Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  3.         Persona.maxIdUp();
  4.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  5.         Persona.maxIdUp();
  6.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  7.         Persona.maxIdUp();
  8.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  9.         Persona.maxIdUp();
  10.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  11.         Persona.maxIdUp();
  12.         MyTreeMap<Integer,Persona> map = new MyTreeMap();
  13.         map.put(p1.getId(), p1);
  14.         map.put(p2.getId(), p2);
  15.         map.put(p3.getId(), p3);
  16.         map.put(p4.getId(), p4);
  17.         map.put(p5.getId(), p5);
  18.         MyTreeMap<Integer,Persona> map2 = new MyTreeMap(map);
  19.         System.out.println("* tamaño mapa 1: " + map.size());
  20.         System.out.println(map);
  21.         System.out.println("* tamaño mapa 2: " + map2.size());
  22.         System.out.println(map2);
  23.     }

Cuando inserto 2, pasa esto:

Cita:
* tamaño mapa 1: 2
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 2
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
Cuando son 3:

Cita:
* tamaño mapa 1: 3
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 3
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
Hasta 4 funciona bien:

Cita:
* tamaño mapa 1: 4
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 4
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
De 5 en adelante es el problema y el rotateLeft es el que me está complicando:

Código Java:
Ver original
  1. private void rotateLeft(Entry<K,V> p) {
  2.         if(p != null){
  3.             Entry<K,V> r = p.right;
  4.             p.right = r.left; // esta es la línea del problema
  5.             if (r.left != null)
  6.                 r.left.parent = p;
  7.             r.parent = p.parent;
  8.             if (p.parent == null) {
  9.                 root = (Entry)r;
  10.             } else if (p == p.parent.left) {
  11.                 p.parent.left = r;
  12.             } else {
  13.                 p.parent.right = r;
  14.             }
  15.             r.left = p;
  16.             p.parent = r;
  17.         }        
  18.     }

¿cómo lo soluciono?

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias

Última edición por detective_jd; 14/06/2018 a las 20:26
  #6 (permalink)  
Antiguo 15/06/2018, 04:43
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.431
Antigüedad: 9 años, 9 meses
Puntos: 181
Respuesta: Balanceos con Árboles Hash

El problema que tienes es que estás creando un segundo Map con una referencia al contenido del primer Map.

Si ejecutas algún método que modifique el contenido del primer map, automáticamente se modificará también para el segundo map.

Un método toString() no debería en ningún caso reordenar los contenidos, sino mostrar su contenido tal cual está.

es mejor que separes cualquier método para reorganizar un map de los métodos de visualización.

Luego tendrás que revisar qué quieres hacer con esos métodos rotate, y si realmente hacen lo que deben, ya que no deberían eliminar contenido sino que en todo caso debería modificarse su posición.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #7 (permalink)  
Antiguo 15/06/2018, 20:29
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Respuesta: Balanceos con Árboles Hash

Hola FuzzyLog gracias por responder y si querías ver algo mucho más troll, es que probé sin toString y me hace esto:

Cita:
* tamaño mapa 1: 5
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
* tamaño mapa 2: 4
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
O sea el 3 está bien escondido jaja, cuando tu código te hace ver cómo idiota jaja,

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #8 (permalink)  
Antiguo 18/06/2018, 05:47
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.431
Antigüedad: 9 años, 9 meses
Puntos: 181
Respuesta: Balanceos con Árboles Hash

Por defecto al tratar de imprimir un objeto te llama al toString sin necesidad de que tú lo especifiques.

La diferencia que podría tener es que lo q muestra es el valor que queda después de finalizar la ejecución.

Pero lo cierto es que sí ejecuta el toString.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #9 (permalink)  
Antiguo 18/06/2018, 21:50
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Respuesta: Balanceos con Árboles Hash

Hola FuzzyLog gracias por responder, resolví el problema del elemento que se borraba, resulta que era el put el que no funcionaba bien y logré cambiarlo:

Código Java:
Ver original
  1. public V put(K key, V value) {
  2.         if(key != null){
  3.             Entry<K,V> e = new Entry(key, value);
  4.             Entry<K,V> parent = null;
  5.             Entry<K,V> t = root;        
  6.             int cmp = 0;
  7.             while (t != null) {
  8.                 parent = t;
  9.                 Comparable<? super K> k = (Comparable<? super K>) key;
  10.                 cmp = (comparator != null) ? comparator.compare(key,t.key) : k.compareTo(t.key);
  11.                 if(cmp < 0){
  12.                     t = t.left;
  13.                 } else if(cmp > 0) {
  14.                     t = t.right;
  15.                 } else {
  16.                     t.value = value;
  17.                     return value;
  18.                 }
  19.             }
  20.             e.parent = parent;
  21.             if(t == null){
  22.                 root = e;
  23.             } else if (cmp < 0) {
  24.                 parent.left = e;
  25.             } else {
  26.                 parent.right = e;
  27.             }
  28.             rbInsertFixup(e);
  29.             size++;
  30.         }
  31.         return null;
  32.     }

sólo que ahora me muestra así:
Cita:
* tamaño mapa 1: 5
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
* tamaño mapa 2: 5
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
en el map1 me lo ordena de forma decreciente y el 2 creciente, cuando los 2 tendrían que estar creciente.
Apenas hice estos otros cambios:

Código Java:
Ver original
  1. private void rbInsertFixup(Entry<K,V> x) {
  2.         x.color = RED;
  3.         while (x.parent != null && x.parent.color == RED) {
  4.             if (x.parent == x.parent.parent.left) {
  5.                 Entry<K,V> y = x.parent.parent.right;
  6.                 if (y != null && y.color == RED) {
  7.                     x.parent.color = BLACK;
  8.                     y.color = BLACK;
  9.                     x.parent.parent.color = RED;
  10.                     x = x.parent.parent;
  11.                 } else {
  12.                     if (x == x.parent.right) {
  13.                         x = x.parent;
  14.                         rotateLeft(x);
  15.                     } else {
  16.                         x.parent.color = BLACK;
  17.                         x.parent.parent.color = RED;
  18.                         rotateRight(x.parent.parent);
  19.                     }
  20.                 }
  21.             } else {
  22.                 Entry<K,V> y = x.parent.parent.left;
  23.                 if (y != null && y.color == RED) {
  24.                     x.parent.color = BLACK;
  25.                     y.color = BLACK;
  26.                     x.parent.parent.color = RED;
  27.                     x = x.parent.parent;
  28.                 } else {
  29.                     if (x == x.parent.left) {
  30.                         x = x.parent;
  31.                         rotateRight(x);
  32.                     } else {
  33.                         x.parent.color = BLACK;
  34.                         x.parent.parent.color = RED;
  35.                         rotateLeft(x.parent.parent);
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         root.color = BLACK;
  41.     }
  42.     /**
  43.      * Do a right rotation around this node.
  44.     */
  45.     private void rotateRight(Entry<K,V> p) {
  46.         Entry<K,V> x = p.left;
  47.         p.left = x.right;
  48.         if (x.right != null)
  49.             x.right.parent = p;
  50.         x.parent = p.parent;
  51.         x.right = p;
  52.         p.right = x;
  53.         if (p.parent == null) {
  54.             root = (Entry)x;
  55.         } else if (p == p.parent.right){
  56.             p.parent.right = x;
  57.         } else {
  58.             x.parent.left = x;
  59.         }        
  60.     }
  61.     /**
  62.      * Do a left rotation around this node.
  63.     */
  64.     private void rotateLeft(Entry<K,V> p) {        
  65.         Entry<K,V> y = p.right;
  66.         p.right = y.left;
  67.         if (y.left != null)
  68.             y.left.parent = p;
  69.         y.parent = p.parent;
  70.         if (p.parent == null) {
  71.             root = (Entry)y;
  72.         } else if (p == p.parent.left) {
  73.             p.parent.left = y;
  74.         } else {
  75.             p.parent.right = y;
  76.         }
  77.         y.left = p;
  78.         p.parent = y;
  79.     }

Espero sus respuestas y saludos.

PD: El toString ya no está más, desapareció.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #10 (permalink)  
Antiguo 19/06/2018, 20:38
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Respuesta: Balanceos con Árboles Hash

Cuando tu satisfacción se vuelve una decepción, resulta que el código de ayer estaba mal si lo pongo así quedo cómo estaba:

Código Java:
Ver original
  1. @Override
  2.     public V put(K key, V value) {
  3.         if(key != null){
  4.             Entry<K,V> z = new Entry(key, value);
  5.             Entry<K,V> y = null;
  6.             Entry<K,V> x = root;        
  7.             int cmp = 0;
  8.             if(comparator != null){
  9.                 while (x != null) {
  10.                     y = x;
  11.                     cmp = comparator.compare(key,x.key);
  12.                     if(cmp < 0){
  13.                         x = x.left;
  14.                     } else if(cmp > 0) {
  15.                         x = x.right;
  16.                     } else {
  17.                         x.value = value;
  18.                         return value;
  19.                     }
  20.                 }
  21.             } else {
  22.                 while (x != null) {
  23.                     y = x;
  24.                     Comparable<? super K> k = (Comparable<? super K>) key;
  25.                     cmp = k.compareTo(x.key);
  26.                     if(cmp < 0){
  27.                         x = x.left;
  28.                     } else if(cmp > 0) {
  29.                         x = x.right;
  30.                     } else {
  31.                         x.value = value;
  32.                         return value;
  33.                     }
  34.                 }
  35.             }            
  36.             z.parent = y;
  37.             if(y == null){ // si pongo x en el ifme muestra 5 elementos sino me muestra 4
  38.                 root = z;
  39.             } else if (cmp < 0) {
  40.                 y.left = z;
  41.             } else {
  42.                 y.right = z;
  43.             }
  44.             z.color = RED;
  45.             rbInsertFixup(z);
  46.             size++;
  47.         }
  48.         return null;
  49.     }

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #11 (permalink)  
Antiguo Ayer, 20:25
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 360
Antigüedad: 7 años, 2 meses
Puntos: 4
Respuesta: Balanceos con Árboles Hash

Buenas noticias logré hacer andar el código pudiendo poner datos de un map a otro, tenía que arreglar el put, fixUp y el successor:

Código Java:
Ver original
  1. @Override
  2.     public V put(K key, V value) {
  3.         if(key != null){
  4.             Entry<K,V> t = root;
  5.             if(t == null){
  6.                 root = new Entry(key,value,null);
  7.                 size = 1;
  8.             } else {
  9.                 Entry<K,V> parent = null;                    
  10.                 int cmp = 0;
  11.                 while (t != null) {
  12.                     parent = t;
  13.                     cmp = checkCompare(t,key);
  14.                     if(cmp < 0){
  15.                         t = t.left;
  16.                     } else if(cmp > 0) {
  17.                         t = t.right;
  18.                     } else {
  19.                         return t.value = value;
  20.                     }
  21.                 }
  22.                 Entry<K,V> e = new Entry<>(key, value, parent);
  23.                 if (cmp < 0) {
  24.                     parent.left = e;
  25.                 } else {
  26.                     parent.right = e;
  27.                 }
  28.                 e.color = RED;
  29.                 fixUp(e);
  30.                 size++;
  31.             }                            
  32.         }
  33.         return null;
  34.     }
  35.     private int checkCompare(Entry<K,V>x, K key){
  36.         if(comparator != null){
  37.             return comparator.compare(key,x.key);
  38.         } else {
  39.             Comparable<? super K> k = (Comparable<? super K>) key;
  40.             return k.compareTo(x.key);
  41.         }
  42.     }
  43.     private void fixUp(Entry<K,V> x) {
  44.         while (x != null && x != root && x.parent.color == RED) {
  45.             if (x.parent == x.parent.parent.left) {
  46.                 Entry<K,V> y = x.parent.parent.right;
  47.                 if (y != null && y.color == RED) {
  48.                     x.parent.color = BLACK;
  49.                     y.color = BLACK;
  50.                     x.parent.parent.color = RED;
  51.                     x = x.parent.parent;
  52.                 } else {
  53.                     if (x == x.parent.right) {
  54.                         x = x.parent;
  55.                         rotateLeft(x);
  56.                     } else {
  57.                         x.parent.color = BLACK;
  58.                         x.parent.parent.color = RED;
  59.                         rotateRight(x.parent.parent);
  60.                     }
  61.                 }
  62.             } else {
  63.                 Entry<K,V> y = x.parent.parent.left;
  64.                 if (y != null && y.color == RED) {
  65.                     x.parent.color = BLACK;
  66.                     y.color = BLACK;
  67.                     x.parent.parent.color = RED;
  68.                     x = x.parent.parent;
  69.                 } else {
  70.                     if (x == x.parent.left) {
  71.                         x = x.parent;
  72.                         rotateRight(x);
  73.                     } else {
  74.                         x.parent.color = BLACK;
  75.                         x.parent.parent.color = RED;
  76.                         rotateLeft(x.parent.parent);
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.         root.color = BLACK;
  82.     }
  83.     /**
  84.      * Do a right rotation around this node.
  85.     */
  86.     private void rotateRight(Entry<K,V> p) {
  87.         Entry<K,V> x = p.left;
  88.         p.left = x.right;
  89.         if (x.right != null)
  90.             x.right.parent = p;
  91.         x.parent = p.parent;
  92.         x.right = p;
  93.         p.right = x;
  94.         if (p.parent == null) {
  95.             root = (Entry)x;
  96.         } else if (p == p.parent.right){
  97.             p.parent.right = x;
  98.         } else {
  99.             x.parent.left = x;
  100.         }        
  101.     }
  102.     /**
  103.      * Do a left rotation around this node.
  104.     */
  105.     private void rotateLeft(Entry<K,V> p) {        
  106.         Entry<K,V> y = p.right;
  107.         p.right = y.left;
  108.         if (y.left != null)
  109.             y.left.parent = p;
  110.         y.parent = p.parent;
  111.         if (p.parent == null) {
  112.             root = (Entry)y;
  113.         } else if (p == p.parent.left) {
  114.             p.parent.left = y;
  115.         } else {
  116.             p.parent.right = y;
  117.         }
  118.         y.left = p;
  119.         p.parent = y;
  120.     }
  121.     //copié el successor de Oracle, claro está
  122.     private Entry<K,V> successor(Entry<K,V> t) {      
  123.         if (t == null)
  124.             return null;
  125.         else if (t.right != null) {
  126.             Entry<K,V> p = t.right;
  127.             while (p.left != null)
  128.                 p = p.left;
  129.             return p;
  130.         } else {
  131.             Entry<K,V> p = t.parent;
  132.             Entry<K,V> ch = t;
  133.             while (p != null && ch == p.right) {
  134.                 ch = p;
  135.                 p = p.parent;
  136.             }
  137.             return p;
  138.         }
  139.     }

Y los test de inserción simple, inserción con clases, y defiendo el órden por las claves de forma creciente andan, pero cuando quiero que me los inserte ordenados por las claves de forma decreciente no andan bien, me hace esto:

Cita:
---- prueba 4 ----
tamaño: 10

[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
................
El código es prueba es este:

Código Java:
Ver original
  1. private static void insertWithClassOrderDesc(){
  2.         Persona.resetId();
  3.         MyTreeMap<Integer,Persona> map = new MyTreeMap(new OrdenarDesc());
  4.         Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  5.         Persona.maxIdUp();
  6.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  7.         Persona.maxIdUp();
  8.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  9.         Persona.maxIdUp();
  10.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  11.         Persona.maxIdUp();
  12.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  13.         Persona.maxIdUp();
  14.         Persona p6 = new Persona(Persona.getMaxId(), "Pedro", 16);
  15.         Persona.maxIdUp();
  16.         Persona p7 = new Persona(Persona.getMaxId(), "Deborah", 26);
  17.         Persona.maxIdUp();
  18.         Persona p8 = new Persona(Persona.getMaxId(), "Nelson", 37);
  19.         Persona.maxIdUp();
  20.         Persona p9 = new Persona(Persona.getMaxId(), "Tommy", 22);
  21.         Persona.maxIdUp();
  22.         Persona p10 = new Persona(Persona.getMaxId(), "Manuela", 15);
  23.         Persona.maxIdUp();
  24.         map.put(p1.getId(), p1);
  25.         map.put(p2.getId(), p2);
  26.         map.put(p3.getId(), p3);
  27.         map.put(p4.getId(), p4);
  28.         map.put(p5.getId(), p5);
  29.         map.put(p6.getId(), p6);
  30.         map.put(p7.getId(), p7);
  31.         map.put(p8.getId(), p8);
  32.         map.put(p9.getId(), p9);
  33.         map.put(p10.getId(), p10);
  34.         map.put(10, new Persona(10, "Micaela", 21));
  35.         map.put(6, new Persona(6, "Sergio", 25));
  36.         map.put(null, new Persona(11, "Sefafin", 7));
  37.         System.out.println("---- prueba 4 ----");
  38.         System.out.println("tamaño: " + map.size() + "\n");
  39.         map.entrySet().forEach((e)->{
  40.             System.out.println(e);
  41.         });
  42.         //System.out.println(map);
  43.     }

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias



La zona horaria es GMT -6. Ahora son las 06:09.