Complexités des traversées d’arbres binaires

Question

Quelle est la complexité temporelle de l’ordre, du post-ordre et de la traversée de précommande des arbres binaires dans les structures de données?? Est-ce O(n) ou O(log n) ou O(n^2)??

Answer 1

``, car vous traversez chaque nœud une fois. Ou plutôt - la quantité de travail que vous effectuez pour chaque nœud est constante (ne dépend pas du reste des nœuds).

Answer 2

O(n),je dirais . Je fais pour un arbre équilibré, applicable à tous les arbres. En supposant que vous utilisez la récursivité,

T(n) = 2*T(n/2) + 1 ----------> (1)

T(n/2) pour le sous-arbre de gauche et T(n/2) pour le sous-arbre de droite et '1' pour la vérification du scénario de base.

Sur Simplifier (1), vous pouvez prouver que la traversée (soit dans l’ordre, soit en précommande ou en post-commande) est de l’ordre O(n).

Answer 3

T(n) = 2T(n/2)+ c

T(n/2) = 2T(n/4) + c => T(n) = 4T(n/4) + 2c + c

de même T(n) = 8T(n/8) + 4c+ 2c + c

....

....

dernière étape ... T(n) = nT(1) + c(somme des puissances de 2 de 0 à h(hauteur de l’arbre))

donc la complexité est O(2^(h+1) -1)

mais h = log(n)

donc, O(2n - 1) = O(n)