Tema: Balanceos con Árboles Hash
Ver Mensaje Individual
  #1 (permalink)  
Antiguo 12/06/2018, 20:18
Avatar de detective_jd
detective_jd
 
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
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