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

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.

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ą.

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.

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.