La complexité de l'insertion de n nombres dans un arbre de recherche binaire
J'ai une question, et il dit: "calculer les délais serrés de la complexité du processus d'insertion de n nombres dans un arbre de recherche binaire". Il ne désigne pas si c'est un arbre équilibré ou pas. Alors, quelle réponse peut-être donnée à une telle question? Si c'est l'équilibre de l'arbre, la hauteur est logn, et l'insertion de n nombres prendre en O(nlogn). Mais ce n'est pas équilibré, il peut être encore O(n2) en temps dans le pire des cas. Que signifie pour trouver le calendrier de la complexité de l'insertion de n nombres à un bst? Ai-je raté quelque chose? Grâce
OriginalL'auteur yrazlik | 2013-03-10
Vous devez vous connecter pour publier un commentaire.
Il pourrait être O(n^2), même si l'arbre est équilibré.
Supposons que vous êtes en train d'ajouter une liste de numéros, tous plus grands que le plus grand nombre dans l'arbre. Dans ce cas, tous les numéros seront ajoutés pour le droit de l'enfant de l'extrême droite de la feuille dans l'arbre, Donc O(n^2).
Par exemple, supposons que vous ajoutez des numéros [15..115] à l'arbre suivant:
Les numéros seront ajoutés comme une longue chaîne, chaque nœud ayant une seule main droite de l'enfant. Pour le i-ème élément de la liste, vous devrez traverser ~je nœuds, ce qui donne O(n^2).
En général, si vous souhaitez garder l'insertion et l'extraction en O(nlogn), vous devez utiliser Auto Équilibrage des arbres.
Je veux dire, c'est encore pire des cas, le peu de temps de complexité moyenne qui? Donc, c'est que Θ(n^2)?
Oui, c'est le pire des cas. Vous pourriez trouver un scénario spécifique avec O(nlogn).
Je pense que c'est
1+2+3+4+5+...+n.Pourquoi le wikipedia de dire le pire des cas est O(n) pour la BST, l'Insertion? en.wikipedia.org/wiki/Binary_search_tree
OriginalL'auteur Adam Matan
Ce que le wiki est en train de dire est correct.
Depuis l'arborescence donnée est un BST, donc on n'a pas besoin de chercher à travers toute l'arborescence, comparant l'élément à insérer avec les racines de l'arbre/la sous-arborescence obtiendrez le nœud approprié pour l'élément th. Cela prend O(log2n).
Une fois que nous avons un tel nœud, nous pouvons insérer la clé, il bht après cela, il est nécessaire de pousser tous les éléments dans le bon aub-arbre à droite, de sorte que la BST et de recherche de la propriété de ne pas obtenir violé. Si l'endroit à être inséré vient d'être la dernière dernière, nous avons besoin de vous inquiéter pour la deuxième procédure. Si cette procédure peut prendre en O(n), dans le pire des cas!!!.
Donc, l'ensemble de la pire des cas, la complexité de l'insertion d'un élément dans un BST serait O(n).
Merci!
OriginalL'auteur Jiten