Je veux résumer toutes les valeurs dans les feuilles dans un BST, et je ne peux pas obtenir les leafs sans courir tout l'arbre ... :(Comment puis-je obtenir les feuilles dans un arbre de recherche binaire?
Merci les gars, mais ses seulement à des fins académiques ... i n'a pas voulu "payer" O (N) pour obtenir la somme de toutes les feuilles, mais il semble que c'est la seule façon
Il n'y a aucun moyen d'obtenir les feuilles d'un arbre sans traverser l'arbre entier (en particulier si vous voulez toutes les feuilles), qui fonctionnera malheureusement en O. Vous êtes sûr qu'un arbre est le meilleur moyen de stocker vos données si vous voulez accéder à toutes ces feuilles? Permettre un accès plus efficace à vos données
Vous devrez soit parcourir l'arborescence à la recherche de nœuds sans enfants, soit modifier la structure que vous utilisez pour représenter l'arborescence afin d'inclure une liste des nœuds feuille. Cela nécessitera également de modifier vos méthodes d'insertion et de suppression pour maintenir la liste (par exemple, si vous supprimez le dernier enfant d'un nœud, il devient un nœud feuille). À moins que l'arbre ne soit très grand, il est probablement assez agréable pour aller de l'avant et traverser l'arbre.
Pour accéder à tous les nœuds feuille d'un BST, vous devrez traverser tous les nœuds de BST et cela serait d'ordre O (n). Une alternative consiste à utiliser l'arborescence B + dans laquelle vous pouvez traverser vers un noeud feuille en O (log n) et après cela, tous les nœuds feuille peuvent être accédés séquentiellement pour calculer la somme. Donc, dans votre cas, ce serait O (log n + k), où k est le nombre de nœuds feuilles et n est le nombre total de nœuds dans l'arbre B +.
acclamations
Le log n peut être éliminé en stockant un pointeur sur le nœud feuille le plus à gauche ou le plus à droite. –
En effet. Cela devrait aider. – Arnkrishn
Vous vous rendez compte que les feuilles elles-mêmes seront au moins 1/2 de O (n) de toute façon?
Pourriez-vous élaborer davantage sur votre question? On dirait que vous cherchez un moyen de faire la somme de toutes les feuilles sans traverser l'arbre complet? L'arbre est-il si gros qu'une traversée complète prend autant de temps? –
Une autre façon de le faire est de l'ajouter à un prix que vous payez déjà; calculer la somme en insérant les données. –