Przydatność przejścia drzew binarnych przed i po zamówieniu

13

To może być bardzo naiwne, ale zastanawiałem się, czy to w kontekście drzew binarnych (zwykłych, posortowanych i zrównoważonych) wszystkich rodzajów przechodzenia:

  • pierwsze zamówienie w głębokości
  • najpierw głębokość w kolejności
  • głębokość pierwszego zamówienia po zamówieniu
  • szerokość pierwsza

jaka jest rzeczywista użyteczność przedsprzedażowa i po zamówieniu? Mam na myśli, czy istnieje jakiś typ i / lub konfiguracja drzewa binarnego, w których przechodzenie przed i / lub po zamówieniu dałoby (pewną) przewagę nad pozostałymi dwoma?

AFAICS, istnieją pewne typy i konfiguracja drzew binarnych, dla których kolejność i szerokość mogą dać pewną przewagę:

  • dla zrównoważonego drzewa binarnego każde przejście w pierwszej głębokości zużyje mniej miejsca w pamięci w porównaniu do pierwszego (np. w przypadku zrównoważonego drzewa binarnego z 6 lub 7 węzłami wysokość wynosi 2, więc każde przejście w pierwszej głębokości będzie musiało pomieścić maksymalnie 2 węzły w danym momencie, podczas gdy ostatni poziom ma 3 lub 4 węzły, więc przejście przez pierwszą szerokość wymagałoby przechowywania do 3 lub 4 węzłów w pewnym momencie). W takim przypadku korzystanie z przechodzenia w kolejności zużywa najmniej pamięci i odwiedza węzły w ich naturalnej kolejności.

  • w przypadku niezrównoważonego drzewa binarnego, jeśli jest ono bliskie najgorszemu scenariuszowi wstawiania, przejście przez szerokość w pierwszej kolejności zużyłoby mniej pamięci w porównaniu do dowolnego przejścia w głębokości pierwszego. Tak więc w tym przypadku pierwsza szerokość jest zaletą. Podróż w kolejności ma tę zaletę, że odwiedza wartości w ich naturalnym porządku.

Nie mogę jednak pomyśleć o sytuacji, w której przed i po przejściu dałoby przewagę nad pozostałymi dwoma.

Shivan Dragon
źródło

Odpowiedzi:

13

Musisz robić różne rzeczy z drzewami, np. Tłumaczyć między strukturą danych a niektórymi reprezentacjami szeregowymi, np. W pliku lub w języku.

Załóżmy na przykład, że masz takie drzewo parsowania:

    *
   / \
  +   \
 / \   \
A   B   C

Możesz serializować go * + A B C, postępując w kolejności prefiksowej lub A B + C *postępując w kolejności postfiksowej. Jeśli w ogóle pracujesz z procesorami językowymi, takie rzeczy muszą być drugą naturą.

Mike Dunlavey
źródło
Bardzo dobry przykład! I zwróć uwagę na to, jak przyniosłoby to przechodzenie w kolejności A + B * C, co jest łatwiejsze do zrozumienia dla zwykłych użytkowników niż którykolwiek z prefiksów postfiksów.
Kilian Foth
3
@KilianFoth, z wyjątkiem tego, że drzewo nie mówi - mówi (A + B) * C, przynajmniej moim oczom. Chociaż moje palce HP-28s jak wersja AB + C * są w porządku. :-)
sdg
@Kilian: sdg ma rację. Z zamówieniem wewnętrznym musisz mieć pierwszeństwo, chyba że umieścisz nawiasy wokół wszystkiego.
Mike Dunlavey,
13

Artykuł na Wikipedii zawiera ładny, zwięzły opis tego, kiedy chcesz użyć różnych typów wyszukiwania w pierwszej kolejności:

  • Przechodzenie w przedsprzedaży z wyprzedzeniem podczas duplikowania węzłów i wartości może stanowić całkowitą kopię drzewa binarnego. Można go również użyć do wykonania wyrażenia prefiksowego (notacji polskiej) z drzew wyrażeń: przeglądaj drzewa wyrażeń w kolejności.
  • Przechodzenie w kolejności jest bardzo często stosowane w drzewach wyszukiwania binarnego, ponieważ zwraca wartości z podstawowego zestawu w kolejności, zgodnie z komparatorem, który ustawił drzewo wyszukiwania binarnego (stąd nazwa).
  • Przechodzenie po zamówieniu podczas usuwania lub zwalniania węzłów i wartości może usunąć lub zwolnić całe drzewo binarne. Może także generować reprezentację postfiksową drzewa binarnego.

Sprowadza się to do logistycznych potrzeb algorytmu. Na przykład, jeśli podczas usuwania nie używasz przechodzenia po zamówieniu, tracisz referencje potrzebne do usunięcia drzewek potomnych.

Karl Bielefeldt
źródło
Wikipedia z 10 listopada 2019 r. Uległa zmianie, a pierwszy opis należy również do Post-Order, co jest mylące. Właśnie dlatego znalazłem się tutaj, szukając innego źródła informacji.
whoan,
5

Istotą posiadania różnych algorytmów do obsługi drzew binarnych nie jest robienie rzeczy z drzewami. Na tym abstrakcyjnym poziomie jedno zamówienie jest w dużej mierze tak samo dobre jak każde inne, ponieważ z procedury uzyskuje się tylko abstrakcyjne symbole.

Ale drzewa są zwykle używane do reprezentowania interesujących rzeczy, a to może mieć duży wpływ na wynik. Na przykład, jeśli węzły reprezentują stany wyszukiwania w pełnym wyszukiwaniu przez dużą domenę (być może nawet domenę nieskończoną), najpierw malejące, a najpierw przetwarzanie nie tylko określa, w jakiej kolejności znajdują się wyniki, ale może nawet ustalić, czy kiedykolwiek znajdź w ogóle jakieś rozwiązania . Najłatwiej jest to dostrzec w przypadku nieskończonych domen: jeśli zejdziesz nieostrożnie, możesz przeoczyć rozwiązanie, które leży dość wysoko na drzewie, po prostu dlatego, że źle skręciłeś. Ale w praktyce, ponieważ pamięć i dyski są również skończone, dotyczy to nawet domen, które są po prostu bardzo duże, a nie naprawdę nieskończone.

Kilian Foth
źródło