Uwolnij drzewo binarne

13

Więc zanim przeczytasz kilka podstawowych pojęć informatycznych.

  1. Drzewo binarne jest dynamicznie alokowaną strukturą (zwykle używaną do uporządkowanego przechowywania).
  2. Ze względu na swój charakter przechodzenie przez drzewa binarne jest zwykle rekurencyjne;
    Wynika to z faktu, że przejście liniowe (przez pętlę) nie jest naturalne, gdy istnieją dwie możliwości zapętlenia.
    • Rekurencyjny: oznacza funkcję, która się wywołuje.
  3. W starych językach zarządzanie pamięcią wymaga ręcznego zarządzania pamięcią.
    • Podręcznik: Oznacza, że ​​musisz to zrobić sam.
  4. Podczas ręcznego zarządzania pamięcią należy faktycznie poprosić system podstawowy o zwolnienie każdego członka drzewa.
    • Bezpłatnie: odzyskaj pamięć do globalnych kupek, aby można ją było ponownie wykorzystać i nie zabrakło pamięci.
    • Uwalnianie: odbywa się to przez wywołanie funkcji free()i przekazanie jej wskaźnika, który chcesz odzyskać.
    • Wskaźnik: To jak wirtualny kij. Na końcu jest pamięć. Gdy poprosisz o pamięć, otrzymasz wskaźnik (wirtualny drążek), który ma pamięć. Po zakończeniu oddasz wskaźnik (wirtualny drążek).

Rozwiązanie rekurencyjne:

freeTree(Node* node)
{
    freeTree(node->left);  
    freeTree(node->right);
    free(node);
}

Problem polega na tym, że rekurencja oznacza, że ​​wielokrotnie wywołujesz tę samą funkcję. To zwiększa stos. Zwiększenie stosu wymaga więcej pamięci. Powodem, dla którego zwalniasz drzewo, jest to, że chcesz odzyskać pamięć przy użyciu większej ilości pamięci, co przynosi efekt przeciwny do zamierzonego (nawet jeśli odzyskasz oba bity pamięci).

Nareszcie pytanie:

Więc problem koncentruje się wokół konwersji powyższej wersji rekurencyjnej na rozwiązanie liniowe (dzięki czemu nie musisz używać pamięci).

Podaj typ węzła

typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

Napisz funkcję, aby zwolnić drzewo tych węzłów.

Ograniczenia:

  • Nie można użyć rekurencji (nawet pośrednio)
  • Nie można przydzielić dynamicznej przestrzeni do śledzenia.

  • Zauważ, że istnieje rozwiązanie O (n)

Zwycięzca:

  1. Najlepsza złożoność.
  2. Tie Break 1: Pierwsze zgłoszenie
  3. Tie Break 2: Najmniejsza liczba postaci.
Martin York
źródło

Odpowiedzi:

7

Wydaje mi się bardzo bliskie O (n):

Robi to najpierw głębokość chodzenia po drzewie i używa ->leftwskaźnika przemierzonych węzłów do śledzenia rodzica.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}
Arnaud Le Blanc
źródło
+1 Dodaj zaznaczenie, aby uzyskać jedyną odpowiedź. Jest nieco bardziej złożony niż rozwiązanie, które przedstawiam poniżej, ale bardzo dobrze.
Martin York,
4

C99, 94, O (n)

Edycja: wydaje się, że wszyscy odnoszą się struct Nodetak, Nodejakby to typedefed, więc ja też.

to właściwie mój pierwszy golf C. wiele wad.

w każdym razie wymaga to C99, ponieważ używa deklaracji wewnątrz pierwszej instrukcji pętli for.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

nawet nie używam #define!

ten algorytm działa poprzez przekształcenie drzewa, tak aby górny węzeł nie miał lewego dziecka, a następnie usunięcie go i przejście do jego prawego dziecka.

na przykład, jeśli zaczniemy od drzewa

 1
/ \
2 3
 \
 4

algorytm zmutuje wskaźniki tak, aby drzewo było

2
 \
 1
/ \
4 3

teraz możemy łatwo usunąć najwyższy węzeł.

dumny haskeller
źródło
Nie użyłem typedef, ponieważ mój był w C ++ (zapominasz o tych małych różnicach między językami). Zaktualizowałem pytanie, więc działa tak samo w C i C ++.
Martin York,
@LokiAstari Tak naprawdę nie znam c ++ i właśnie zacząłem uczyć się C. Ale wiedziałem wystarczająco dużo, aby odpowiedzieć na to :-)
dumny haskeller
1
Na razie zrobię +1. Ale wciąż nie opracowałem, jak to działa, więc wrócę po indyka. :-)
Martin York,
@LokiAstari w zasadzie wykorzystuje fakt, że C łączy ze sobą wyrażenia i instrukcje, aby robić rzeczy używając tylko wyrażeń
dumny haskeller
1

C / C ++ / Objective-C 126 znaków (zawiera wymagany końcowy znak nowej linii)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Nie działa w czasie O (n). Ale OP nie wymaga tego, więc oto moje rozwiązanie O (n 2 ).

Algorytm: zejdź do liścia od korzenia. Puść to. Powtarzaj, aż nie będzie liści. Zwolnij root.

Nie golfowany:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}
Thomas Eding
źródło
Niestety to nie zadziała. przed zwolnieniem nie ustawisz wskaźnika na liściu na NULL. W ten sposób będziesz w nieskończoność zwalniał ten sam węzeł liścia i nigdy nie dojdziesz do punktu, w którym uwolnisz drzewo.
Martin York
@LokiAstari: Dziękujemy za zauważenie błędu. Należy to teraz naprawić (choć nie przetestowałem kodu).
Thomas Eding,
1

c ++ 99 O (n)

Pętle są świetne do łączenia łańcuchów wzdłuż listy, ale nie do hierarchii. user300 zarządzał nim (jestem pod wrażeniem), ale kod jest trudny do odczytania.

Rozwiązaniem jest przekonwertowanie drzewa na listę.
Sztuką jest zrobienie tego w tym samym czasie, gdy usuwasz węzły.

void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Wersja golfowa

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf rozszerzony

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}
Martin York
źródło
0

C, 150 bajtów

f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Wypróbuj na JDoodle

T. Salim
źródło