[Powered by Google Translate] Jak można reprezentować wszystkich członków rodziny w komputerze? Możemy po prostu skorzystać z listy, ale istnieje wyraźna hierarchia tutaj. 

Załóżmy, że zaczynamy z prababki, Alice. Ona ma 2 synów, Bob a twój dziadek, Charlie. Charlie ma 3 dzieci, twój wujek, Dave, twoja ciocia, Eve, i ojciec, Fred. Jesteś jedynakiem Freda. 

Dlaczego miałby organizowanie członków rodziny w ten sposób lepiej niż prosta reprezentacji listy? Jednym z powodów tego jest fakt, że strukturę hierarchiczną, zwaną "drzewo", zawiera więcej informacji niż prosta lista. Znamy rodzinnych relacji między wszystkimi tylko badając drzewo. Ponadto, można przyspieszyć look-up time ogromnie, jeśli dane drzewo jest posortowana. 

Nie możemy wykorzystać, że tutaj, ale zobaczymy przykład tego wkrótce. Każdy jest reprezentowany przez element drzewa. Węzły mogą mieć węzły oraz węzeł nadrzędny. Są to warunki techniczne, nawet przy użyciu drzew rzeczy oprócz rodzin. Węzeł Alicji ma 2 dzieci i nie ma rodziców, natomiast węzeł Charlie ma 3 dzieci i 1 rodzica. 

Węzeł liścia jest, że nie ma żadnych dzieci na zewnętrznej krawędzi drzewa. Najwyższy węzeł drzewa, węzeł root, nie ma rodzica. 

Drzewo binarne to szczególny rodzaj drzewa, , w którym każdy węzeł ma co najwyżej 2 dzieci. Oto struktura węzła z drzewa binarnego w C. Każdy węzeł ma pewne dane związane i 2 wskaźniki do innych węzłów. 

W naszym drzewie genealogicznym, Związane było dane każdej osoby imię. Tutaj jest to int, choć to może być cokolwiek. Jak się okazuje, Drzewo binarne nie byłoby dobre przedstawienie dla rodziny, ponieważ ludzie często mają więcej niż 2 dzieci. 

Binary search tree Jest to specjalny, zamawianych typ drzewa binarnego która pozwala nam spojrzeć na wartości szybko. Można zauważyć, że każdy węzeł poniżej korzenia drzewa jest źródłem innego drzewa, zwany poddrzewa. Tutaj, korzeniem drzewa jest 6, i jej dziecko, 2, jest korzeniem poddrzewa. 

W binarnym drzewie poszukiwań wszystkie wartości węzła rację poddrzewa są większe niż węzła wartości. Tutaj: 6. Cóż, wartości z lewego poddrzewa węzła mniej niż węzła wartości. Jeżeli musimy obsługiwać zduplikowane wartości, możemy zmienić jeden z tych, do luźnej nierówności czyli identyczne wartości może spaść albo na lewo lub prawo, tak długo, jak są zgodne o nim całym. To drzewo jest drzewo binarne wyszukiwanie ponieważ wynika te zasady. 

Jest to, jak to będzie wyglądać, jeśli okazało wszystkie węzły do ​​struktur C. Zauważ, że jeśli dziecko nie ma, wskaźnik jest null. W jaki sposób sprawdzić, czy 7 jest w drzewie? Zaczynamy od korzenia. Siedem jest większa niż 6, jeśli jest to w drzewie, musi być w prawo. Następnie, nie jest mniejszy niż 8, więc należy pozostawić. Tutaj nie znaleziono 7. Teraz będziemy sprawdzać 5. Pięć jest mniejsza niż 6, tak więc musi być w lewo. Pięć jest większy niż 2, więc musi być w porządku, i to jest również większa niż 4, więc to musi być jeszcze raz w prawo. Jednakże, nie ma na dziecko. Wskaźnik jest null. Oznacza to, że nie jest w 5 naszego drzewa. 

Możemy przeszukiwać drzewo binarne z następującego kodu: Na każdym węźle, możemy sprawdzić, czy udało nam się znaleźć wartość szukamy. Jeśli nie znajdziemy, możemy ustalić, czy powinien on być na prawo lub w lewo i sprawdź, poddrzewa. Pętla ta będzie nadal w dół drzewa dopóki nie ma węzeł dziecko na lewo lub prawo. 

Pamiętaj, że 5 nie był w drzewie. Jak możemy włożyć? Proces wygląda podobnie do wyszukiwania. Mamy iteracyjne w dół drzewa, począwszy od 6, lewej do 2, prawo do 4, i znowu w prawo, a dzieci nie 4 po tej stronie. Będzie nową pozycję 5, i rozpocznie się bez dzieci. 

Jak szybko to operacje na drzewa binarnego wyszukiwania? Pamiętaj, że Bigohnotation ma zapewnić ograniczenie górne. W najgorszym przypadku, nasze drzewo może być po prostu połączonej listy co oznacza, że ​​wstawiania, usuwania i wyszukiwania może czasu jest proporcjonalny do liczby węzłów w drzewie. To O (n). 

Na przykład poniższe nie jest ważne drzewo wyszukiwania binarnego. Jednakże, jeśli staramy się znaleźć 9, musimy przemierzać każdy węzeł. Nie jest lepsza niż połączonej listy. Idealnie, chcielibyśmy każdy węzeł z naszego drzewa wyszukiwania binarnego mieć 2 dzieci. W ten sposób, wstawiania, usuwania i wyszukiwania weźmie, co gorsza, O (log n) czasu. Drzewo z przed może być bardziej zrównoważony, tak. Teraz, patrząc na jakąkolwiek wartość trwa najwyżej 3 kroki. To drzewo jest zrównoważone, co oznacza, że ​​ma minimalne jest głębokość w stosunku do liczby węzłów. 

Szukasz wartości w zrównoważonym drzewie wyszukiwania binarnego jest podobny do binarnego wyszukiwania w posortowanej tablicy. W rzeczywistości, jeśli nie musimy wstawić lub usunąć elementy, zachowują się dokładnie tak samo. Jednak struktura drzewa jest lepiej do wstawienia i usunięcia obsługi 

Nazywam się Bannus Van der Kloot. To CS50.