Pour exa, c'est l'arbre.Trouvez le nœud de poids maximum dans une arborescence si chaque nœud est la somme des poids de tous les nœuds qu'il contient.
10
12 -1
5 1 1 -2
2 3 10 -9
Comment trouver le nœud avec la valeur maximale?
Dans le cas général, vous devez parcourir l'arborescence entière. Si les valeurs dans l'arborescence ne sont pas contraintes (par exemple, toutes les valeurs non négatives, mais dans votre exemple, il y a des valeurs négatives), la valeur dans un nœud ne vous dit rien sur les valeurs individuelles inférieures.
Étant donné le problème indiqué, vous devez traverser l'arbre entier. Voir la preuve ci-dessous.
Traverser l'arbre entier devrait être un processus assez trivial.
Preuve que nous devons traverser l'arbre entier:
Supposons que nous sommes en mesure d'identifier de quel côté d'un arbre maximum est sans traverser l'arbre entier.
Étant donné un arbre avec le nœud maximum sur la gauche. Appelez ce maximum x.
Sélectionnez l'un des nœuds feuille sur la droite. Ajoutez 2 enfants: x+1 et -x-1. Depuis x+1-x-1 = 0, l'ajout de ceux-ci ne changera pas la somme à la feuille à laquelle nous l'avons ajouté, ni les sommes des autres nœuds de l'arbre. Puisque ceci peut être ajouté à n'importe quelle feuille dans l'arbre, et cela n'affecte pas les sommes, nous aurions besoin de traverser l'arbre entier pour savoir si cela se produit n'importe où.
Ainsi, notre supposition que nous pouvons identifier le côté d'un arbre où le maximum est activé sans traverser l'arbre entier est incorrecte.
Nous devons donc traverser l'arbre entier.
Est-ce le problème complet? Si c'est le cas, il n'y a aucune raison pour laquelle vous ne pouvez pas vérifier chaque nœud, puisque la simple lecture de l'arbre est déjà une opération 'O (n)'. Peut-être avez-vous plusieurs requêtes/mises à jour? – IVlad