Kluczowa różnica – drzewo binarne a drzewo wyszukiwania binarnego
Struktura danych to systematyczny sposób organizowania danych w celu efektywnego ich wykorzystania. Porządkowanie danych za pomocą struktury danych powinno skrócić czas działania lub czas wykonania. Ponadto struktura danych powinna wymagać minimalnej ilości pamięci. Czasami dane mogą być ułożone w strukturę drzewa. Drzewo reprezentuje węzeł połączony krawędziami. Najwyższym węzłem jest korzeń. Każdy węzeł może mieć maksymalnie dwa węzły. Są one znane jako węzły podrzędne. Węzeł na lewo od węzła nadrzędnego jest lewym węzłem podrzędnym, podczas gdy węzeł na prawo od węzła nadrzędnego jest węzłem prawym. Drzewo binarne i drzewo wyszukiwania binarnego to dwie drzewiaste struktury danych. Drzewo binarne to rodzaj struktury danych, w której każdy węzeł nadrzędny może mieć co najwyżej dwa węzły podrzędne. Drzewo wyszukiwania binarnego to drzewo binarne, w którym lewe dziecko zawiera tylko węzły o wartościach mniejszych lub równych węzłowi nadrzędnemu, a prawe dziecko zawiera tylko węzły o wartościach większych niż węzeł nadrzędny. To jest kluczowa różnica. W przeciwieństwie do struktur danych, takich jak tablice, drzewo binarne i drzewo wyszukiwania binarnego nie mają górnego limitu przechowywania danych.
Co to jest drzewo binarne?
Podczas aranżowania danych w strukturze drzewa węzeł na szczycie drzewa nazywany jest węzłem głównym. Dla całego drzewa może być tylko jeden korzeń. Każdy węzeł z wyjątkiem węzła głównego ma jedną krawędź w górę do węzła. Nazywa się to węzłem nadrzędnym. Węzeł poniżej kodu rodzica nazywa się jego węzłem potomnym. Każdy węzeł nadrzędny może mieć maksymalnie dwa węzły podrzędne. Są one określane jako lewy węzeł podrzędny i prawy węzeł podrzędny. Węzeł bez żadnego węzła podrzędnego nazywany jest węzłem liścia. Nie ma konkretnego sposobu na uporządkowanie danych w drzewie binarnym. Istnieje ścieżka od węzła głównego do każdego węzła.
Rysunek 01: Przykład drzewa binarnego
Powyżej jest przykładem drzewa binarnego. Elementem 2, znajdującym się na szczycie drzewa, jest korzeń. Każdy węzeł ma maksymalnie dwa węzły. Jeśli drzewo zawiera jakiekolwiek pętle lub jeśli jeden węzeł zawiera więcej niż dwa węzły, nie można go sklasyfikować jako drzewo binarne. Aby przejść z jednego węzła do drugiego, zawsze istnieje jedna ścieżka. Węzły potomne węzła głównego 2 to 7 i 5. Możliwe jest również, że węzeł nie będzie miał żadnych węzłów. Ale żaden węzeł nie może mieć więcej niż dwóch węzłów. Prawy element korzenia to 5. Ten element 5 jest węzłem nadrzędnym dla węzła podrzędnego 9. Węzły 4 i 11 nie mają elementów podrzędnych. Dlatego są to węzły liści.
Drzewo binarne służy do przechowywania danych w porządku hierarchicznym. Jest podobny do struktury plików komputera. Struktura danych, taka jak tablica, może przechowywać określoną ilość danych. Ale w drzewie binarnym nie ma górnego limitu liczby węzłów.
Co to jest drzewo wyszukiwania binarnego?
Drzewo wyszukiwania binarnego to struktura danych w postaci drzewa binarnego. Podobnie jak drzewo binarne, drzewo wyszukiwania binarnego również może mieć dwa węzły. Każdy węzeł z wyjątkiem węzła głównego ma jedną krawędź w górę do węzła. Nazywa się to węzłem nadrzędnym. Węzeł poniżej danego połączony krawędzią w dół nazywa się jego węzłem potomnym. Węzeł bez żadnego węzła podrzędnego nazywany jest węzłem liścia. Każdy węzeł nadrzędny może mieć maksymalnie dwa węzły. Istnieją węzły potomne odwołujące się do lewego węzła potomnego i prawego węzła potomnego. Najwyższy element nazywa się węzłem głównym. Lewy element potomny zawiera tylko węzły o wartościach mniejszych lub równych węzłowi nadrzędnemu. Prawe dziecko zawiera tylko węzły o wartościach większych lub równych węzłowi nadrzędnemu.
Rysunek 02: Przykład drzewa wyszukiwania binarnego
Element 8 jest najwyższym elementem. Dlatego jest to węzeł główny. Jeśli 3 jest węzłem nadrzędnym, to 1 i 6 są węzłami podrzędnymi. 1 to lewy węzeł podrzędny, a 6 to prawy węzeł podrzędny. Lewy element potomny zawiera wartości mniejsze lub równe węzłowi nadrzędnemu. Gdy 3 jest węzłem nadrzędnym, lewa strona powinna mieć element, który jest mniejszy lub równy 3. W tym przykładzie jest to 1. Prawe dziecko zawiera tylko węzły o wartościach większych niż węzeł nadrzędny. Gdy 3 jest węzłem nadrzędnym, prawy węzeł podrzędny powinien mieć wyższą wartość niż 3. W tym przykładzie jest to 6. Podobnie, istnieje pewna kolejność rozmieszczania każdego elementu danych w drzewie wyszukiwania binarnego. Jest to struktura danych zapewniająca wydajny sposób sortowania, pobierania i wyszukiwania danych.
Jakie są podobieństwa między drzewem binarnym a drzewem wyszukiwania binarnego?
- Zarówno drzewo binarne, jak i drzewo wyszukiwania binarnego to hierarchiczne struktury danych.
- Zarówno drzewo binarne, jak i drzewo wyszukiwania binarnego mają korzenie.
- Zarówno drzewo binarne, jak i drzewo wyszukiwania binarnego mogą mieć maksymalnie dwa węzły podrzędne.
Jaka jest różnica między drzewem binarnym a drzewem wyszukiwania binarnego?
Drzewo binarne a drzewo wyszukiwania binarnego |
|
| Drzewo binarne to rodzaj struktury danych, w której każdy węzeł nadrzędny może mieć maksymalnie dwa węzły podrzędne. | Drzewo wyszukiwania binarnego jest drzewem binarnym, w którym lewe dziecko zawiera tylko węzły z wartościami mniejszymi lub równymi węzłowi nadrzędnemu, a prawe dziecko zawiera tylko węzły o wartościach większych niż węzeł rodzicielski. |
| Zamówienie porządkowania danych | |
| Drzewo binarne nie ma określonej kolejności rozmieszczania elementów danych. | Drzewo wyszukiwania binarnego ma określoną kolejność rozmieszczania elementów danych. |
| Zastosowanie | |
| Drzewo binarne służy do wydajnego wyszukiwania danych i informacji w strukturze drzewa. | Drzewo wyszukiwania binarnego służy do wstawiania, usuwania i wyszukiwania danych. |
Podsumowanie – drzewo binarne a drzewo wyszukiwania binarnego
Struktura danych to sposób organizowania danych. Czasami dane mogą być ułożone w strukturę drzewa. Dwa z nich to drzewo binarne i drzewo wyszukiwania binarnego. W tym artykule omówiono różnicę między drzewem binarnym a drzewem wyszukiwania binarnego. Drzewo binarne to rodzaj struktury danych, w której każdy węzeł nadrzędny może mieć co najwyżej dwa węzły podrzędne. Drzewo wyszukiwania binarnego jest drzewem binarnym, w którym lewe dziecko zawiera tylko węzły o wartościach mniejszych lub równych węzłowi nadrzędnemu, a prawe dziecko zawiera tylko węzły o wartościach większych niż węzeł nadrzędny.
Pobierz plik PDF drzewa binarnego a drzewo wyszukiwania binarnego
Możesz pobrać wersję PDF tego artykułu i używać jej do celów offline zgodnie z notatką cytowania. Proszę pobrać wersję PDF tutaj: Różnica między drzewem binarnym a drzewem wyszukiwania binarnego
