Une médiane d'une AVL. Comment profiter de l'AVL?

Voici la source de ma question.

Étant donné un arbre à équilibrage automatique (AVL), codez une méthode qui renvoie la médiane.

(Médiane: la valeur numérique séparant la moitié supérieure d'un échantillon de données de la moitié inférieure. Exemple: si la série est

2, 7, 4, 9, 1, 5, 8, 3, 6

alors la médiane est 5.)

Je peux proposer la solution suivante:

1. Parcourez l'arbre donné, retournez le nombre d'éléments.
2. Traversez n / 2 + 1(si nc'est impair) l'arbre en appliquant à nouveau une marche dans l'arbre dans l'ordre. La valeur du n / 2 + 1e élément est la médiane.

Mais je peux le faire avec un arbre de recherche binaire, non? Existe-t-il un meilleur algorithme pour un AVL?

Si vous modifiez l'arborescence AVL en stockant la taille de la sous-arborescence à chaque nœud plutôt que juste sa hauteur, alors vous pouvez trouver la médiane dans le temps $O(\log n)$en utilisant le fait que l'arbre est équilibré. Pour ce faire, vous écrivez une procédure plus générale Sélectionnez qui accepte un nœud$v$ et un certain nombre $k$et trouve le $k$e plus petit nœud du sous-arbre enraciné à $v$.

Supposons que le sous-arbre gauche (le cas échéant) ait $L$nœuds. Si$k \leq L$puis nous rentrons dans le sous-arbre gauche. Si$k = L+1$ puis nous revenons $v$. Sinon, nous rentrons dans le sous-arbre droit, réduisant$k$ par $L+1$.

Le temps d'exécution de cet algorithme est linéaire dans la hauteur de l'arbre, qui est $O(\log n)$.

AVL est un arbre de recherche binaire avec une propriété spéciale: c'est un arbre auto-équilibré. Sa hauteur est toujours logarithmique. L'arbre binaire ordinaire dans certains pires scénarios peut être une liste liée (si vous ajoutez des données triées), sa hauteur est donc n. L'arbre AVL dans le pire des cas est l'arbre fibonacci.