Analyse de complexité temporelle de l'arborescence AVL

Puisque la hauteur d'un arbre AVL est O(log n), la complexité temporelle de la recherche, de l'insertion et de delete dans AVLTree sont O(log n). La complexité temporelle des méthodes search, insert et delete dans AVLTree dépend de la hauteur de l'arbre. Nous pouvons prouver que la hauteur de l'arbre est O(log n).

Soit G(h) le nombre minimum de nœuds dans un arbre AVL de hauteur h. Évidemment, G(1) vaut 1 et G(2) vaut 2. Le nombre minimum de nœuds dans un arbre AVL de hauteur h >= 3 doit avoir deux sous-arbres minimum : un de hauteur h - 1 et l'autre de hauteur h. - 2. Ainsi,

G(h) = G(h - 1) + G(h - 2) + 1

Rappelons qu'un nombre de Fibonacci à l'indice i peut être décrit en utilisant la relation de récurrence F(i) = F(i - 1) + F(i - 2). Par conséquent, la fonction G(h) est essentiellement la même que F(i). On peut prouver que

h < 1,4405 log(n + 2) - 1,3277

où n est le nombre de nœuds dans l'arborescence. Par conséquent, la hauteur d'un arbre AVL est O(log n).

Les méthodes

search, insert et delete impliquent uniquement les nœuds le long d'un chemin dans l'arborescence. Les méthodes updateHeight et balanceFactor sont exécutées à un temps constant pour chaque nœud du chemin. La méthode balancePath est exécutée en temps constant pour un nœud du chemin. Ainsi, la complexité temporelle des méthodes search, insert et delete est O(log n).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!