Czy można w pełni nie zrozumieć drzew RB? [Zamknięte]

Właśnie nauczyłem się czerwonych czarnych drzew w Cormen i łał! Zazwyczaj lubię rozumieć wszystkie algorytmy i struktury danych do tego stopnia, że ​​mogę je odbudować od zera bez konieczności oszukiwania, patrząc na pseudo kod. Naprawdę lubię algorytmy, więc lubię uczyć się, jak one działają, i zwykle chodzę wiersz po wierszu i wypróbowuję niektóre przypadki, patrząc na kod i sprawdzając, czy to, co się dzieje, jest tym, co zrozumiałem, że powinno się zdarzyć.

Samo zrozumienie, co się dzieje, zajęło mi dużo czasu dla drzew RB. Mimo wyjaśnień tej książki wciąż trudno mi było zrozumieć kod. Nie wspominając już o tym, że nie mogłem zrozumieć, jak / dlaczego działają rotacje. Nie uważam tego za intuicyjne. Mam na myśli trzy (właściwie sześć) różnych przypadków do wstawienia, a następnie 4 przypadki do usunięcia? Czy można to zrozumieć? Nie mogę odbudować tego kodu bez oszukiwania. Aż do binarnego drzewa mogłem wdrożyć te rzeczy z mojej głowy, z pewnymi poprawkami zawsze działałyby, ale drzew RB nawet nie spróbuję. To znaczy, nawet nauczyciel czasami się mylił, więc przypuszczam, że to naprawdę nie jest takie łatwe, ale jednocześnie nie powinniśmy rozumieć wszystkiego, co się dzieje, a przynajmniej dlaczego? Książka nie Naprawdę wyjaśniam, jak ktoś wpadł na pomysł rotacji. Jak ktoś zauważył, że przy 2 obrotach możesz rozwiązać problem z wstawieniem? To wspaniale!

Moje pytanie brzmi: czy naprawdę muszę w 100% zrozumieć drzewa RB? Czuję się źle, pomijając rzeczy, nie do końca je rozumiejąc. Z góry dziękuję! (PS: nie ma tagu dla drzewa RB, właściwie nawet dla drzewa, tylko drzewo binarne, więc umieszczam tylko algorytmy)

Wydaje się, że utożsamiacie pomysł „rozumienia” z „umiejętnością pisania kodu bez patrzenia na książkę”. To są dwie różne rzeczy. Jeśli widzisz, jak obracanie węzłów drzewa zmienia drzewo w celu utrzymania równowagi, to rozumiesz. Możliwość natychmiastowego przywołania wszystkich przypadków, w których obowiązują rotacje, nie jest istotna.

Sama mogłabym prawdopodobnie odkryć rotację, gdybym miał długopis / papier / kilka godzin na zabawę. Ale z pewnością nie mogłem tego napisać bez namysłu. Gdybym rzeczywiście musiał napisać taki algorytm, sprawdziłbym go, aby upewnić się, że wszystkie szczegóły są prawidłowe. Oczywiście w prawie każdej sytuacji używałbym już napisanego kodu.

Wszystko to znajduje zastosowanie, gdy natrafisz na sytuację, która nie pasuje do żadnego z algorytmów. Nigdy nie będziesz musiał pisać własnej implementacji drzewa. Ale możesz znaleźć, powiedzmy, potrzebę spłaszczenia dziedziczności podwójnie powiązanych list. W takim przypadku zrozumienie podstawowej idei rotacji może być bardzo pomocne.

Jeśli w ogóle znasz się na programowaniu funkcjonalnym, możesz znaleźć dla nich takie podejście (Okasaki 1999):

http://www.eecs.usma.edu/webs/people/okasaki/jfp99redblack.pdf

Jeśli nie, przynajmniej weź serce z pierwszego zdania:

Wszyscy dowiadują się o zrównoważonych drzewach wyszukiwania binarnego na wstępnych zajęciach z informatyki, ale nawet zdenerwowani drżą na myśl o tym, że rzeczywiście zaimplementują taką bestię.

Nie musisz szczegółowo rozumieć rotacji. Ci powinni zrozumieć związek między drzewami Rb i 2-3-4 drzew (patrz Sedgewick). Wszystkie te szalone rotacje mają o wiele większy sens, kiedy myślisz o nich jak o 2-3-4 drzewach. Jeśli twój profesor nie nauczył drzew RB jako szczegółów implementacji dla 2-3-4 drzew, prawdopodobnie powinieneś przeczytać coś na 2-3-4 drzewach. (Leczenie Sedgewicka jest całkiem dobre; Wikipedia go nie ma.)

Mówiąc bardziej ogólnie, zrozumienie szczegółów implementacji działania algorytmu jest tylko czasami przydatne. Zrozumienie logiki działania algorytmu jest prawie zawsze przydatne. Możliwość samodzielnego wymyślenia algorytmu zwykle nie jest konieczna, chociaż im więcej algorytmów zrozumiesz, tym większa szansa, że ​​będziesz mieć.

Jeśli potrzebujesz „RB Trees By Heart” na badanie w przyszłym tygodniu, musisz ugryźć kulę i nauczyć się ich. W takim przypadku powinieneś ponownie rozważyć swoje metody uczenia się. Być może próba wyjaśnienia RB Tree koledze z klasy pomoże ci więcej niż kolejna noc samotnego pisania kodu.

Jeśli RB Drzewa są bazą dla twojego następnego kursu po wakacjach, pomiń je teraz (bez złych uczuć) i skoncentruj się na kursie tego semestru. Ale miej oczy szeroko otwarte na tematy, które mogą przygotować cię na drugą próbę RB Trees.

Jeśli naprawdę czujesz, że tak naprawdę nigdy ich nie potrzebujesz (por. Komentarz Anny Lear), pocałuj ich na pożegnanie bez żalu - nikt nie wie więcej niż kropla w morzu wiedzy (szkoda, że ​​nauczyciele często myślą, że ich kropla jest najbardziej ważny).

Kluczem do sukcesu w programowaniu jest nigdy się nie poddawać :

Dzisiaj jego drzewa RB jutro będzie czymś innym. Większa lekcja się nie poddaje .

Dla mnie to jedna z podstawowych zasad programowania, nie poddawanie się ...

Sugerowałbym, abyś nadal próbował , a gdy zawiedziesz, ZRÓB TO PONOWNIE .

„Aż dostaniesz, aż kliknie, aż uruchomi się”.

Ponieważ po pokonaniu gór niebo staje się czyste. Twój umysł zmienia się w zrozumieniu, jesteś tymczasowo wzniesiony (do następnej góry) . To tymczasowe podniesienie jest warte więcej niż wszystkie pieniądze na świecie ...

Najlepszym sposobem na zrozumienie tego jest wypróbowanie :

• Istnieją 3 lub 6 obrotów. Weź kawałek papieru i wypisz je jeden po drugim.
• Gdy go zdobędziesz, idź i zaimplementuj czerwone czarne drzewo. Jest ok, jeśli musisz sprawdzić kilka rzeczy.

Tak właśnie zrobiliśmy na studiach. Do badania musimy wyjaśnić, jak działała jego część.