On Monday, August 14, 2017 at 11:44:06 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 20:04, M.M. pisze:
> > Hmmm, nie wiem co dla Ciebie znaczy "bardzo". Dwadzieścia zagłębień, przy
> > breanch-factor 2.5, oznacza, że drzewko ma np. 90mln węzłów. Kiedyś
> > chyba też miałem styczność z takim mocno zdegenerowanym drzewie...
> > niestety szczegółów już nie mogę sobie przypomnieć. Wydaje się, że
> > ta procedura nie zagłębi się powyżej 40 wywołań, może jeszcze jakiś
> > błąd jest w kodzie?
>
> Chodzi o bardziej zdegenerowane, przypominające listy. Ale ta metoda
> może być. Dla 10 tys moja przerobiona na iterację ma 10 tys zagłębienia,
> a dla tego przykładu z Twoją optymalizacją 1/3 tego.
> https://gist.github.com/borneq/a1f5d7a45b08c77414a44
4462547d8a1

Nie wiem jak budujesz to drzewko, ale są możliwe jeszcze dwie
optymalizacje. Trzeba w węźle zapamiętać maksymalną głębokość
wszystkich pod-gałęzi. Czyli depth(rodzic) = max( depth(childs) ) + 1.
Potem można:
1) najpierw wchodzić do najpłytszych pod-gałęzi
2) ostatniego potomka można iteracyjnie zwalniać.

Pozdrawiam