Drzewa, czerwono-czarne drzewa

"Cześć, Amigo!"

"Cześć Rysiu!"

„Znalazłem tam moje stare notatki i przygotowałem dla ciebie ciekawy materiał. Myślę, że będziesz zainteresowany”.

„Posłuchajmy. Zawsze znajdziesz coś ciekawego, co później okaże się bardzo przydatne”.

„OK. Dziś chcę wam opowiedzieć o drzewach , więc zacznę od wykresów ”.

" Wykres to układ punktów i linii, które je łączą. Punkty nazywane są wierzchołkami grafu, a linie krawędziami grafu. Na przykład:"

„Wykres jest bardzo wygodny w użyciu jako model matematyczny dla różnych procesów i zadań w świecie rzeczywistym. Wymyślono wiele różnych zadań i algorytmów dla wykresów, więc są one dość często używane”.

„Załóżmy na przykład, że wierzchołki to miasta, a krawędzie to drogi. Wtedy poszukiwanie najkrótszej drogi między miastami wygląda następująco: «Dając graf, znajdź najkrótszą ścieżkę między dwoma wierzchołkami»” .

„Jednak ścieżka z punktu A do B nie zawsze jest taka sama, jak ścieżka z punktu B do punktu A. Dlatego czasami preferowane są dwie różne linie. W tym celu linie (krawędzie wykresu) są zastępowane strzałkami. W innymi słowy, wykres może mieć dwie strzałki: jedną od A do B, a drugą od B do A”.

„Jeśli wykres używa strzałek, to nazywa się go grafem skierowanym ; jeśli ma tylko linie, nazywa się to grafem nieskierowanym ”.

„Każdy wierzchołek może mieć własną liczbę krawędzi. Wierzchołek może również nie mieć żadnych krawędzi. I odwrotnie, wierzchołek może być połączony krawędziami z każdym innym wierzchołkiem.  Jeśli każda para wierzchołków w grafie jest połączona krawędzią, to nazywa się to pełnym wykresem. ”

„Jeśli możesz użyć krawędzi, aby dotrzeć do każdego wierzchołka grafu, nazywa się to grafem spójnym . Graf, który ma trzy oddzielne wierzchołki i nie ma krawędzi, nadal jest grafem, ale nazywamy go grafem rozłączonym ”.

„Aby utworzyć spójny graf z N wierzchołków, potrzebujesz co najmniej N-1 krawędzi. Ten typ wykresu nazywa się drzewem”.

„Co więcej, zwykle jeden wierzchołek jest wybierany jako korzeń drzewa , a pozostałe deklarowane są jako gałęzie. Gałęzie drzew, które nie mają własnych gałęzi, nazywane są liśćmi . Na przykład:”

„Jeśli każdy element drzewa ma dwoje dzieci, nazywa się to drzewem binarnym . Innymi słowy, może istnieć 0 lub 2 gałęzie. Możesz zobaczyć drzewo binarne w prawym górnym rogu”.

„ Drzewo nazywamy kompletnym drzewem binarnym , gdy każda gałąź ma 2 dzieci, a wszystkie liście (wierzchołki bez dzieci) znajdują się w tym samym rzędzie”.

"Na przykład:"

„Dlaczego te drzewa są potrzebne?”

„Och, drzewa są używane w wielu miejscach. Ogólnie rzecz biorąc, drzewa binarne to posortowane dane strukturalne”.

"Co to jest?"

„Tak, to bardzo proste. Przechowujemy pewną wartość w każdym wierzchołku. A każdy element podlega regule: wartość przechowywana w prawym dziecku musi być większa niż wartość przechowywana w wierzchołku, a wartość przechowywana w lewym dziecku musi być mniejsza niż wartość przechowywana w wierzchołku.  Takie uporządkowanie umożliwia szybkie znalezienie potrzebnych elementów drzewa”.

– Możesz wyjaśnić, co to znaczy?

„Elementy drzewa są zwykle sortowane przez dodanie. Załóżmy, że mamy 7 elementów: 13, 5, 4, 16, 8, 11, 10”

„Oto jak elementy są dodawane do drzewa.”

„Jeśli szukamy numeru 7 w tym drzewie, to tak będzie przebiegać wyszukiwanie”

"0) Zacznij od korzenia."

„1a) Czy 7 równa się 13? Nie”

„1b) Czy 7 jest większe niż 13? Nie, więc przechodzimy do lewego poddrzewa”.

„2a) Czy 7 równa się 5? Nie”.

„2b) Czy 7 jest większe niż 5? Tak, więc przechodzimy do prawego poddrzewa”.

„3a) Czy 7 równa się 8? Nie”

„3b) Czy 7 jest większe niż 8? Nie, więc przechodzimy do lewego poddrzewa”.

„4a) Nie ma lewego poddrzewa, co oznacza, że ​​w drzewie nie ma cyfry 7”.

„Ach. Innymi słowy, musimy tylko sprawdzić wierzchołki na ścieżce od korzenia do potencjalnej lokalizacji żądanej liczby. Tak, to naprawdę szybko”.

„Co więcej, jeśli drzewo jest zrównoważone, wystarczy przejść przez około 20 wierzchołków, aby przeszukać milion elementów”.

„Zgadzam się – to nie jest zbyt wiele”.

„Co masz na myśli, mówiąc o zrównoważonym drzewie?”

„Drzewo, które nie jest zniekształcone, tj. nie ma długich gałęzi. Na przykład, gdyby elementy były już posortowane podczas budowania drzewa, stworzylibyśmy bardzo długie drzewo składające się z jednej gałęzi ” .

"Hmm. Masz rację. Więc co robimy?"

„Jak zapewne już się domyśliłeś, najbardziej wydajne drzewo ma gałęzie mniej więcej tej samej długości. Wtedy każde porównanie odrzuca największą część pozostałego poddrzewa”.

„Więc musimy odbudować drzewo?”

„Tak. To musi być «zbalansowane» — jak najbardziej zbliżone do pełnego drzewa binarnego”.

„Aby rozwiązać ten problem, wynaleziono samobalansujące się drzewa.  Jeśli drzewo zostanie zniekształcone po dodaniu elementu, to zmienia nieco kolejność elementów, aby wszystko było w porządku.  Oto przykład równoważenia:”

„Niektóre z tych drzew są znane jako drzewa czerwono -czarne ”.

„Dlaczego nazywają się czerwono-czarnymi?”

„Ich wynalazca narysował wszystkie wierzchołki dwoma kolorami. Jeden kolor był czerwony, a drugi czarny. Różne wierzchołki podlegają różnym zasadom. To stanowi całą podstawę procedury równoważenia”.

"Na przykład:"

– Więc jakie są te zasady?

„1) Czerwony wierzchołek nie może być dzieckiem czerwonego wierzchołka”.

„2) Głębia czerni każdego liścia jest taka sama (głębokość czerni odnosi się do liczby czarnych wierzchołków na ścieżce od korzenia).”

„3) Korzeń drzewa jest czarny”.

„Nie będę wyjaśniał, jak to działa – twoja głowa prawdopodobnie już eksploduje”.

„Tak. Mój procesor wydziela trochę dymu”.

„Oto link dla ciebie. Jeśli chcesz, możesz przeczytać więcej na ten temat tutaj”.

Link do dodatkowych materiałów

– A teraz idź odpocząć.