Drzewo binarne a drzewo wyszukiwania binarnego: różnica między drzewem binarnym a drzewem wyszukiwania binarnego

Wstęp

Sortowanie to proces porządkowania danych w systematycznej kolejności, aby można je było efektywniej analizować. Proces identyfikacji konkretnego rekordu nazywa się wyszukiwaniem. Jeśli dane są odpowiednio posortowane w określonej kolejności, wyszukiwanie staje się łatwym i wydajnym zadaniem. Ten artykuł dotyczy jednej z najważniejszych nieliniowych struktur danych, czyli drzew.

Drzewa służą przede wszystkim do reprezentowania danych poprzez pokazanie hierarchicznej relacji między elementami. Na przykład spis treści, drzewo genealogiczne. Technicznie, drzewo może być zdefiniowane jako skończony zbiór „T” jednego lub więcej węzłów, tak że węzeł jest przypisany jako korzeń drzewa, a pozostałe węzły są podzielone na n>=0 zbiory rozłączne T1, T2, T3, T4 …. Tn i są wywoływane jako poddrzewa lub dzieci tego węzła głównego.

Co to jest drzewo binarne?

Drzewo binarne to nieliniowa struktura danych, w której węzeł może mieć 0, 1 lub 2 węzły. Każdy węzeł w drzewie binarnym jest określany jako węzeł nadrzędny lub jako węzeł podrzędny. Najwyższy węzeł drzewa binarnego jest określany jako węzeł główny. Każdy węzeł nadrzędny może mieć maksymalnie 2 węzły potomne, które są lewym węzłem potomnym i prawym węzłem potomnym.

Węzeł w drzewie binarnym ma trzy pola:

1. Element danych — przechowuje wartość danych, która ma być przechowywana przez węzeł.
2. Wskaźnik do lewego dziecka — przechowuje odniesienie (lub adres) do lewego węzła podrzędnego.
3. Wskaźnik do prawego dziecka — przechowuje odwołanie do prawego węzła podrzędnego.

W ten sposób kilka węzłów jest połączonych razem, aby zbudować drzewo binarne.

Drzewo binarne może być reprezentowane jako:

Źródło

Z powyższego rysunku węzeł główny 2 ma dwoje dzieci (lub węzły podrzędne), 7 i 5. 7 jest określany jako węzeł lewy-podrzędny, a 5 jest nazywany węzłem prawym podrzędnym. W ten sposób każdy z węzłów podrzędnych działa jako węzeł nadrzędny dla kilku innych węzłów i razem reprezentuje drzewo binarne.

Sprawdź: Rodzaje drzewa binarnego

Terminologie używane w drzewie binarnym

Węzeł : podstawowa reprezentacja punktu końcowego w drzewie.

Węzeł główny : najwyższy węzeł drzewa binarnego.

Węzeł nadrzędny : jeśli węzeł jest połączony z innym węzłem przez krawędzie, nazywany jest węzłem nadrzędnym. W drzewie binarnym węzeł nadrzędny może mieć maksymalnie 2 węzły podrzędne.

Węzeł podrzędny : Jeśli węzeł ma poprzednika, jest nazywany węzłem podrzędnym.

Węzeł liścia : węzeł, który nie ma żadnego węzła podrzędnego, jest wywoływany jako węzeł liścia.

Głębokość węzła : jest to odległość od węzła głównego do tego konkretnego węzła, którego głębokość ma być mierzona.

Wysokość drzewa : jest to najdłuższa odległość od węzła korzenia do węzła liścia.

Oto kilka podstawowych terminologii drzewa binarnego. Mając to podstawowe zrozumienie drzewa binarnego, przejdźmy do rozwoju drzewa binarnego znanego jako drzewo wyszukiwania binarnego.

Przeczytaj także: Algorytm wyszukiwania binarnego: funkcja, korzyści, złożoność czasu i przestrzeni

Co to jest drzewo wyszukiwania binarnego

Jak sama nazwa wskazuje, drzewo wyszukiwania binarnego lub BST to drzewo używane do sortowania, pobierania i wyszukiwania danych. Jest to również rodzaj nieliniowej struktury danych, w której węzły są ułożone w określonej kolejności. W związku z tym jest również nazywany „ Uporządkowanym drzewem binarnym ”. Posiada następujące właściwości:

