Tema: Balanceos con Árboles Hash
Ver Mensaje Individual
  #11 (permalink)  
Antiguo 22/06/2018, 20:25
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
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