Comment obtenir la taille d'un arbre binaire?

Question

J'ai une structure d'arbre binaire très simple, quelque chose comme:

struct nmbintree_s { 
    unsigned int size; 
    int (*cmp)(const void *e1, const void *e2); 
    void (*destructor)(void *data); 
    nmbintree_node *root; 
}; 

struct nmbintree_node_s { 
    void *data; 
    struct nmbintree_node_s *right; 
    struct nmbintree_node_s *left; 
}; 

Parfois j'ai besoin d'extraire un « arbre » d'une autre et j'ai besoin pour obtenir la taille de « l'arbre extrait » afin de mettre à jour le taille de l'arbre initial.

Je pensais à deux approches:

1) En utilisant une fonction récursive, quelque chose comme:

unsigned int nmbintree_size(struct nmbintree_node* node) { 
    if (node==NULL) { 
    return(0); 
    } 
    return(nmbintree_size(node->left) + nmbintree_size(node->right) + 1); 
} 

2) Un pré-commande/afinde/postorder traversal fait dans un itérative façon (en utilisant la pile/file d'attente) + compter les noeuds. D'après vous, quelle approche est la plus «à l'épreuve des défaillances de la mémoire»/performante, selon vous?

D'autres suggestions/conseils?

NOTE: Je vais probablement utiliser cette implémentation dans le futur pour de petits projets. Donc, je ne veux pas échouer de façon inattendue :).

Answer 1

Utilisez simplement une fonction récursive. C'est simple à mettre en œuvre de cette façon et il n'est pas nécessaire de le rendre plus compilé. Si vous le faisiez "manuellement", vous finiriez par implémenter la même chose, juste que vous n'utiliseriez pas la pile d'appels système pour les variables temporaires, mais votre propre pile. Habituellement, cela n'aura aucun avantage sur le code plus compliqué. Si vous découvrez par la suite que vous dépensez beaucoup de temps dans votre programme pour calculer la taille des arbres (ce qui n'arrivera probablement pas), vous pouvez toujours commencer à dresser un profil et essayer comment une implémentation manuelle fonctionne. Mais alors il pourrait aussi être préférable de faire des améliorations algorithmiques, comme déjà suivre les changements de taille au cours du processus d'extraction.

Answer 2

Si votre arbre binaire "très simple" n'est pas équilibré, alors l'option récursive est effrayante, à cause de la profondeur de récurrence non contrainte. Les traversées itératives ont le même problème de temps, mais au moins la pile/file d'attente est sous votre contrôle, vous n'avez donc pas besoin de planter. En fait, avec des drapeaux et un pointeur supplémentaire dans chaque nœud et un accès exclusif, vous pouvez itérer sur votre arbre sans aucune pile/file d'attente.

Une autre option consiste pour chaque nœud à stocker la taille du sous-arbre en dessous. Cela signifie que chaque fois que vous ajoutez ou supprimez quelque chose, vous devez suivre tout le chemin jusqu'à la mise à jour de toutes les tailles. Donc, encore une fois, si l'arbre n'est pas équilibré c'est une opération lourde.

Si l'arbre est équilibré, il n'est pas très profond. Toutes les options sont à l'épreuve des échecs, et les performances sont estimées par mesure :-) Mais selon la structure de votre nœud d'arbre, il n'est pas équilibré ou bien vous jouez des jeux idiots avec des drapeaux dans les plus petits ...

Il n'y a peut-être pas beaucoup de raison d'être très intelligent avec ça. Pour de nombreuses utilisations pratiques d'un arbre binaire (en particulier s'il s'agit d'un binaire recherche arbre), vous réalisez tôt ou tard que vous voulez qu'il soit équilibré.Alors économisez votre énergie pour quand vous atteignez ce point :-)

Answer 3

Quelle est la taille de cet arbre, et à quelle fréquence avez-vous besoin de connaître sa taille? Comme l'a dit sth, la fonction récursive est la plus simple et probablement la plus rapide. Si l'arbre est comme 10^3 nœuds, et vous le changez 10^3 fois par seconde, alors vous pouvez simplement garder un compte externe, que vous décrémenter lorsque vous supprimez un nœud, et incrémenter quand vous en ajoutez un. Autre que cela, simple est le meilleur.

Personnellement, je n'aime pas toute solution qui nécessite de décorer les nœuds avec des informations supplémentaires comme les compteurs et les pointeurs «up» (bien que parfois je le fais). Toute donnée supplémentaire comme celle-ci rend la structure dénormalisée, donc la modifier implique un code supplémentaire et des chances supplémentaires d'erreurs.