• Lewe poddrzewo węzła ma węzły, które są tylko mniejsze niż klucz tego węzła.
• Prawe poddrzewo węzła ma węzły, które są tylko większe niż klucz tego węzła.
• Każdy węzeł ma odrębne klucze, a duplikaty nie są dozwolone w drzewie wyszukiwania binarnego.
• Lewe i prawe poddrzewo również musi być drzewem wyszukiwania binarnego.

Zwizualizujmy tę koncepcję, aby uzyskać jasne zrozumienie drzew wyszukiwania binarnego.

Źródło

Na powyższym rysunku widzimy, że wartość węzła głównego wynosi 8. Po dalszej analizie można zauważyć, że wszystkie wartości w lewym poddrzewie są mniejsze niż wartość węzła głównego, a wszystkie wartości w prawym poddrzewie mają wartości, które są większe niż węzeł główny. Ponadto należy zauważyć, że każda wartość w drzewie wyszukiwania binarnego jest unikalna i nie ma duplikatów. W ten sposób weryfikowane są właściwości drzewa wyszukiwania binarnego podane powyżej.

W jeszcze innym przykładzie widzimy, że chociaż lewe i prawe poddrzewa są binarnymi drzewami wyszukiwania z unikalnymi wartościami w całym drzewie. Wartość w węźle liścia w lewym poddrzewie wynosi 12, czyli jest większa niż wartość węzła głównego, która wynosi 12. Zatem nie spełnia to właściwości BST, a zatem nie jest to drzewo wyszukiwania binarnego.

Operacja wyszukiwania w BST –

Rozważ drzewo wyszukiwania binarnego z wartościami podanymi poniżej. Pozwól nam zrozumieć, w jaki sposób wykonywana jest operacja wyszukiwania, aby uzyskać 9 z drzewa wyszukiwania binarnego.

Źródło

Aby przeprowadzić wyszukiwanie binarne, najpierw ułożymy wszystkie liczby całkowite w posortowaną tablicę. Nazywa się to przestrzenią wyszukiwania. Ta przestrzeń poszukiwań powinna składać się z dwóch wskaźników, nazywanych wskaźnikami początkowym i końcowym. Tablica powyższego drzewa wyszukiwania binarnego jest reprezentowana jako:

Pierwszym krokiem jest obliczenie środkowej wartości tablicy i porównanie jej z wartością, która ma być przeszukana, w naszym przypadku 9. Odbywa się to poprzez obliczenie n/2, gdzie n jest całkowitą liczbą elementów w tablicy (BST), a wynosi 6. Zatem trzeci element jest elementem środkowym, czyli 5.

Teraz, gdy środkowy element jest porównywany z 9 i ponieważ nie jest równy (większy), operacja wyszukiwania zostanie wykonana na prawej tablicy. W ten sposób operacja wyszukiwania zostaje skrócona do połowy, jak pokazano poniżej:

W kolejnym kroku obliczany jest środkowy element i okazuje się, że ma wartość 9, co odpowiada naszemu wyszukiwanemu elementowi.

Drzewo binarne a drzewo wyszukiwania binarnego –

Teraz, gdy mamy podstawową wiedzę na temat zarówno drzewa binarnego, jak i drzewa wyszukiwania binarnego, szybko podsumujmy niektóre różnice między nimi.

Wniosek

Stąd wnioskujemy, że chociaż zarówno drzewo binarne, jak i drzewo wyszukiwania binarnego mają wspólną strukturę hierarchiczną z kolekcją węzłów, mają kilka różnic w ich zastosowaniu. Drzewo binarne to podstawowa struktura z prostą zasadą, że żaden rodzic nie może mieć więcej niż dwoje dzieci, podczas gdy drzewo wyszukiwania binarnego jest wariantem drzewa binarnego z zachowaniem określonej kolejności, w jakiej powinny być zorganizowane węzły.

Jeśli chcesz dowiedzieć się więcej o drzewie binarnym a drzewie wyszukiwania binarnego, sprawdź IIIT-B i upGrad's PG Diploma in Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z przemysłem eksperci, indywidualni z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.

Ucz się online kursów nauki o danych z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.