Porządek złożoności w kolejności w drzewie wyszukiwania binarnego (przy użyciu iteratorów)?

Question

Powiązane pytanie: Time Complexity of InOrder Tree Traversal of Binary Tree O(N)?, jednak opiera się na przechodzeniu przez rekursję (czyli w przestrzeni O (log N)), podczas gdy iteratory pozwalają na zużycie tylko O ​​(1) spacji.

W języku C++ normalnie istnieje wymóg, aby inkrementacja kontenera standardowego była operacją O (1). W przypadku większości kontenerów jest to banalnie udowodnione, jednak z map i takie, wydaje się nieco trudniejsze.

• Jeśli map zostały zaimplementowane jako skip-liście, to wynik byłby oczywisty
• Jednak często są one realizowane jako czerwono-czarny drzew (lub przynajmniej jak przeszukiwanie binarne drzew)

Tak więc, podczas przechodzenia w kolejności są chwile, w których "następna" wartość nie jest tak łatwo dostępna. Na przykład jeśli wskażesz prawy dolny lewy lewy poddrzewo, to następnym węzłem do przemierzania jest korzeń, który jest oddalony o kilka kroków.

Próbowałem „udowodnienia”, że algorytmicznych złożoność (w kategoriach „kroków”) został amortyzowane O (1), co wydaje się w porządku. Jednak nie mam jeszcze demonstracji.

Oto mały diagram, który wyśledziłem dla drzewa o głębokości 4, liczby (w miejscu węzłów) reprezentują liczbę kroków, które mają przejść od tego węzła do następnego podczas przemieszczania się w kolejności :

 3 
    2  2 
1 1 1 1 
1 2 1 3 1 2 1 4 

Uwaga: prawo-najbardziej liść ma koszt 4 w przypadku byłoby to sub-tree większego drzewa.

Suma wynosi 28, dla łącznej liczby węzłów wynoszącej 15: w ten sposób średnio mniej niż 2 na węzeł, który (jeśli będzie się utrzymywał) będzie ładnym zamortyzowanym kosztem. Więc:

• Podczas przechodzenia na zamówienie, jest zwiększany iteracyjnej naprawdę O (1) dla zrównoważonego (i pełne) binarne drzewo wyszukiwania?
• Czy wynik może zostać rozszerzony na inne, nieobsługiwane drzewa wyszukiwania binarnego?

Answer 1

Tak, zamortyzowany koszt to rzeczywiście O(1) za iterację dla dowolnego drzewa.

Dowód jest oparty na liczbie "odwiedzin" każdego węzła.
Liście są odwiedzane tylko raz. Żadne liście nie są odwiedzane co najwyżej 3 razy:

1. podczas przechodzenia od rodzica do samego węzła.
2. kiedy wracając z lewego poddrzewa
3. kiedy wraca z prawego poddrzewa

Nie ma więcej wizyt wszelkich węzłów, więc jeśli zsumujemy liczbę odwiedzin każdego węzła, otrzymujemy liczba mniejsza niż 3n, więc łączna liczba wizyt wszystkich połączonych węzłów to O(n), co daje nam O(1) na krok amortyzowany.

(Uwaga gdyż w pełnym drzewie istnieje n/2 liście, że są coraz 2n pan osiągnął kres, wierzę, można pokazać, że suma wizyt będzie mniejszy niż 2n dla każdego drzewa, ale ta „optymalizacja "jest poza zakresem IMO).

---

W najgorszym przypadku za krokiem jest O(h), który jest O(logn) w zrównoważonym drzewie, ale może być O(n) w niektórych przypadkach.

---

P.S. Nie mam pojęcia, jak czerwono-czarne drzewa są zaimplementowane w C++, ale jeśli struktura danych drzewa zawiera pole parent z każdego węzła, może zastąpić stos rekursywny i pozwolić na zużycie przestrzeni. (Jest to oczywiście "oszustwo", ponieważ przechowywanie takich pól jest samo w sobie O(n)).