Spisu treści:
- Definicja - Co oznacza samo-równoważące się drzewo wyszukiwania binarnego?
- Techopedia wyjaśnia samowyrównujące się drzewo wyszukiwania binarnego
Definicja - Co oznacza samo-równoważące się drzewo wyszukiwania binarnego?
Samowyważące się drzewo wyszukiwania binarnego jest rodzajem struktury danych, która dostosowuje się, aby zapewnić spójny poziom dostępu do węzła. W binarnym drzewie wyszukiwania binarnego połączenia od górnego węzła do dodatkowych węzłów są sortowane i ponownie dostosowywane, aby drzewo było równe, a linie trajektorii wyszukiwania dla każdego węzła końcowego są równe pod względem długości.
Samowyrównujące się drzewo wyszukiwania binarnego jest również znane jako drzewo zrównoważone lub drzewo wyszukiwania binarnego o zrównoważonej wysokości.
Techopedia wyjaśnia samowyrównujące się drzewo wyszukiwania binarnego
Drzewo wyszukiwania binarnego ogólnie zapewnia strukturę danych z jednym węzłem u góry i jednym lub dwoma węzłami podłączonymi do niego na każdym kolejnym poziomie. Drzewa wyszukiwania binarnego obsługują trzy operacje - operatorzy mogą wstawiać komponenty, usuwać komponenty lub wyszukiwać pewną liczbę lub inną zawartość węzła. Jedną z zalet binarnych drzew wyszukiwania jest to, że system może sortować, ignorując połowę drzewa na każdym poziomie, co prowadzi do bardziej wydajnych obciążeń wyszukiwania.
Pozytywnym aspektem samowyważącego się drzewa binarnego wyszukiwania jest to, że dostęp do węzła jest równy - na przykład zamiast konieczności przejścia pięciu kroków po jednej stronie drzewa lub trzech kroków po drugiej stronie drzewa z powodu samego siebie - dostosowana struktura węzła, wyszukiwanie przejdzie tylko określoną liczbę kroków (n) do dowolnego danego węzła końcowego. Osiąga się to poprzez usunięcie poszczególnych połączeń węzłów i zastąpienie ich połączeniami binarnymi, aby skrócić poszczególne kończyny drzewa.
Wadą samoregulującego wyszukiwania binarnego trzy jest to, że działa ono tylko wtedy, gdy połączenia węzłów są „niezależne od poziomu” - innymi słowy, jeśli pojedynczy węzeł można ponownie wyregulować do poprzedniego poziomu w celu skrócenia gałęzi drzewa . Na przykład, jeśli samo-równoważące się drzewo wyszukiwania binarnego składa się z podanej liczby u góry i dwóch kolejnych liczb po obu stronach, a istnieje łańcuch trzech dodatkowych liczb z połączeniami z pojedynczym węzłem, dostosowanie drzewa piąty węzeł wraz z trzecim węzłem zamiast czwartego węzła, tak że trzeci węzeł ma dwa węzły łączące zamiast jednego. Jeśli jednak struktura danych musi zidentyfikować określoną zawartość węzła jako powiązaną w konkretnej relacji rodzic / dziecko, dostosowanie tych węzłów do dopasowania do struktury drzewa nie zadziała.
