Exercice 7 - complexité moyenne d'une recherche

Soit un ensemble $E = \{1, \ldots, n\}$ de $n$ clés. Nous voulons déterminer le nombre moyen $a_n$ de noeuds visités lors de la recherche d'une de ces clés dans un ABR contenant les clés de $E$. On suppose que les ordres d'insertion sont équiprobables. Par ailleurs, on considère que la probabilité de rechercher la clé $i \in E$ est $\frac{1}{n}$.

1. Montrer que la probabilité que la racine ait la clé $i$ est $\frac{1}{n}$.
2. Notons $a^i_n$ le nombre moyen de comparaisons nécessaires pour trouver une clé dans un arbre à $n$ clés dont la racine porte la clé $i$. Exprimer $a_n$ en fonction de $\{a_n^i \vert i \in E\}$.
3. On pose $a_0 = 0$. Combien valent $a^1_1$ et $a_1$ ?
4. Montrer que $$\forall i \in E, a^i_n = (a_{i-1} + 1)\frac{i-1}{n} + \frac{1}{n} + (a_{n-i} + 1)\frac{n-i}{n}$$
5. En déduire que $$a_n = 1 + \frac{2}{n^2}\sum_{i=1}^{n-1}ia_i$$
6. En déduire que $$a_n = \frac{1}{n^2}((n^2 - 1)a_ {n-1} + 2n - 1)$$
7. Utiliser le fait que $$log_2(n-1) = \frac{1}{ln2}\int_1^{n-1}\frac{dx}{x}$$ et que $$\frac{1}{n} \leq \int_{n-1}^n\frac{dx}{x}$$ pour prouver par récurrence qu'il existe $\alpha$ tel que $$a_n \leq \alpha log_2(n)$$
8. Quelle est la complexité moyenne de la recherche d'une clé de $E$ dans un ABR ?