Klasa std :: map C++ STL implementuje przeglądanie O (log (n)) przy użyciu drzewa binarnego. Ale w przypadku drzew nie jest oczywiste, jak działa iterator. Co właściwie oznacza operator ++ w strukturze drzewa? Podczas gdy pojęcie "następnego elementu" ma oczywistą implementację w tablicy, dla mnie nie jest tak oczywiste w drzewie. W jaki sposób można wdrożyć iterator drzewa?Jak działa iterator std :: map?
W przypadku przesyłania w trybie nieprzekraczalnym (prawdopodobnie działa również w przypadku innych), jeśli w swoich węzłach znajduje się wskaźnik nadrzędny, można przeprowadzić konwersację nierekurencyjną. Powinno być możliwe zapisanie dwóch wskaźników w iteratorze: potrzebujesz wskazania, gdzie jesteś, i prawdopodobnie będziesz (nie robię teraz badań) potrzebuję czegoś takiego jak "poprzedni" wskaźnik, abyś mógł zrozumieć twój aktualny kierunek ruchu (tzn. czy muszę przejść do lewego poddrzewa, czy też właśnie z niego wróciłem).
„Poprzednia” będzie prawdopodobnie być coś „rodzica”, jeśli mamy właśnie wszedł do węzła; "left", jeśli wracamy z lewego poddrzewa, "right", jeśli wracamy z prawego poddrzewa, i "self", jeśli ostatni węzeł, który wróciliśmy, był naszym własnym.
Implementacja może wiedzieć, że wskaźniki węzłów są wyrównane do słów i nadużywają niższych bitów wskaźnika węzła do przechowywania stanu, zamiast używania drugiego wskaźnika. – MSalters
Myślę, że to jest to, czego potrzebowałem. Zasadniczo próbuję utworzyć iterator dla ogólnej klasy drzewiastej i wygląda na to, że działa dla n-ary nieuporządkowanych drzew. – Avi
Rozważ zestaw wszystkich elementów na mapie, które są nie mniejsze niż bieżący element, które nie są również bieżącym elementem. "Następny element" to element z tego zestawu elementów, który jest mniejszy niż wszystkie inne elementy w tym zestawie.
Aby korzystać z mapy, musisz mieć klucz. I ten klucz musi implementować operację "mniej niż". Określa sposób formowania mapy, dzięki czemu operacje wyszukiwania, dodawania, usuwania, zwiększania i zmniejszania są wydajne.
Ogólnie mapa wewnętrznie używa jakiegoś drzewa.
Możesz przyjrzeć się źródłu jako przystawkę: http://www.sgi.com/tech/stl/stl_map.h – amit
Zobacz typowe [auto-bilansujące drzewo wyszukiwania binarnego] (http: // en.wikipedia.org/wiki/Red%E2%80%93black_tree). Łatwo jest zobaczyć algorytm, który dostaje się z danego węzła do następnego większego, patrząc na właściwe dzieci lub przechodząc w górę iw dół drzewa. Czasami trzeba skakać kilka razy, ale wciąż jest to amortyzowany stały czas (ponieważ wysokość drzewa jest logarytmem liczby elementów). –
Ten artykuł wikipedia może odpowiedzieć na niektóre z twoich pytań: [Tree traversal] (http://en.wikipedia.org/wiki/Tree_traversal). Zasadniczo "następny" element może się różnić w zależności od rodzaju przejścia, którego używasz. W przypadku 'std :: map' drzewo jest przemieszczane w kolejności (od najmniejszego elementu do największego). –