Witam. Uczę się do poprawki z algorytmów i korzystam z tego apletu, żeby sobie jakoś to wszystko zobrazować i sprawdzić czy nie robię błędów: http://people.ksp.sk/~kuko/bak/index.html
Teraz pytanie dlaczego to robi tyle ruchów? Usuwam wierzchołek 62. Czy na drugim drzewie (po wrzuceniu 68 w miejsce 62) nie są spełnione właściwości drzewa czerwono-czarnego? Jeżeli tak to dlaczego? Bo wg mnie to właśnie drugie drzewo powinno być efektem końcowym i nie rozumiem po co jeszcze dalsze działania. Bardzo proszę o wytłumaczenie bo już mi się miesza wszystko.
0
0
A wiesz że tam jest w tym aplecie taka opcja "pause" i po prawej stronie w okienku będzie ci krok po kroku wypisywać co się dzieje i czemu?
0
Przecież ta opcja jest domyślnie zaznaczona i czytam te wskazówki. Tylko, że one nie mówią o który węzeł dokładnie chodzi. Po prostu chciałbym aby ktoś opisał w tym konkretnym przypadku dlaczego tak jest a nie inaczej. A dokładniej dlaczego usuwanie nie kończy się na drugim obrazku.
0
Ech ok, ale nie widze tej twojej poprawki:
Na drzewku 2 jeśli startujemy z węzła 68 to dojście do liścia (tego NULLowego) przy węźle 81 powoduje przejście przez 2 czarne węzły (założenie że NULL jest czarny) a dojście do dowolnego innego liścia jest przez 3 czarne węzły, ergo własności nie są zachowane i trzeba rotować (oczywiście startując z węzła 81 mamy analogiczną sytuację)
0
No i o taką odpowiedź mi chodziło. Nie wiedziałem, że warunek musi być spełniony także. dla pustych węzłów. Dzięki