Libérer un arbre binaire

13

Donc, avant de lire quelques concepts informatiques de base.

  1. Un arbre binaire est une structure allouée dynamiquement (généralement utilisée pour le stockage ordonné).
  2. En raison de sa nature, la traversée d'arbres binaires est généralement récursive;
    En effet, la traversée linéaire (via une boucle) n'est pas naturelle lorsqu'il existe deux voies de bouclage.
    • Récursif: cela signifie une fonction qui s'appelle elle-même.
  3. Dans les langues anciennes, la gestion de la mémoire nécessite une gestion manuelle de la mémoire.
    • Manuel: signifie que vous devez le faire vous-même.
  4. Lorsque vous effectuez une gestion manuelle de la mémoire, vous devez demander au système sous-jacent de libérer chaque membre de l'arborescence.
    • Gratuit: récupérez la mémoire dans le caca mondial afin qu'elle puisse être réutilisée et que vous ne manquiez pas de mémoire.
    • Libération: cela se fait en appelant la fonction free()et en lui passant le pointeur que vous souhaitez récupérer.
    • Pointeur: C'est comme un bâton virtuel. À la fin, c'est la mémoire. Lorsque vous demandez de la mémoire, vous recevez un pointeur (bâton virtuel) qui a de la mémoire. Lorsque vous avez terminé, vous rendez le pointeur (bâton virtuel).

La solution récursive:

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

Le problème est alors que la récursivité signifie que vous appelez à plusieurs reprises la même fonction. Cela augmente la pile. Agrandir la pile utilise plus de mémoire. La raison pour laquelle vous libérez l'arborescence est que vous souhaitez récupérer de la mémoire en utilisant plus de mémoire est contre-productif (même si vous récupérez les deux bits de mémoire).

Enfin la question:

Le problème se concentre donc sur la conversion de la version récursive ci-dessus en une solution linéaire (de sorte que vous n'ayez pas à utiliser de mémoire).

Donnez le type de nœud

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

Écrivez une fonction pour libérer un arbre de ces nœuds.

Restrictions:

  • Ne peut pas utiliser la récursivité (pas même indirectement)
  • Impossible d'allouer d'espace dynamique pour le suivi.

  • Notez qu'il existe une solution O (n)

Gagnant:

  1. Meilleure complexité.
  2. Tie Break 1: première soumission
  3. Tie Break 2: moins de personnages.
Martin York
la source

Réponses:

7

Semble très proche de O (n) pour moi:

Cela fait une marche en profondeur sur l'arbre et utilise le ->leftpointeur des nœuds traversés pour garder une trace du parent.

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
la source
+1 Ajoutez la coche pour la seule réponse. C'est un peu plus complexe que la solution que je présente ci-dessous mais très bonne.
Martin York
4

C99, 94, O (n)

Edit: tout le monde semble se référer à struct Nodetout comme Nodecomme si l' typedefÉd, donc je l'ai fait aussi.

c'est en fait mon premier golf C. beaucoup de segfaults.

de toute façon, cela nécessite C99 car il utilise une déclaration à l'intérieur de la première instruction d'une boucle 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));}

n'utilisant même pas #define!

cet algorithme fonctionne en transformant l'arborescence de sorte que le nœud supérieur n'a pas d'enfant gauche, puis en le supprimant et en passant à son enfant droit.

par exemple, si nous commençons par l'arbre

 1
/ \
2 3
 \
 4

l'algorithme mute les pointeurs afin que l'arbre soit

2
 \
 1
/ \
4 3

nous pouvons maintenant supprimer facilement le nœud le plus haut.

fier haskeller
la source
Je n'ai pas utilisé typedef car le mien était en C ++ (on oublie ces petites différences entre les langages). J'ai mis à jour la question pour qu'elle fonctionne de la même manière en C et C ++.
Martin York
@LokiAstari Je ne connais pas vraiment le c ++, et j'ai juste commencé à apprendre le C récemment. Mais j'en savais assez pour répondre à cette question :-)
fier haskeller
1
Je vais faire un +1 pour l'instant. Mais je n'ai toujours pas compris comment cela fonctionne, donc je reviendrai après la Turquie. :-)
Martin York
@LokiAstari, il utilise essentiellement le fait que C mélange des expressions et des instructions pour faire des choses en utilisant uniquement des expressions
fier haskeller
1

C / C ++ / Objective-C 126 caractères (inclut la nouvelle ligne de fin requise)

#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);}

Ne fonctionne pas en temps O (n). Mais l'OP ne l'exige pas, voici donc ma solution O (n 2 ).

Algorithme: descendez jusqu'à une feuille depuis la racine. Publiez-le. Répétez jusqu'à ce qu'il n'y ait pas de feuilles. Relâchez la racine.

Non golfé:

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
la source
Malheureusement, cela ne fonctionnera pas. vous ne définissez pas le pointeur de la feuille sur NULL avant de le libérer. Ainsi, vous continuerez sans cesse à libérer le même nœud feuille et n'atteindrez jamais le point où vous libérez l'arbre.
Martin York
@LokiAstari: Merci d'avoir remarqué le bug. Il devrait être corrigé maintenant (même si je n'ai pas testé le code).
Thomas Eding
1

c ++ 99 O (n)

Les boucles ici sont parfaites pour enchaîner une liste mais pas pour monter et descendre des hiérarchies. user300 l'a géré (je suis impressionné) mais le code est difficile à lire.

La solution consiste à convertir l'arborescence en liste.
L'astuce consiste à le faire en même temps que vous supprimez les nœuds.

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;
}

Version Golf

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 élargi

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
la source
0

C, 150 octets

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++;}}

Essayez-le sur JDoodle

T. Salim
la source