J'ai un arbre binaire parfait, c'est-à-dire que chaque nœud de l'arbre est soit un nœud de feuille, soit deux enfants, et tous les nœuds de feuilles sont au même niveau. Chaque nœud a un indice en profondeur-premier ordre. (par exemple, dans un arbre avec 3 niveaux, le nœud racine a indice 0, le premier enfant a 1, le premier enfant du premier enfant a 2, le deuxième enfant de la Le premier enfant a 3, le deuxième enfant a 4 ans, le premier enfant du deuxième enfant en a 5, le deuxième enfant du deuxième enfant a indice 6. ) Je connais la taille de l'arborescence (nombre de nœuds / niveau maximum), mais seul l'index d'un nœud particulier, et je dois calculer son niveau (c'est-à-dire sa distance à la norme rootnode). Comment puis-je faire cela le plus efficacement?
7 Réponses :
EDIT: Tentative Number 1 ... ne fonctionne que pour BFS.
Si par arbores binaire parfaite, vous voulez dire un arbre binaire avec une structure similaire à un tas, vous pouvez alors calculer l'index parent d'un nœud à l'aide de cette formule: afin que vous puissiez répéter cette formule jusqu'à ce que vous arriviez à <= 0, chaque fois que vous vous bougeez essentiellement un niveau dans l'arbre. EDIT: Tentative Numéro 2 .. La meilleure façon que je puisse penser que cela prendrait O (index + log n) qui est O (n). Faites un DFS jusqu'à ce que vous atteigniez l'index désiré, puis continuez à monter l'arborescence à l'aide d'un pointeur parent jusqu'à ce que vous atteigniez la piste à la racine du nombre de fois que vous avez augmenté. Cela suppose qu'un pointeur parent existe sur chaque nœud.
Non, car il utilise l'indice en profondeur-premier ordre.
@Justin "O (index + journal n) qui est toujours O (journal n)" -> Non O (index + log n) est O (n)
@Thomash d'oh! Bonne prise à nouveau!
Il semble que la marche sur l'arbre doit être suffisamment efficace.
à chaque étape de l'algorithme, gardez à l'esprit la plage des index sur le sous-arbre du nœud que vous avez. La première valeur de la plage de la plage est le nœud racine et, après la première moitié, la plage de la sous-arbre à gauche et la seconde moitié doit être la plage du sous-arbre de droite. Vous pouvez ensuite rejoindre récursivement jusqu'à ce que vous trouviez votre nœud.
Par exemple, permet de rechercher dans un arbre de 4 niveaux avec 15 éléments vous devriez Soyez capable de le faire avec une boucle simple, en utilisant seulement quelques variables pour stocker le début et la fin des gammes. Vous devriez également facilement être capable d'adapter ceci si vous apportez des modifications mineures, telles que l'utilisation de Traversal Post / Pre / Pre / Or-commander ou de démarrer le formulaire d'index 1 au lieu de 0.
Cela semble également être correct et se prête bien à une solution facilement maintenable, mais ne correspond probablement pas à mes exigences de performance.
@hrehfeld: En réalité, cela devrait correspondre aux exigences de performance. Quel que soit l'algorithme que vous recevez de cela devrait ressembler beaucoup à ce que Tomash, etc. est venu avec.
Si tout ce que vous avez est l'index, vous ne pouvez pas trouver la profondeur.
Supposons que vous ayez un arbre comme celui-ci: p> le nœud avec index 3 a une profondeur 2. p> supposons que vous ayez un arbre comme celui-ci: p> Le nœud avec index 3 a une profondeur 1. P> Vous ne pouvez pas distinguer entre ces deux arbres simplement en connaissant leurs index. Il n'ya aucun moyen de trouver la distance entre la racine juste en connaissant l'index. P> Edit: Si vous voulez dire un arbre binaire parfait comme dans, toutes les feuilles sont à la même profondeur, et chaque parent a deux enfants, puis vous Je ne trouve toujours pas la profondeur. P> Comparez ces deux arbres: P> def distanceFromRoot(index, rootIndex, treeHeight):
if index == rootIndex:
return 0
leftIndex = rootIndex+1
rightIndex = rootIndex + 2**treeHeight
if index >= rightIndex:
return 1 + distanceFromRoot(index, rightIndex, treeHeight-1)
else:
return 1 + distanceFromRoot(index, leftIndex, treeHeight-1)
Nous parlons de parfait arbres binaires. "J'ai un arbre binaire parfait, c'est-à-dire que chaque nœud de l'arbre est soit un nœud de feuille, soit deux enfants."
Mon exemple d'arbres n'a-t-il pas satisfer ce critère? Tous les nœuds ont 0 ou 2 enfants.
Je pense que "parfait" arbre représente généralement "complètement rempli". Comme dans, si vous avez des niveaux K, vous avez 2 ^ k-1 nœuds.
bon point. J'ai ajouté un autre exemple pour les arbres complètement remplis.
Oui, mais nous savons la taille de l'arbre
Augh, la définition de problème continue de déplacer :)
Pardon! Je pensais que ma question était précise, mais ce n'était pas :-)
non testé: ici compte est le nombre total de nœuds dans l'arborescence.
(Compt + 1) / 2 - 1 semble un peu bizarre, pourquoi n'utilisez-vous pas (compte - 1) / 2 ?
let Cet algorithme fait ce que vous voulez: < Pré> xxx 0 est l'index de la racine, si i est l'index que vous recherchez et n soit le nombre total de nœuds. i = 0 alors vous êtes au bon niveau, sinon vous pouvez supprimer la racine et vous obtenez deux sous-arbres n = (n-1) / 2 mises à jour Le nombre de nœuds est le nouvel arborescence (qui est un sous-arbre de l'ancien) et i = i% n sélectionne uniquement le bon Sous-arbre.
Je viens d'ajouter des explications.
HM, maintenant, je comprends comment ça marche, mais il me semble que la phrase "i = i% n sélectionne uniquement le bon sous-arbre." est faux. On dirait que vous "remplacer les coordonnées" pour faire des travaux d'algorithme dans le sous-arbre, quelle racine = 0. BTW, bel algorithme.
Donc, nous avons un tel arbre avec 4 niveaux:
static int level(int index, int root, int treeDepth) {
if (index == root)
return 0;
if (treeDepth <= 0 /* no tree */ || treeDepth == 1 /* tree contains only root */)
throw new Exception("Unable to find node");
int left = root + 1;
int right = left + (int)Math.Pow(2, treeDepth - 1) - 1;
if (index == left || index == right)
return 1;
if (left < index && index < right)
return 1 + level(index, left, treeDepth - 1);
else
return 1 + level(index, right, treeDepth - 1);
}
P.S: désolé pour mon anglais, s'il vous plaît
Voici une autre suggestion qui faciliterait la solution à cette question:
Si vous étiquetez les nœuds avec un index dans l'arrière-plan, vous pouvez calculer le niveau sans aucune traversée dans O (1) heure. Donc, si vous faites plusieurs requêtes, vous pouvez effectuer une opération O (n) BFT et que chaque requête a répondu dans O (1) heure. P>
La formule du niveau est la suivante: P>
0
/ \
/ \
1 2
/ \ / \
/ \ / \
3 4 5 6
Désolé, mais la mise en page a été spécifiquement demandée d'être en profondeur-premier ordre.
Ce n'est pas un arbre binaire, si un nœud peut avoir> 2 enfants.
S'il vous plaît, lisez la question: "C'est la profondeur - premier, mais pas Un arbre binaire parfait"
Vous devez également connaître le nombre total de nœuds, sinon le niveau peut ne pas être possible de calculer.
@nsinreal Eh bien, la question est trompeuse. Il dit "J'ai un arbre binaire parfait" et "c'est la profondeur - premier, mais pas un arbre binaire parfait"
@Justin Eh bien, c'est juste un exemple de première commande
Oui, j'aurais dû dire que plus clairement.