Balanceos con Árboles Hash

[detective_jd]

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:

public V put(K key, V value) {
        if(key != null){
            Entry<K,V> e = new Entry(key, value);
            Entry<K,V> parent = null;
            Entry<K,V> t = root;        
            int cmp = 0;
            while (t != null) {
                parent = t;
                Comparable<? super K> k = (Comparable<? super K>) key;
                cmp = (comparator != null) ? comparator.compare(key,t.key) : k.compareTo(t.key);
                if(cmp < 0){
                    t = t.left;
                } else if(cmp > 0) {
                    t = t.right;
                } else {
                    t.value = value;
                    return value;
                } 
            }
            e.parent = parent;
            if(t == null){
                root = e;
            } else if (cmp < 0) {
                parent.left = e;
            } else {
                parent.right = e;
            }
            rbInsertFixup(e);
            size++;
        }
        return null;
    }
 

sólo que ahora me muestra así:

* 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:

private void rbInsertFixup(Entry<K,V> x) {
        x.color = RED;
        while (x.parent != null && x.parent.color == RED) {
            if (x.parent == x.parent.parent.left) {
                Entry<K,V> y = x.parent.parent.right;
                if (y != null && y.color == RED) {
                    x.parent.color = BLACK;
                    y.color = BLACK;
                    x.parent.parent.color = RED;
                    x = x.parent.parent;
                } else {
                    if (x == x.parent.right) {
                        x = x.parent;
                        rotateLeft(x);
                    } else {
                        x.parent.color = BLACK;
                        x.parent.parent.color = RED;
                        rotateRight(x.parent.parent);
                    }
                }
            } else {
                Entry<K,V> y = x.parent.parent.left; 
                if (y != null && y.color == RED) {
                    x.parent.color = BLACK;
                    y.color = BLACK;
                    x.parent.parent.color = RED;
                    x = x.parent.parent;
                } else {
                    if (x == x.parent.left) {
                        x = x.parent;
                        rotateRight(x);
                    } else {
                        x.parent.color = BLACK;
                        x.parent.parent.color = RED;
                        rotateLeft(x.parent.parent);
                    }
                }
            }
        }
        root.color = BLACK;
    }
    /**
     * Do a right rotation around this node.
    */
    private void rotateRight(Entry<K,V> p) {
        Entry<K,V> x = p.left;
        p.left = x.right;
        if (x.right != null)
            x.right.parent = p;
        x.parent = p.parent;
        x.right = p;
        p.right = x;
        if (p.parent == null) {
            root = (Entry)x;
        } else if (p == p.parent.right){ 
            p.parent.right = x;
        } else {
            x.parent.left = x;
        }        
    }
    /**
     * Do a left rotation around this node.
    */
    private void rotateLeft(Entry<K,V> p) {        
        Entry<K,V> y = p.right;
        p.right = y.left;
        if (y.left != null)
            y.left.parent = p;
        y.parent = p.parent;
        if (p.parent == null) {
            root = (Entry)y;
        } else if (p == p.parent.left) {
            p.parent.left = y;
        } else {
            p.parent.right = y;
        }
        y.left = p;
        p.parent = y; 
    }
 

Espero sus respuestas y saludos.

PD: El toString ya no está más, desapareció.