Czy drzewa binarne służą do określonego celu przechowywania danych hierarchicznych? Jakie jest ich kanoniczne zastosowanie?

12

Rozumiem strukturę drzew binarnych i sposób ich przechodzenia. Jednak mam problemy z realizacją ich rzeczywistych zastosowań, celów w programach i programowaniu. Kiedy myślę o przykładach danych hierarchicznych z „prawdziwego życia”, prawie na pewno mają więcej niż 2 dzieci. Na przykład w drzewie genealogicznym matka często może mieć więcej niż dwoje dzieci.

Czy „drzewa binarne” są naprawdę użyteczne tylko do przechowywania danych powiązanych liniowo ze względu na szybszy czas przetwarzania tablic i list? Alternatywnie, czy służą one konkretnemu celowi w przechowywaniu danych hierarchicznych? Jeśli tak, jakie są przykłady zastosowania drzew binarnych. Jakie dane powodują, że węzeł ma najwyżej 2 dzieci?

data-structures binary-tree sw123456
źródło
Myślę, że głównym zastosowaniem drzewa binarnego jest porządkowanie danych. https://en.wikipedia.org/wiki/Binary_search_tree
Mandrill

Odpowiedzi:

25

Nie, drzewa binarne nie służą do przechowywania danych hierarchicznych w sensie, o którym myślisz. Podstawowym przypadkiem użycia dla drzew n-ary, gdzie njest stała liczba, jest możliwość szybkiego wyszukiwania , a nie hierarchia semantyczna.

Zapamiętaj starą grę, w której jedna osoba myśli o liczbie od 1 do 100, a druga musi zgadywać ją w jak najmniejszej liczbie domysłów, a jeśli pomylisz się, osoba myśląca o liczbie musi powiedzieć ci, czy ty też jesteś zbyt wysoki czy zbyt niski? Po pewnym czasie robi się nudno, ponieważ szybko zdajesz sobie sprawę, że zawsze powinieneś zacząć od 50, a następnie przejść do 25 lub 75 i dalej dzielić zakres do przeszukiwania na pół przy każdej nowej zgadywance, a ostatecznie możesz odgadnąć dowolną liczbę gwarantowane co najwyżej 7 domysłów.

Może to nie być fajna gra, ale ta właściwość sprawia, że ​​drzewa binarne (i inne n-ary) są użyteczne: możesz ich użyć do wyszukiwania bardzo dużego zestawu danych w bardzo krótkim czasie.

Mason Wheeler
źródło
Doskonała odpowiedź, dziękuję bardzo. Więc drzewa binarne są tak naprawdę kolejną strukturą do przechowywania danych, tak jak w tablicy lub na liście, ale z dodatkową zaletą szybkiego wyszukiwania?
sw123456
1
@ sw123456: Zgadza się. Jak w przypadku każdej inżynierii, ma ona kompromisy, (wykorzystuje więcej - i bardziej pofragmentowaną - pamięć niż tablicę z taką samą liczbą elementów, dostęp O (n) do elementu # n zestawu danych zamiast O (1) dostęp itp.), ale szybkie wyszukiwanie jest zdecydowanie główną zaletą drzew binarnych.
Mason Wheeler
@ sw123456 Cieszę się, że mogę to wyjaśnić :)
Mason Wheeler
3
Dostęp do elementów ma wartość O (log (n)), gdy drzewo jest zrównoważone. O (n) będzie najgorszym przypadkiem, gdy zostanie zdegenerowany (większość węzłów ma tylko jeden nawias).
Mandrill
@ sw123456 Routing sieciowy wykorzystuje niewielką modyfikację drzewa binarnego o nazwie Trie (stworzoną dla większej wydajności w dziedzinie problemowej). W rzeczywistości przechowuje informacje o hierarchii, gdy routery przeszukują drzewo krok po kroku, szukając adresu IP, aby dowiedzieć się, dokąd powinien przekazać pakiet. Adresy IP są również z natury hierarchiczne, więc podczas przemierzania adresu IP w celu znalezienia najdłuższego dopasowania prefiksu router przemierza hierarchię IP, adresy IP podsieci itp. Nie jest to oczywiste semantycznie, ale związek istnieje. Routery używają tej struktury do zwiększenia wydajności wyszukiwania, jak odpowiedział Mason.
Chris Cirefice
3

Dowolną strukturę drzewa, w której węzeł może mieć nieograniczoną liczbę dzieci, można zaimplementować za pomocą drzewa binarnego.

Dla każdego węzła w drzewie zastąp go węzłem z prawym i lewym wskaźnikiem. Lewy wskaźnik wskazuje pierwsze dziecko potomne węzła. Właściwy węzeł przechodzi do następnego rodzeństwa węzła. Wszystkie elementy podrzędne węzła znajdują się na połączonej liście połączonej prawymi wskaźnikami, a nagłówek listy wskazuje lewy wskaźnik ich rodzica.

Twoje skomplikowane drzewo n-ary stało się prostym drzewem binarnym.

Jestem pewien, że jest to w Knuth, Vol. 1 gdzieś.

Justsalt
źródło
To naprawdę ciekawe wdrożenie. Czy mam rację, myśląc, że ponieważ każdy węzeł potomny był początkiem listy połączonej, drzewo nie byłoby już O (log) n), jeśli było zrównoważone, ani O (n), jeśli nie, ze względu na fakt, że odwiedzanie każdego węzła by się zaczęło poza liniowym wyszukiwaniem? Wdrożenie spowodowałoby znacznie wolniejsze czasy wyszukiwania? Ale z drugiej strony, czasy wyszukiwania byłyby szybsze niż w przypadku standardowej struktury liniowej? Czy zrozumiałem to poprawnie?
sw123456
@ sw123456, Gdyby oryginalne drzewo było zrównoważone, wynikowe drzewo binarne prawie na pewno nie byłoby. Wierzę, że wszystko inne zależy od wentylatora z drzewa, ile dzieci ma dany węzeł. Wyszukiwanie liniowe miałoby miejsce tylko wtedy, gdy dowiemy się, które z dzieci danego węzła mają być śledzone. Ale nie jestem pewien, czy można tego uniknąć w każdej innej implementacji drzewa n-ary.
Justsalt
2

Drzewa binarne, po co z nich korzystać?

W programowaniu dużo pracujesz z kolekcjami danych tego samego typu.

Dwa podstawowe sposoby przechowywania tych danych to: listy połączone i tablice.

Oba mają wady i zalety: na połączonej liście łatwo jest dodawać elementy w dowolnej pozycji lub usuwać elementy. Ale dostęp do określonego elementu jest trudniejszy, ponieważ musisz przeglądać listę, aż znajdziesz się w żądanym elemencie.

  • Nie wyszukuje wydajnie, ale wstawianie i usuwanie jest łatwe.

Dostęp do określonego elementu z tablicy jest łatwy, ale trudniej jest wstawić lub usunąć element, ponieważ wstawianie oznacza: przedłużyć tablicę o jeden, przesunąć wszystkie elementy przed pozycją wstawiania 1 w prawo i wstawić element.

  • Wyszukuje wydajnie (jeśli jest posortowane), ale wstawianie i usuwanie jest trudne.

Tak więc zarówno lista połączona, jak i tablica mają wady.

Drzewa binarne są tworzone w celu rozwiązania zarówno problemów tablicy, jak i połączonej listy:

  1. Łatwe wstawianie i usuwanie
  2. Łatwe wyszukiwanie

Drzewo binarne powstaje wtedy, gdy masz dużo danych, które regularnie się zmieniają.

Pieter B.
źródło