Le nombre Total de nœuds dans l'arbre de structure de données?
J'ai un arbre de structure de données qui est L niveaux de profondeur de chaque nœud a sur N nœuds. Je veux le nombre total de nœuds dans l'arbre. Pour ce faire (je pense) j'ai besoin de savoir quel est le pourcentage de nœuds qui ont des enfants.
Qu'est-ce que le terme correct pour ce ratio de nœuds feuilles non-nœuds feuilles en N?
Quelle est la formule pour le nombre total de nœuds dans les trois?
Mise à jour Quelqu'un mentionner facteur de branchement dans un de la réponse, mais il a ensuite disparu. Je pense que c'est le terme que je cherchais. Donc ne devrait pas une formule de prendre le facteur de branchement en compte?
Mise à jour j'aurais dit une estimation sur une hypothétique discbased, pas le chiffre exact!
OriginalL'auteur tpower | 2009-02-05
Vous devez vous connecter pour publier un commentaire.
Ok, chaque nœud a propos de N nœuds secondaires et l'arbre est L niveaux de profondeur.
Le nombre total de nœuds (N^L-1) /(N-1).
Ok, juste un petit exemple pourquoi, elle est exponentielle:
+1, mais il ne serait pas mal de préciser l'algèbre de montrer pourquoi 1+N+N^2+...+N^L = (N^L-1)/(N-1).
Edit: j'ai fait Andrea Ambu du changement proposé et aussi corrigé une erreur de frappe.
En fait, votre solution de l'équation est un peu hors il devrait être tout simplement (N^L)-1 (imaginez si N 2 et L, 3 - la somme est 1+2+4=7=(2^3)-1). Ce qui peut être montré assez facilement par le biais de l'induction.
J'ai tiré Gamecat la formule de façon indépendante. Si N=2, alors votre réponse proposée est aussi correct comme en divisant par (N-1) ne change rien dans ce cas. C'est quand on N>2 que vous avez besoin pour effectuer la division d'obtenir une réponse correcte.
OriginalL'auteur Toon Krijthe
Juste pour corriger une faute de frappe dans la première réponse: le nombre total de nœuds d'un arbre de la profondeur de L est (N^(L+1)-1) /(N-1)... (qui est, à la puissance de l'+1 plutôt que de simplement L).
Cette situation peut être illustrée comme suit. Tout d'abord, prendre notre théorème:
1 + N^1 + N^2 + ... + N^L = (N^(L+1)-1)/(N-1)
Multiplier les deux côtés par (N-1):
(N-1)(1 + N^1 + N^2 + ... + N^L) = N^(L+1)-1.
Développez le côté gauche:
N^1 + N^2 + N^3 + ... + N^(L+1) - 1 - N^1 - N^2 - ... - N^L.
Tous les termes N^1 à N^L sont annulées, ce qui laisse N^(L+1) - 1. C'est notre côté droit, de sorte que la première égalité est vraie.
OriginalL'auteur
Si votre arbre est d'environ plein, c'est chaque niveau a son complément d'enfants, sauf pour les deux derniers, alors vous avez entre les N^(L-2) et N^(L-1) nœuds feuilles et entre les N^(L-1) et N^L de nœuds total.
Si votre arbre n'est pas complet, alors connaître le nombre de nœuds feuilles n'aide pas totalement déséquilibrée arbre aura un nœud feuille mais arbitrairement de nombreux parents.
Je me demande comment précis de votre déclaration de 'chaque nœud a propos de N nœuds est si vous savez le facteur de branchement moyen, peut-être vous pouvez calculer la taille de l'arbre.
Si vous êtes en mesure de trouver la proportion de feuilles pour les noeuds internes, et vous savez le nombre moyen d'enfants, vous pouvez calculer approximativement ce que (n*ratio)^N = n. Ce ne sera pas vous donner votre réponse, mais je me demande si quelqu'un avec une meilleure maths que moi, peut trouver un moyen d'interposer L dans cette équation et vous donner quelque chose soluble.
Encore, si vous voulez savoir précisément, vous devez effectuer une itération sur la structure de l'arbre et de compter les noeuds que vous allez.
OriginalL'auteur HenryR
La formule pour calculer la quantité de nœuds dans la profondeur de L est: (étant Donné qu'il y a N nœuds racine)
NL
Pour calculer le nombre de tous les nœuds de ce qu'on doit faire cela pour chaque couche:
Si il ya seulement 1 nœud racine, soustraire 1 de L et ajouter 1 au total de nœuds nombre de.
Être conscient que si dans un nœud de la quantité de feuilles est différente de la moyenne des cas, cela peut avoir un grand impact sur votre numéro. Le plus haut dans l'arbre le plus d'impact.
C'est wiki de la communauté, alors n'hésitez pas à modifier mon effroyable de l'algèbre.
Que le premier niveau de l'arbre a N nœuds, plutôt que de 1. Mis à jour en conséquence.
Vous avez raison, quoique, en réalité, la somme que vous êtes dans le calcul de cette boucle s'avère être exprimable comme une simple formule, donnée dans GameCat de réponse.
OriginalL'auteur
Si vous ne savez rien d'autre, mais la profondeur de l'arbre, alors votre seule option pour travailler sur la taille totale est d'aller à travers et de les compter.
Yep, c'était mon erreur - j'ai lu la question comme ayant besoin de connaître la taille exacte de l'arbre.
OriginalL'auteur Mark Pim