Ver Mensaje Individual
  #9 (permalink)  
Antiguo 18/06/2018, 21:50
Avatar de detective_jd
detective_jd
 
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 8 meses
Puntos: 6
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