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 originalprivate void rbInsertFixup(Entry<K,V> x) {
x.color = RED;
while (x.parent != null && x != root && x.parent.color == RED) {
if (x.parent == x.parent.parent.left) {
// x's parent is a left child.
Entry<K,V> y = x.parent.parent.right;
if (y != null && y.color == RED) {
// Case 1: x's uncle y is red.
// System.out.println("rbInsertFixup: Case 1 left");
x.parent.color = BLACK;
y.color = BLACK;
x.parent.parent.color = RED;
x = x.parent.parent;
} else {
if (x == x.parent.right) {
// Case 2: x's uncle y is black and x is a right child.
// System.out.println("rbInsertFixup: Case 2 left");
x = x.parent;
rotateLeft(x);
}
// Case 3: x's uncle y is black and x is a left child.
//System.out.println("rbInsertFixup: Case 3 left");
x.parent.color = BLACK;
x.parent.parent.color = RED;
rotateRight(x.parent.parent);
}
} else {
// x's parent is a right child. Do the same as when x's
// parent is a left child, but exchange "left" and "right."
Entry<K,V> y = x.parent.parent.left;
if (y != null && y.color == RED) {
// Case 1: x's uncle y is red.
// System.out.println("rbInsertFixup: Case 1 right");
x.parent.color = BLACK;
y.color = BLACK;
x.parent.parent.color = RED;
x = x.parent.parent;
} else {
if (x == x.parent.left) {
// Case 2: x's uncle y is black and x is a left child.
// System.out.println("rbInsertFixup: Case 2 right");
x = x.parent;
rotateRight(x);
}
// Case 3: x's uncle y is black and x is a right child.
// System.out.println("rbInsertFixup: Case 3 right");
x.parent.color = BLACK;
x.parent.parent.color = RED;
rotateLeft(x.parent.parent);
}
}
}
// The root is always black.
root.color = BLACK;
}
/**
* Do a right rotation around this node.
*/
private void rotateRight(Entry<K,V> y) {
if(y != null){
Entry<K,V> x = y.left;
y.left = x.right;
if (x.right != null)
x.right.parent = y;
x.parent = y.parent;
if (y.parent == null) {
root = (Entry)x;
} else if (y == y.parent.right){
y.parent.right = x;
} else {
x.parent.left = x;
}
x.right = y;
y.parent = x;
}
}
/**
* Do a left rotation around this node.
*/
private void rotateLeft(Entry<K,V> x) {
if(x != null){
Entry<K,V> y = x.right;
x.right = y.left;
if (y.left != null)
y.left.parent = x;
y.parent = x.parent;
if (x.parent == null) {
root = (Entry)y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
}
Y ahí es cuando no me doy cuenta en cómo resolverlos. ¿Cómo resuelvo esta falla?
Espero sus respuestas y saludos.