Cześć,
analizując sposób reprezentacji drzew czerwono-czarnych w witrynie: https://algs4.cs.princeton.edu/33balanced napotkałem problem w metodzie, która usuwa minimum.
Autorzy, dla całej struktury zaproponowali układ, w którym czerwone odnośniki mogą być tylko po lewej stronie.
W usuwaniu minimalnej wartości, aby zachować zbalansowanie drzewa, zakładamy, że kolejny węzeł nie może być podwójny (tj. czarny). Jeżeli jest - wykonujemy odpowiednie transformacje Tutaj znajduje się moje pytanie. Dlaczego w kodzie sprawdzamy dwa kolejne węzły zamiast tylko jednego?
Kod całej klasy dostępny jest tutaj:
Metoda minimum, i wszystkie inne wymagane do jej działania, wyglądają następująco:
public void deleteMin(){
if(isEmpty())
return;
root = deleteMin(root);
}
private Node deleteMin(Node x) {
if(x.left == null)
return null;
//Chodzi mi to ten fragment
if(!isRed(x.left) && !isRed(x.left.left)){
flipColors(x);
if (isRed(x.right.left)) {
x.right = rotateRight(x.right);
x = rotateLeft(x);
flipColors(x);
}
}
x.left = deleteMin(x.left);
return balance(x);
}
private Node balance(Node h) {
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
private Node rotateLeft(Node h)
{
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
private Node rotateRight(Node h)
{
Node x= h.left;
h.left = x.right;
x.right = h;
x. color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
private void flipColors(Node h)
{
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}