La différence entre la complexité du temps nécessaire pour construire les Binaires de recherche de l'arbre et de l'arbre AVL?

Alors que j'étais en train d'apprendre arbre de recherche Binaire(Symétrique et asymétrique), j'arrive avec des questions auxquelles je dois résoudre:

  1. Si je construire un arbre de recherche Binaire(Pas besoin d'être équilibré) , à l'aide de n éléments, alors quel est le temps total de la complexité de la construction de l'arbre ?

  2. Si un arbre AVL est construit à partir de n éléments, alors quel est le temps de la complexité de contruct que AVL arbres ?

Devrait-il être plus que nlog(n) ? parce que nous avons besoin de beaucoup de rotation pour la construction de l'arbre AVL .

Je sais que l'insertion et la suppression fonctionnement en AVL arbre sera de log(n) de l'ordre(même si binaire un arbre de recherche construit avec des éléments aléatoires a log(n) hauteur).

Mais j'ai besoin de savoir à propos de global de la construction de l'arbre de coût et de comment il varie comme j'ai besoin d'utiliser équilibré arbre de recherche pour le tri but .

  • 1) O(n) 2) nlog2(n)
  • 1. moyenne des cas: O(nlgn) ; pire cas: O(n*n) 2. O(nlgn)
InformationsquelleAutor Kshitij Jain | 2013-07-13