Dlaczego TreeSet Iteracja O (n) zamiast O (n * logn)?

Question

Przeczytałem previous question o złożoności czasowej dla TreeSet i odpowiedziano, że zajmuje to O (n) czas. Jednak nie rozumiem, dlaczego jest O (n) do iteracji zamiast O (n * nlogn).

Każde następne wywołanie odbywa O(logn) time

Więc jeśli iterację TreeSet tak:

while (iterator.hasNext()){ //Runs N times 
    System.out.println(iterator.next() + " "); //each next is O(logn) 
} 

by się spodziewać, że będzie O (n * logn), a nie O (n), ponieważ pętla while ma N iteracji, a każda iterator.next() wywołuje czas O (logn).

Answer 1

Najgorszy czas dla jednej operacji next to O(log n), ponieważ jest to wysokość drzewa. Średnio jednak następny element można znaleźć w czasie O(1). Dzieje się tak dlatego, że cała operacja polega na dwukrotnym użyciu każdej krawędzi drzewa.

Answer 2

można zaimplementować iteracji dla drzewa tak:

void print(Node n) { 
    if (n.left != null) print(n.left); 
    System.out.println(n.value); 
    if (n.right != null) print(n.right); 
} 

Druk funkcja ma być wywołana dokładnie jeden raz dla każdego węzła, więc całkowity czas iteracji wynosi O (N). Możesz wdrożyć dokładnie ten sam algorytm iteracyjnie (bez rekursji). A jeśli jesteś wystarczająco ostrożny, możesz mieć klasę, która zachowa stan iteracyjny i przejdzie do przodu, gdy zostanie wywołana .next(). To prawda, że ​​liczba wywołań funkcji między println s jest nierównomierna, ale gdy spojrzysz na nią ogólnie, odkryjesz, że jest ich dokładnie N.