Witam.
Proszę was o pomoc bo już nie mogę sobie z tym poradzić. PRzekopałem już tyle prezentacji, książek i skryptów, że nie wiem jak to rzowiązać, bo problem pojawia się kiedy w drzewie jest mało elementów.
Poniżej podaję treść metody dodającej i koloryzującej drzewo.
Ten algorytm też testowałem. Niestety też pojawiają się takie same błędy.
Po pierwsze jest to bardzo ciekawe, że przeszukałeś tak wiele materiałów i każdy kod zwraca ten sam błąd. Wniosek jest chyba oczywisty dotychczasowa nauka o drzewa RB to jakaś ściema. Mi np. kod z tamtej strony działa na SPOJu w jednym zadaniu, gdzie potrzebowałem napisać słownik, więc nie wierzę, że go zaprogramowałeś, po prostu szukasz jelenia, który zrobi to za ciebie. Mam więc propozycję:
Nie szukam jelenia, który zrobi to za mnie. Zaprogramowałem całe drzewo, ale nie mogę sobie poradzić tylko z naprawianiem własności kolorów. Po prostu gdzieś w moim rozumowaniu tego kodu jest błąd i szukam tylko kogoś kto wskaże mi błąd w moim myśleniu. Gdzieś mam źle ustawionego ifa, albo coś innego, ale nie potrafię zlokalizować tego miejsca.
Bardzo “dziękuję” za Twoją jakże nieocenioną pomoc, ale muszę Cię zmartwić bo Google to ja mam i gotowce też potrafię sobie znaleźć - skoro szukam tutaj pomocy to widocznie to co jest w Google jest w jakimś stopniu dla mnie nie jasne. Nie chcesz pomagać to przynajmniej siedź cicho.
Nie odniosłem się do twojego kodu, bo to porażka, jest tyle błędów, że szybciej będzie napisać to od początku. Porównajmy z pseudo kodem:
Ok. Przepraszam bo faktycznie racji nie miałem. Błąd, na który zwróciłeś mi uwagę wynika stąd, że przepisywałem kilka razy ten pseudokod i w końcu zacząłem usuwać część odwołań o poziom wyżej i wyszło to co wyszło.
while x <> root[T] and color[p[x]] = RED
Nie ma takiej możliwości, ponieważ musisz być różny od korzenia, a tylko korzeń może nie mieć rodzica w drzewie (definicja korzenia). Ale za to może nie istnieć dziadek. Przy czym dla tego konkretnego przypadku łatwo to rozwiązać, korzeniem nie będzie element bez rodzica, ale będący swoim własnym rodzicem, wtedy korzeń co prawda zostanie ustawiony na czerwony może zostać ustawiony na czerwony, ale dzięki ostatniej linijce
color[root[T]] := BLACK
niezmiennik zostanie przywrócony.
Ok. A co jeśli p[p[x]] nie istnieje? Jak mam traktować sytuację, w której mam korzeń z key = 5. Chcę wstawić 4. Pójdzie ona na lewo, a w czasie wstawiania uruchomi się metoda przywracania wartości kolorów i wysypie się na etapie:
y := right[p[p[x]]]
bo przecież 4, która jest x ma p[x], ale już p[p[x]] nie istnieje.
Przeczytaj jeszcze raz post #8, szczególnie tę część o dziadku.
Nie wiem czy dobrze rozumiem. W takim przypadku za dziadka mam uznać p[x] czyli rodzica tzn. korzeń?
Tak. Najlepiej po prostu przy wstawianiu korzenia ustawić mu jako rodzica jego samego. A jeśli gdziekolwiek wyszukiwanie korzenia polega na przemieszczaniu się do góry w drzewie, do czasu aż
p[x] = null
to wystarczy zamienić na
Ok. Dzięki, a mógłbyś mi jeszcze podpowiedzieć w jaki sposób naprawić błąd w rotacjach? Patrząc na kod lewej rotacji: problem jest taki, że jeśli mój y nie istnieje to sypie błędem. A nie mogę w tym wypadku pominąć części poleceń bo po prostu drzewo nie zadziała tak jak powinno.
Nie stwierdzam nic takiego w załączonym pseudokodzie w linku. Y oznacza w tym wypadku prawy element, który dodałeś i nastąpiło wychylenie drzewa na prawo stąd rotujesz w lewo, więc nie może być sytuacji w której jego nie ma, bo nie byłoby wychylenia. Przepisz ten pseudokod na javę tam są wszystkie przypadki rozważone…
Ok. Widocznie się gdzieś pomyliłem przy kodowaniu. Dziękuję Ci bardzo za pomoc 
Znalazłem, jeszcze coś takiego, tylko, że w C++, ale myślę, że jest to na tyle podobne do Javy, że nie powinno być problemu. Jest tu lepsze formatowanie i trochę więcej komentarzy, ale idea ciągle ta sama. LINK
Dzięki 