Usunięcie w lewym krzywym czerwonym czarnym drzewku

Question

Uczę się o Left Leaning Red Black Trees.

W algorytmie usuwania usuniętym z papieru, jeśli klucz pasuje do węzła, a prawy poddrzewo ma wartość NULL dla tego węzła, węzeł ten jest usuwany. Ale może być również poddrzewo, które nie jest brane pod uwagę.

Nie jestem w stanie zrozumieć dlaczego lewy poddrzewo miałoby być NULL również. Podobnie dzieje się podczas usuwania minimum lub maksimum. Czy ktokolwiek mógłby mi w tym pomóc?

Answer 1

Wydaje mówisz o tym kawałku kodu:

if (isRed(h.left)) 
    h = rotateRight(h); 
if (key.compareTo(h.key) == 0 && (h.right == null)) 
    return null; 

Tutaj lewy potomek nie może być „czerwony”, ponieważ kod poprzedzających byłoby obrócić ją w prawo.

Również potomek nie może być "czarny", ponieważ w tym przypadku na lewo od h znajduje się ścieżka zawierająca co najmniej jeden "czarny" węzeł, podczas gdy żadna ścieżka po prawej stronie nie ma żadnych "czarnych" węzłów. Ale w drzewie RB liczba czarnych węzłów na każdej ścieżce musi być taka sama.

Oznacza to, że w ogóle nie ma potomka, a węzeł h jest węzłem liści.

Funkcja nie ma potrzeby sprawdzania prawego pod-drzewa, jeśli lewe pod-drzewo jest puste, ponieważ prawe pod-drzewo drzewa LLRB nie może być większe niż odpowiadające mu lewe drzewo podrzędne.

Answer 2

Istnieje interesująca analiza tego, czy lewostronne czerwone czarne drzewa są naprawdę lepsze, czy nawet prostsze niż wcześniejsze implementacje. Artykuł Left-Leaning Red Black Trees Considered Harmful został napisany przez profesora Harvarda Comp Sci Eddie Kohler. Pisze:

Tricky writing 

Sedgewick’s paper is tricky. As of 2013, the insert section presents 2–3–4 trees as 
the default and describes 2–3 trees as a variant. The delete implementation, however, 
only works for 2–3 trees. If you implement the default variant of insert and the 
only variant of delete,your tree won’t work. The text doesn’t highlight the switch 
from 2–3–4 to 2–3: not kind.