\documentclass[a4paper]{article}
\usepackage{entete}
\usepackage{algorithm,algofr}
\usepackage[table]{xcolor}
\author{Référence~: Cormen, p.357 de la seconde édition}
\title{Arbres binaires de recherche optimaux}
\date{2011-2012}
\DeclareMathOperator{\prof}{Prof}
\begin{document}
\maketitle

On s'intéresse ici à optimiser les arbres binaires de recherche quand on connait la probabilité pour chaque clef d'être recherchée.

On se donne $n$ clefs distinctes triées dans l'ordre croissant $k_1 < \cdots < k_n$, où pour tout $i$, $k_i$ a une probabilité $p_i$ d'être recherchée.

On rajoute aussi $n+1$ clefs factices $d_0,\ldots,d_n$ représentant les recherches qui ne sont aucun des $k_i$.

$d_0$ représente toutes les valeurs inférieures à $k_1$, $d_n$ celle supérieures à $k_n$, et $d_i$ celles comprises entre $k_i$ et $k_{i+1}$. On se donne de plus une probabilité $q_i$ que la recherche soit dans $d_i$.

Les nœuds internes de l'arbre seront les $k_i$, et les feuilles les $d_i$.

On a donc 
$$\sum_{i=1}^n p_i + \sum_{i=0}^n q_i = 1.$$

Le coût moyen d'une recherche dans notre arbre sera
$$1 + \sum_{i=1}^n \prof(k_i)p_i + \sum_{i=0}^n \prof(d_i) q_i.$$

Un arbre binaire de recherche sera dit {\em optimal} si ce coût moyen est minimal. On abrège en "ABRO".

La recherche d'un ABRO en listant tous les arbres possibles a une complexité bien trop grande, on va donc essayer un algorithme de programmation dynamique.

On remarque pour cela que tout sous-arbre de notre arbre {\em doit} être optimal~: sinon, on le remplace par un optimal, faisant ainsi baisser le coût total.

Le sous-problème à résoudre est donc, étant donnés $i\geqslant 1$ et $i-1 \leqslant j \leqslant n$ un ABRO contenant les clefs $k_i,\ldots,k_j$.

Soit $e[i,j]$ le coût d'un arbre contenant $k_i,\ldots,k_j$.

Si $j=i-1$, alors il n'y a que la clef factice $d_{i-1}$ dans l'arbre~: le coût moyen est $q_{i-1}$.

Sinon, $j\geqslant i$. On choisit un nœud $k_r$, $i\leqslant r \leqslant j$, et on construit l'arbre de racine $k_r$. Le sous-arbre gauche de $k_r$ contiendra les clefs $k_i,\ldots,k_{r-1}$, et le sous arbre droit les clefs $k_{r+1},\ldots,k_j$.

Quand on fait "descendre" un sous-arbre, on augmente la profondeur de ce sous-arbre de 1, on donc on augmente le coût de 
$$w(i,j) = \sum_{k=i}^j p_k + \sum_{k=i-1}^j q_k.$$

On obtient donc la formule~:

$$e[i,j] = p_r + e[i,r-1]+w(i,r-1)+e[r+1,j] + w(r+1,j).$$

On remarque que 
$$w(i,j) = w(i,r-1)+p_r+w(r+1,j),$$ et donc
$$e[i,j] = e[i,r-1]+e[r+1,j] + w(i,j).$$

Cette formule est valide si on a choisi la bonne racine pour notre sous-arbre. On optimise donc~:

$$e[i,j] = 
\left\{
\begin{array}{ll}
    q_{i-1} & \text{si } j =i-1 \\
    \min_{i\leqslant r \leqslant j} e[i,r-1]+e[r+1,j]+w(i,j) & \text{si } i\leqslant j
\end{array}
\right.$$

Pour garder une trace de notre construction, on définit $racine[i,j]$ comme l'indice de la racine optimale pour le sous-arbre contenant $k_i,\ldots,k_j$.

On va maintenant utiliser la programmation dynamique pour calculer $e[1,n]$.

\begin{rmq}
    Plutôt que de calculer tous les $w(i,j)$ à chaque fois, on crée un tableau défini par 
    $$\left\{
    \begin{array}{l}
        w(i,i-1) = q_{i-1} \\
        w(i,j) = w(i,j-1) + p_j+q_j
    \end{array}
    \right.$$
\end{rmq}

On a donc l'algorithme suivant~:

\begin{algorithm}[!h]
    \caption{ABRO}
    \label{ABRO}
    \begin{algorithmic}
        \REQUIRE $p,q$ probabilités, $n$ nombre de clefs
        \FOR {$i=1$ à $n+1$}
            \STATE $e[i,i-1] \leftarrow q_{i-1}$
            \STATE $w[i,i-1] \leftarrow q_{i-1}$
        \ENDFOR
        \FOR {$\ell=1$ à $n$}
            \FOR {$i=1$ à $n-\ell+1$}
                \STATE $j \leftarrow i+\ell-1$
                \STATE $e[i,j] \leftarrow \infty$
                \STATE $w[i,j] \leftarrow w[i,j-1]+p_j+q_j$
                \FOR {$r=i$ à $j$}
                    \STATE $t\leftarrow e[i,r-1]+e[r+1,j]+w[i,j]$
                    \IF {$t < e[i,j]$}
                        \STATE $e[i,j] \leftarrow t$
                        \STATE $racine[i,j] \leftarrow r$
                    \ENDIF
                \ENDFOR
            \ENDFOR
        \ENDFOR
        \STATE \RETURN $e$ et $racine$

    \end{algorithmic}
\end{algorithm}


Les trois boucles imbriquées nous donnent une complexité en $\mathcal O (n^3)$.
\end{document}
