Najczęściej zadawane pytania i odpowiedzi dotyczące drzewa binarnego [Dla nowicjuszy i doświadczonych]

Wstęp

Struktury danych są jednym z najbardziej podstawowych pojęć w programowaniu obiektowym. Mówiąc prosto, struktura danych to szczególny sposób organizowania danych w komputerze, aby można je było efektywnie przetwarzać. Istnieje kilka struktur danych, takich jak stosy, kolejki i drzewa, które mają swoje własne unikalne właściwości.

Drzewa pozwalają nam organizować dane w sposób hierarchiczny. Taka struktura danych bardzo różni się od liniowych struktur danych, takich jak połączone listy lub tablice. Drzewo składa się z węzłów, które przenoszą informacje.

Drzewo binarne to specjalny rodzaj drzewa, które może mieć maksymalnie dwoje dzieci. Oznacza to, że określony węzeł w drzewie binarnym nie może mieć dziecka, jednego dziecka lub dwojga dzieci, ale nie więcej. Drzewo binarne to ważna struktura danych, która umożliwia nam rozwiązywanie trudnych problemów i budowanie złożonych kodów.

Jeśli ubiegasz się o pracę jako programista Java lub inżynier oprogramowania, rozmowa kwalifikacyjna może zawierać kilka pytań dotyczących tej koncepcji. Często kandydatom trudno jest odpowiedzieć na pytania oparte na drzewach binarnych, drzewach wyszukiwania binarnego i powiązanych programach. W tym artykule przyjrzymy się niektórym z najczęściej zadawanych pytań podczas wywiadów związanych z drzewami binarnymi. Ten artykuł pomoże Ci lepiej zrozumieć koncepcję i przygotować Cię do zdobycia wymarzonej pracy!

Top Pytania i odpowiedzi dotyczące drzewa binarnego

Poniższa sekcja zawiera katalog pytań i ich oczekiwanych odpowiedzi w oparciu o koncepcję drzewa binarnego.

1) Co to jest węzeł liścia?

Każdy węzeł w drzewie binarnym lub drzewie, które nie ma żadnych dzieci, jest nazywany węzłem liścia.

2) Co to jest węzeł główny?

Pierwszy węzeł lub najwyższy węzeł w drzewie nazywany jest węzłem głównym.

3) Jak znaleźć najniższego wspólnego przodka (LCA) drzewa binarnego w Javie?

Rozważmy dwa węzły n1 i n2, które są częścią drzewa binarnego.

Najniższy wspólny przodek (LCA) n1 i n2 to wspólny przodek n1 i n2, który znajduje się najdalej od korzenia.

Możesz zastosować następującą metodę, aby znaleźć LCA.

1. a) Znajdź ścieżkę od węzła głównego do n1 i zapisz ją w tablicy.
2. b) Znajdź ścieżkę od węzła głównego do n2 i zapisz ją w tablicy.
3. c) Przemierz obie ścieżki, aż wartość w obu tablicach będzie taka sama.

4) Jak sprawdzić, czy dane drzewo binarne jest poddrzewem innego drzewa binarnego?

Rozważmy, że mamy drzewo binarne T. Teraz chcemy sprawdzić, czy drzewo binarne S jest poddrzewem T.

Aby to zrobić, najpierw spróbuj sprawdzić, czy znajdziesz węzeł w T, który jest również w S.

Po znalezieniu tego wspólnego węzła sprawdź, czy następujące węzły również są częścią S.

Jeśli tak, możemy śmiało powiedzieć, że S jest poddrzewem T.

Trzeba przeczytać: Pomysły i tematy projektów dotyczących struktury danych

5) Jak znaleźć odległość między dwoma węzłami w drzewie binarnym?

Rozważ dwa węzły n1 i n2, które są częścią drzewa binarnego.

Odległość między n1 i n2 jest równa minimalnej liczbie krawędzi, które trzeba pokonać, aby dotrzeć z jednego węzła do drugiego.

Należy zauważyć, że przemierzasz najkrótszą odległość między węzłami.

6) Co to jest drzewo wyszukiwania binarnego?

Drzewo wyszukiwania binarnego (BST) to specjalny rodzaj drzewa binarnego, w którym każdy węzeł wewnętrzny zawiera klucz. W przypadku drzewa wyszukiwania binarnego regułą jest:

1. a) Węzeł może mieć klucz, który jest większy niż wszystkie klucze w lewym poddrzewie węzła.
2. b) Węzeł może mieć klucz, który jest mniejszy niż wszystkie klucze w prawym poddrzewie węzła.

Tak więc, jeśli n1 jest węzłem, który ma klucz 8, to każdy węzeł w lewym poddrzewie n1 będzie zawierał klucze mniejsze niż 8, a każdy węzeł w prawym poddrzewie n1 będzie zawierał klucze większe niż 8.

7) Czym jest samozrównoważone drzewo?

