On Saturday, May 7, 2016 at 11:27:08 AM UTC+2, Borneq wrote:
> W dniu 07.05.2016 o 08:34, M.M. pisze:
> > najkrótszy czas, to problem jest skomplikowany. Można
> > zapamiętać długość najdłuższego ciągu w każdym węźle. Niestety
> > przez to wstawianie i usuwanie będzie zajmowało nieco więcej
>
> Normalnie to bym przechodził w głąb zapisując głębokość każdego węzła i
> szukając najgłębszego. O tyle - proste.

I tak zrób...

> Jednak to drzewo jest bardzo mało rozgałęzione, ale za to bardzo
> głębokie. Nie chcę rekursji z ponad 400 tys poziomów.

To nie używaj rekursji. Przechodzenie drzewa w głąb/w szerz
bez rekursji, ale za pomocą stosu/kolejki (struktury denych choćby
z stl) to podstawowa technika. Pierwszy rozdział Algorytmy struktury
danych Diksa/rytra. W Cormenia też musi być.

O, i nawet przez aero mi przeciekło, że w wiki jest:
https://en.wikipedia.org/wiki/Depth-first_search#Pse
udocode

A non-recursive implementation of DFS:[6]

1 procedure DFS-iterative(G,v):
2 let S be a stack
3 S.push(v)
4 while S is not empty
5 v = S.pop()
6 if v is not labeled as discovered:
7 label v as discovered
8 for all edges from v to w in G.adjacentEdges(v) do
9 S.push(w)

Tylko zamiast indeksu wierzchołka "pushuj" parę indeks
<wierzchołka, głebokosc>

Złożonośc pamięciowa O(wysokość drzewa).

Pseudokod jest dla DSF dowolnego grafu, więc nawet możesz
linijkę 7 (i znaczniki w wierzchołkach) pominać

> Chcę zapisywać na stos tylko gdy jest rozgałęzienie a ono ma być rzadko

Nadal możęsz to zrobić (w 7 linijce while "jeden potomek" to
v:= syn v; glebokosc++, Po zrobieniu POP i tak odczytasz wysokość
ze stosu.) ale nadal masz pamieciowo O(wysokosć),
przykładem jest drzewo, gdzie każdy lewy syn nie ma potomków,
a każdy (poza ostatnim) prawy syn ma 2 potomków

/\
/\
/\
/\
/\

pzdr
bartekltg