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:
-
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 ?
-
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)
Vous devez vous connecter pour publier un commentaire.
Laissez-nous commencer avec la construction d'un Arbre AVL. Pour créer un arbre, vous avez pour insérer
n
éléments. Pour insérer l'élément dans un arbre équilibré vous avez besoinlog(n)
. Donc vous vous retrouvez avecO(n*log(n))
.De revenir à un régulière BST. Il est contre-intuitif, mais ça dépend comment voulez-vous construire cet arbre. Si vous ne connaissez pas tous les éléments de la STB à l'avance (algorithme en ligne) alors vous devez insérer chaque
n
éléments l'un après l'autre. Si vous êtes très malchanceux, la complexité de l'insert estO(n)
et donc il se détériore àO(n^2)
.Avis que cette situation est très peu probable mais toujours possible.
Mais vous pouvez encore atteindre
O(nlog(n))
si vous connaissez tous les éléments à l'avance. Vous pouvez les trierO(nlog(n))
puis insérer les éléments dans l'ordre suivant. Prendre le milieu de l'élément et l'insérer en tant que root, puis, de manière récursive faire la même chose pour les deux parties que sont la gauche. Vous allez vous retrouver l'équilibre de la STB, l'insertionn
éléments à l'aide delog(n)
.