Samobalansowane drzewa wyszukiwania binarnego automatycznie utrzymują swoją wysokość tak małą, jak to możliwe, gdy mają miejsce operacje takie jak wstawianie i usuwanie.

Aby drzewo BST było samozrównoważone, ważne jest, aby konsekwentnie przestrzegało zasad BST, tak aby lewe poddrzewo miało klucze o niższej wartości, podczas gdy prawe poddrzewo miało klucze o wysokiej wartości.

Odbywa się to za pomocą dwóch operacji:

– Lewy obrót

– Prawy obrót

8) Co to jest drzewo AVL?

Drzewo AVL nosi imię jego wynalazców: Adelson, Velski i Landis. Drzewo AVL to samobalansujące drzewo binarne, które sprawdza wysokość lewego i prawego poddrzewa i zapewnia, że ​​różnica nie jest większa niż 1. Ta różnica jest nazywana współczynnikiem równowagi

Zatem BalanceFactor = wysokość (Lewe poddrzewo) – wysokość (Prawe poddrzewo)

Jeśli współczynnik równowagi jest większy niż 1, drzewo jest równoważone za pomocą niektórych z następujących technik:

– Lewy obrót

– Prawy obrót

– Obrót lewo-prawo

– Obrót prawo-prawo

Przeczytaj także: Sortowanie w strukturze danych

9) Jak przekonwertować drzewo binarne na drzewo wyszukiwania binarnego w Javie?

Główna różnica między drzewem binarnym a drzewem wyszukiwania binarnego polega na tym, że BST następujące po lewym poddrzewie powinno mieć niższe wartości kluczy, a prawe poddrzewo powinno mieć regułę wyższych wartości kluczy. Można to zrobić za pomocą szeregu technik przechodzenia w następujący sposób:

1. Utwórz tymczasową tablicę, która przechowuje przechodzenie inorder w drzewie
2. Sortuj tablicę tymczasową. Tutaj możesz użyć dowolnego algorytmu sortowania.
3. Ponownie wykonaj przechodzenie w kolejności na drzewie.
4. Skopiuj elementy tablicy jeden po drugim do każdego węzła drzewa.

10) Jak usunąć węzeł z drzewa wyszukiwania binarnego w Javie?

Operacja usuwania drzewa BST może być trudna, ponieważ jego właściwości muszą zostać zachowane po operacji. Oto spojrzenie na wszystkie trzy możliwe przypadki:

1. Węzeł do usunięcia jest węzłem liścia.
   Po prostu usuń węzeł.
2. Węzeł do usunięcia ma jedno dziecko.

W takim przypadku skopiuj dziecko do węzła i usuń dziecko.

1. Węzeł do usunięcia ma dwoje dzieci.

W takim przypadku znajdź następcę inorder węzła. Następnie możesz skopiować jego zawartość do węzła i usunąć następcę inorder.

11) Jaka jest struktura danych drzewa czerwono-czarnego?

Drzewo czerwono-czarne to specjalny rodzaj samobalansującego drzewa, które ma następujące właściwości:

1. Każdy węzeł ma kolor czerwony lub czarny.
2. Korzeń jest zawsze czarny.
3. Czerwony węzeł nie może mieć czerwonego rodzica ani czerwonego dziecka.
4. Każda ścieżka od węzła głównego do węzła NULL ma taką samą liczbę czarnych węzłów.

Trzeba przeczytać: Pomysły i tematy projektów dotyczących struktury danych

12) Jak stwierdzić, że dwa drzewa są identyczne?

Dwa drzewa binarne są identyczne, jeśli mają te same dane i układ. Można to zrobić, przemierzając oba drzewa i porównując ich dane i układy.

Oto algorytm, który może nam to umożliwić:

1. Sprawdź dane węzła głównego ( tree1 data ==tree2 data)
2. Sprawdź rekurencyjnie lewe poddrzewo. wywołaj to samoTree( drzewo1-> lewe poddrzewo, drzewo2-> lewe poddrzewo)
3. Podobnie, sprawdź prawe poddrzewo
4. jeśli a,b,c są prawdziwe, zwraca 1

Zamówienie: rodzaje drzewa binarnego

Końcowe przemyślenia

W tym artykule omówiliśmy niektóre z najczęściej zadawanych pytań do wywiadów dotyczących drzewa wyszukiwania binarnego. Więcej informacji na temat struktur danych może pomóc w lepszym zrozumieniu logiki i programowania. Możesz spróbować spojrzeć na przykłady wymienione w tym artykule i poćwiczyć, zmieniając wartości, aby zbudować swoje podstawy. Przy odrobinie praktyki będziesz w doskonałej pozycji, aby złamać rozmowę kwalifikacyjną.

Jeśli jesteś zainteresowany nauką o danych, sprawdź program IIIT-B i upGrad Executive PG w dziedzinie 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 ekspertami z branży, 1 -on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.