On Monday, August 14, 2017 at 3:47:20 PM UTC+2, Borneq wrote:
> Nie patrząc już na shared_ptr i na listy,grafy cykliczne, mamy drzewko.
> Zwalniamy obiektowo tak że zwalniamy korzeń, wołany jest destructor dla
> korzenia, potem jego dzieci itd.
> Ale co gdy drzewo zdegeneruje się niemal do listy, tak że będziemy
> musieli rekurencyjnie zwalniać listę głębokości 100 tys i więcej?
> Samą listę można zwalniać iteracyjnie od korzenia lub końca. Ale co gdy
> zamiast listy mamy zdegenerowane głębokie drzewo, od którego co ileś
> odchodzą krótkie rozgałęzienia np. długości 20. Ewentualnie jest dwie
> czy trzy gałęzi długie rzędu 100 tys.
> Oto ciekawy problem.


Facet tu mówi o tym:
https://www.youtube.com/watch?v=JfmTagWcqoE
Ok 16 minuty zaczyna się właściwa cześć, wcześniej konstruuje
drzewo na mądrych wskaźnikach.

Dośc pobieżnie, i jestem niemal pewien, ze kod, który pokazuje
jest n^2 a nie nlogn ;-) Jeśli mamy wskaźnik na parent to łatwo
naprawić.

Pomysł, by zwalniać w pętli jeśli jest jeden potomek,
rekurencyjnie, gdy więcej, nie sprawdzi się:
/\
/\
/\
/\
/\
/\
/\
/\

To drzewo też ma głębokość O(n), a zwalniasz je rekurencyjnie.
(do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
szczegolny przypadek).

@pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je
skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.

Przesuń usuwany wierzchołek do kontenera.
Teraz całe drzewo tam siedzi, zaczepione pod ten element;-)
Niech indeks pokazuje na ten (jedyny na razie) element. int i=0; :)

Teraz w pętli:
Wszystkie dzieci wierzchołka spod 'i' przerzuć do kontenera,
i++
Pętle konczysz, gdy i =size.

Działająca przykąłdowa implementacja (wystarczy c++11, ale make_unique
aż się  prosi gdziniegdzie:) poniżej.

pzdr
bartekltg


#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <iterator>
using namespace std;

struct Node {
vector<unique_ptr<Node>> children;
int data;
Node(int x):data(x){}
~Node() { cout << "destruktor "<<data<<endl;}

};
class Tree {
unique_ptr<Node> root;
public:

~Tree(){
vector <unique_ptr<Node>> vec;
vec.push_back(move(root));
unsigned int i=0;

while (i<vec.size()) {
move(vec[i]->children.begin(),vec[i]->children.end()
, std::back_inserter(vec) );
cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
i++;
}
}
void push(int x){
if (root.get()==nullptr){
root = unique_ptr<Node>(new Node(x));
}else{
Node *n=root.get();
while( n->children.size()>0 )
n = (n->children[0].get());
n->children.push_back(unique_ptr<Node>(new Node(x)));
}

}

/*...*/
};



int main(int argc, char *argv[])
{
int c;

{
Tree tree;
for (int k=1000;k<1004;k++)
tree.push(k);
}

cout<<"bla"<<endl;

return 0;
}



OUT:
przenosiny dzieci 0: 1000
przenosiny dzieci 1: 1001
przenosiny dzieci 2: 1002
przenosiny dzieci 3: 1003
destruktor 1000
destruktor 1001
destruktor 1002
destruktor 1003