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.
źródło
A + B * C
, co jest łatwiejsze do zrozumienia dla zwykłych użytkowników niż którykolwiek z prefiksów postfiksów.Artykuł na Wikipedii zawiera ładny, zwięzły opis tego, kiedy chcesz użyć różnych typów wyszukiwania w pierwszej kolejności:
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.
źródło
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.
źródło