\chapter{Les arbres:\\structures hiérarchiques}

\begin{exointro}{Lycée Camille Claudel, Blois}
On considère l'arbre suivant :

\Par

\begin{figure}
\begin{center}
\includegraphics{175_arbre-exintro01}
\end{center}
\end{figure}

\Par

On parcourt cet arbre en profondeur avec un ordre préfixe.

\begin{questions}
\item Quel est le résultat de l'opération obtenue si l'on tient compte des\linebreak priorités opératoires, c'est-à-dire du fait que la multiplication et la division sont prioritaires sur l'addition et la soustraction?

\item Implémenter cet arbre et retrouver le résultat de la question précédente à l'aide d'un programme écrit en Python.
\end{questions}
\vspace*{-1.5em}
\end{exointro}

\newpage

Les listes et tableaux sont des structures de données peu pratiques à manipuler dès lors que l'on souhaite effectuer des recherches sur leurs valeurs, ou même ajouter et supprimer des valeurs.

\begin{problematique}
Comment représenter un ensemble ordonné de clés de sorte à effectuer\linebreak simplement des opérations élémentaires?
\end{problematique}

\section{Notion d'arbres}

\begin{defin}
En informatique, un \textit{arbre} est est un graphe acyclique orienté connexe dont tout sommet est sommet d’arrivée d’au plus une arête.
\end{defin}

\begin{defins}[vocabulaire]
\begin{itemize}
\item Le seul sommet n’étant l’arrivée d’aucune arête d’un arbre est la \textit{racine}.
\item Les arêtes d'un arbre sont aussi appelées \textit{branches}.
\item Les sommets sont appelés les \textit{n\oe uds}.
\item Les sommets étant sommets d’arrivée d’une arête dont l’origine est le n\oe ud
N sont appelés \textit{sommets issus} de N.
\item Les n\oe uds issus d'un n\oe ud $N$ sont appelés les \textit{fils} de $N$. $N$ est alors appelé le \textit{père}.
\item Les n\oe uds d'un même niveau sont appelés les \textit{n\oe uds frères}.
\item Les n\oe uds n'ayant pas de fils sont aussi appelés des \textit{feuilles}.
\item La \textit{distance} d'un n\oe ud à un autre est le nombre de branches reliant l'un à l'autre.
\item La \textit{profondeur} d'un n\oe ud est la distance de la racine à ce n\oe ud.
\item La \textit{hauteur} de l'arbre est la plus grande distance de la racine à une feuille.
\item La \textit{taille} de l'arbre est le nombre de n\oe uds.
\item Une \textit{clé} est la valeur d'un n\oe ud.
\end{itemize}
\end{defins}
\index{Arbres!Hauteur}
\index{Arbres!Profondeur}
\index{Arbres!Taille}
\index{Arbres!Clé}

\begin{Remarque}
dans cet ouvrage, la convention utilisée est celle-ci: la hauteur d'un
arbre vide est égale à $-1$. Il existe cependant d'autres conventions (par exemple, hauteur de l'arbre vide égale à 0).
\end{Remarque}

\vspace*{-1em}
\enlargethispage*{2em}
\begin{Exemple}
on a représenté ci-dessous un arbre de hauteur 2 et de taille 9.
\Par
\begin{figure}
\begin{center}
\includegraphics{177_01-crs-arbre}
\figcaption{Représentation sagittale d'un arbre}
\label{arbre}
\end{center}
\end{figure}
\end{Exemple}

On peut représenter un arbre par une liste commençant par la racine et suivie d'une suite de listes représentant les différents chemins de l'arbre.

\begin{Exemple}
reprenons l'arbre de l'exemple précédent en ajoutant un autre niveau:

\Par

\begin{minipage}{0.6\linewidth}
\begin{figure}
\includegraphics{177_01-crs-arbre2}
\figcaption{Arbre à trois niveaux}
\end{figure}
\end{minipage}
\hfill
\begin{minipage}{0.35\linewidth}
Cet arbre pourra alors être implémenté par la liste:

\Par

{
\ttfamily
[ 'A' , 

\quad ['B', 

\qquad ['E' , 

\qquad\quad ['Z']

\qquad ] , 

\qquad ['F']

\quad ],

\quad ['C' ,

\qquad ['G' ,

\qquad\quad ['X'] ,

\qquad\quad ['Y']

\qquad ] ,

\qquad ['H'] ,

\qquad ['I']

\quad ],

['D'] 

]
}
\end{minipage}
\end{Exemple}


\section{Arbre binaire}
\index{Arbres!Binaires}
\subsection{Définitions}

\begin{defins}
Un arbre est dit \textit{binaire} si chaque n\oe ud admet au plus deux fils, que l'on appelle \textit{fils gauche} et \textit{fils droit}.

Si, pour tout n\oe ud de l'arbre, les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1, l'arbre est un \textit{arbre AVL}, du nom de Georgy Adelson-Velsky et Evgenii Landis, qui l'ont inventé en 1962.
\end{defins}
\index{Arbres!AVL}

\begin{defin}[sous-arbres gauche et droit]
Soit $T$ un arbre binaire. On appelle \textit{sous-arbre gauche} (resp. \textit{droit}) d'un n\oe ud l'arbre issu du fils gauche (resp. droit) de ce n\oe ud.
\end{defin}

%\begin{Exemple}on a représenté ci-dessous un arbre binaire de hauteur 3 et de taille 9.\Par\begin{figure}\begin{center}\includegraphics{01-crs-arbre-binaire}\figcaption{Représentation d'un arbre binaire}\end{center}\end{figure}\Par\ParC'est un arbre AVL.\end{Exemple}

\begin{Exemple}
on a représenté ci-dessous un arbre binaire de hauteur 3 et de taille 9.
\begin{figure}
\begin{center}\label{crs01ArbreBinaire}
\includegraphics{178_01-crs-sous-arbres}
\figcaption{Représentation des sous-arbres gauche et droit de la racine}
\end{center}
\end{figure}
\end{Exemple}

\subsection{Propriétés sur les arbres binaires}

\begin{prop}
Un arbre binaire de hauteur $h$ admet au plus $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ n\oe uds.
\end{prop}

\newpage

\begin{props}
\begin{itemize}
\item Un arbre binaire ayant $n$ n\oe uds a une hauteur $h$ telle que : 
\[
\log_2(n+1) - 1 \leqslant h \leqslant n
\]
c'est-à-dire:
\[
\dfrac{\ln (n+1)}{\ln 2} - 1 \leqslant h \leqslant n.
\]

\item Tout arbre binaire ayant $f$ feuilles a une hauteur $h$ telle que:
\[
h \geqslant \log_2(f).
\]

\item Soit un arbre binaire ayant $f$ feuilles et $n$ n\oe uds. Alors,
\[
\log_2(f) \leqslant \log_2\left(\dfrac{n+1}{2}\right).
\]
\end{itemize}
\end{props}

\subsection{Arbre Binaire de Recherche (ABR)}
\index{Arbres!ABR}

\NathanLiveVideo[\PictoVideo\ Retrouvez en vidéo la notion d'arbre binaire de recherche.]{arbres binaires}{https://media.prepamath.fr/ILTNSIch06crs01}

\qrset{height=1.1cm,version=5}\rput(-1,0.3){
\psframebox{\qrcode{https://media.prepamath.fr/ILTNSIch06crs01}}}
\vspace*{-20pt}


\begin{defin}
Un \textit{arbre binaire de recherche}, en abrégé : ABR, est un arbre vide ou un arbre binaire dont:
\begin{itemize}
\item tous les n\oe uds sont étiquetés par des nombres;
\item la racine est supérieure ou égale à tout n\oe ud du sous-arbre gauche;
\item la racine est inférieure à tout n\oe ud du sous-arbre droit;
\item les deux sous-arbres de la racine sont eux-mêmes des ABR.
\end{itemize}
\end{defin}
\enlargethispage*{5em}
\begin{Exemple}
l'abre binaire ci-dessous est un ABR.
\Par
\begin{figure}
\begin{center}
\includegraphics{179_01-crs-ABR}
\figcaption{Représentation d'un ABR}
\end{center}
\end{figure}
\end{Exemple}


\section{Représentations des arbres binaires}

\subsection{Représentation contigüe}

On peut représenter un arbre binaire à l'aide d'un tableau (une liste) à une\linebreak dimension.


Si \texttt{L} est cette liste:
\begin{itemize}
\item \texttt{L[0]} est la racine;
\item \texttt{L[1]} est le fils gauche de la racine (notons-le R.g);
\item \texttt{L[2]} est le fils droit de la racine (notons-le R.d);
\item \texttt{L[3]} est le fils gauche de R.g;
\item \texttt{L[4]} est le fils droit de R.g;
\item \texttt{L[5]} est le fils gauche de R.d;
\item \texttt{L[6]} est le fils droit de R.d;
\item etc.
\end{itemize}

\vspace*{-3mm}
\index{Arbre!Représentation!par une liste}
\begin{Exemple}
la représentation de l'arbre de la figure \ref{crs01ArbreBinaire} page \pageref{crs01ArbreBinaire} est donnée ci-dessous.

\Par

\begin{center}
\begin{tabular}{|L|*{13}{Zc|}}
\tabulartitle\hline
Rang & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7  &8&9&10&11&12\\
\hline
Valeur & A & B & C & D & E &  & F & & & G & H & I & \\
\hline
\end{tabular}

\Par

\ttfamily
L = [A , B , C , D , E ,  , F , , , G , H , I , ]
\end{center}
\end{Exemple}

\subsection{Représentation avec une classe}

\subsubsection{Première possibilité}
\index{Arbre!Représentation!par une classe}
Nous pouvons représenter un arbre binaire à l'aide d'une classe \texttt{node} (par exemple) contenant trois champs:
\begin{itemize}
\item la valeur du n\oe ud;
\item le parent du n\oe ud;
\item la position du n\oe ud par rapport à son parent (gauche ou droit)
\end{itemize}

puis d'une classe \texttt{tree} contenant une liste des n\oe uds, dont le premier élément est la racine.

Si nous implémentons en Python l'arbre de la figure \ref{crs01ArbreBinaire}, cela donne:\enlargethispage*{3em}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/06-01.py}}}
\vspace*{-10pt}
\begin{listing}{}{06-01-1.txt}\end{listing}
\newpage
\begin{listing}{}{06-01-2.txt}\end{listing}
\Par
qui affiche: { \ttfamily D est le fils Gauche de B}


\subsubsection{Autre possibilité}

Nous pouvons utiliser la récursivité implicitement liée aux  arbres binaires. Ainsi, pour l'arbre de la figure \ref{crs01ArbreBinaire}), on peut définir de manière simple une classe \texttt{Arbre} comme dans le code donné page suivante.


\label{classe-arbre}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/06-02.py}}}
\vspace*{-10pt}
\begin{listing}{}{06-02-1.txt}\end{listing}
\newpage
\begin{listing}{}{06-02-2.txt}\end{listing}

\Par

Ce programme affiche :

\Par
\begin{minipage}{\textwidth}
\ttfamily
A\\
\hspace*{5mm}B\\
\hspace*{10mm}D\\
\hspace*{10mm}E\\
\hspace*{15mm}G\\
\hspace*{15mm}H\\
\hspace*{5mm}C\\
\hspace*{10mm}-\\
\hspace*{10mm}F\\
\hspace*{15mm}I\\
\hspace*{15mm}-
\end{minipage}

\section{Algorithmique}
\enlargethispage*{3em}

\subsection{Calcul de la taille d'un arbre binaire}

Ce calcul se fait à l'aide d'un algorithme récursif.

\newpage

\begin{algorithme}{}
fonction taille(arbre):
\quad Si arbre est vide:
\qquad retourner 0
\quad Sinon:
\qquad G $\leftarrow$ taille(gauche(arbre))
\qquad D $\leftarrow$ taille(droit(arbre))
\qquad return 1 + G + D
\end{algorithme}

\Par

Ici, \texttt{gauche(arbre)} représente le sous-arbre gauche du n\oe ud sur lequel nous sommes et \texttt{droit(arbre)} son sous-arbre droit.

\subsection{Calcul de la hauteur d'un arbre binaire}

On utilise ici le même type d'algorithme que pour le calcul de la taille, en\linebreak convenant de prendre $-1$ pour hauteur d'un arbre vide (où seule la racine existe).

\begin{algorithme}{}
fonction hauteur(arbre):
\quad Si arbre est vide:
\qquad retourner -1
\quad Sinon:
\qquad G $\leftarrow$ hauteur(gauche(arbre))
\qquad D $\leftarrow$ hauteur(droit(arbre))
\qquad return 1 + max(G,D)
\end{algorithme}

\subsection{Parcours en profondeur d'un arbre binaire}
\index{Arbres!Parcours en profondeur}

\begin{minipage}{6cm}
\begin{figure}
\begin{center}
\includegraphics{183_01-crs-parcours-arbre}
\figcaption{Parcours d'un arbre binaire}
\label{parcours-arbre}
\end{center}
\end{figure}
\end{minipage}
\hfill
\begin{minipage}{\dimexpr\linewidth-6.5cm}
Parcourir un arbre binaire signifie accéder à l'information contenue dans les n\oe uds.

Nous allons donc imaginer que l'on parcourt l'arbre de la façon\linebreak indiquée ci-contre.
\end{minipage}



\Par

Ce parcours est appelé \textit{parcours en profondeur} de l'arbre.

\Par

Il existe trois façons d'énumérer les n\oe uds.

\subsubsection{Ordre préfixe}
\index{Arbres!Parcours en profondeur!Ordre préfixe}

On liste les n\oe uds dans l'ordre dans lequel on les rencontre pour la première fois.

\begin{Exemple}
l'arbre de la figure \ref{parcours-arbre} donne :
\Par
\begin{center}
A -- B -- D -- E -- G -- H -- C -- F -- I
\end{center}
\end{Exemple}


\begin{algorithme}{Algorithme (récursif) de parcours préfixe}
ParcoursPrefixe(arbre):
\quad Afficher la clé de l'arbre
\quad ParcoursPrefixe(gauche(arbre))
\quad ParcoursPrefixe(droit(arbre))
\end{algorithme}\label{algo-ordre-prefixe}

\subsubsection{Ordre postfixe}
\index{Arbres!Parcours en profondeur!Ordre postfixe}

On liste les n\oe uds dans l'ordre dans lequel on les rencontre pour la dernière fois.
\Par
\begin{Exemple}
l'arbre de la figure \ref{parcours-arbre} donne :
\begin{center}
D -- G -- H -- E -- B -- I -- F -- C -- A
\end{center}
\end{Exemple}

\begin{algorithme}{Algorithme (récursif) de parcours postfixe}
ParcoursPostfixe(arbre):
\quad ParcoursPostfixe(gauche(arbre))
\quad ParcoursPostfixe(droit(arbre))
\quad Afficher la clé de l'arbre
\end{algorithme}\label{algo-ordre-postfixe}

\subsubsection{Ordre infixe}
\index{Arbres!Parcours en profondeur!Ordre infixe}

On liste les n\oe uds selon la règle suivante :
\begin{itemize}
\item chaque n\oe ud sans fils gauche est répertorié la première fois qu'on le rencontre;
\item chaque n\oe ud comportant un fils gauche est répertorié la seconde fois qu'on le\linebreak rencontre;
\end{itemize} 

\newpage

\begin{Exemple} 
pour l'arbre de la figure \ref{parcours-arbre}, nous allons avant tout faire un tableau.
\begin{center}
\begin{tabular}{|Zc|Zc|Zc|Zc|}
\tabulartitle\hline
Sommets & Fils gauche & Répertorié la... & Parcours\\
\hline
A & Oui & 2\up{nde} fois & \\
\hline
B & Oui & 2\up{nde} fois & \\
\hline
D & Non & 1\iere{} fois & D \\
\hline
B & Oui & 2\up{nde} fois & D -- B \\
\hline
E & Oui & 2\up{nde} fois & D -- B \\
\hline
G & Non & 1\iere{} fois & D -- B -- G\\
\hline
E & Oui & 2\up{nde} fois & D -- B -- G -- E\\
\hline
H & Non & 1\iere{} fois & D -- B -- G -- E -- H\\
\hline
E & Oui & 2\up{nde} fois &  D -- B -- G -- E -- H \\
\hline
B & Oui & 2\up{nde} fois & D -- B -- G -- E -- H  \\
\hline
A & Oui & 2\up{nde} fois & D -- B -- G -- E -- H -- A\\
\hline
C & Non & 1\iere{} fois & D -- B -- G -- E -- H -- A -- C \\
\hline
F & Oui & 2\up{nde} fois & D -- B -- G -- E -- H  -- A -- C \\
\hline
I & Non & 1\iere{} fois & D -- B -- G -- E -- H  -- A -- C -- I \\
\hline
F & Oui & 2\up{nde} fois & D -- B -- G  -- E -- H -- A -- C -- I -- F\\
\hline
C & Non & 1\iere{} fois & D -- B -- G -- E -- H  -- A -- C -- I -- F \\
\hline
A & Oui & 2\up{nde} fois & D -- B -- G -- E -- H -- A -- C -- I -- F\\
\hline
\end{tabular}
\end{center}
\end{Exemple}


\begin{algorithme}{Algorithme (récursif) de parcours infixe}
ParcoursInfixe(arbre):
\quad ParcoursInfixe(gauche(arbre))
\quad Afficher la clé de l'arbre
\quad ParcoursInfixe(droit(arbre))
\end{algorithme}
\label{ordre-infixe}

\subsection{Parcours en largeur}
\index{Arbres!Parcours en largeur}
Reprenons l'arbre de la figure \ref{crs01ArbreBinaire} page \pageref{crs01ArbreBinaire}.

\Par

L'idée consiste à lister chaque n\oe ud-fils niveau par niveau.

Nous avons présenté page suivante les différentes étapes.

\newpage

\begin{tabular}{Zc@{\hspace*{1cm}}Zc}
\includegraphics{186_01-crs-parcours-largeur-01} & 
\includegraphics{186_01-crs-parcours-largeur-02} \\
\'Etape 1 & \'Etape 2\\[1cm]
\includegraphics{186_01-crs-parcours-largeur-03} & 
\includegraphics{186_01-crs-parcours-largeur-04} \\
\'Etape 3 & \'Etape 4\\[1cm]
\includegraphics{186_01-crs-parcours-largeur-05} & 
\includegraphics{186_01-crs-parcours-largeur-06} \\
\'Etape 5 & \'Etape 6
\end{tabular}


L'algorithme de parcours en largeur est basé sur une file.

\begin{algorithme}{Algorithme de parcours en largeur}
F est une file vide
P est une liste vide
Enfiler racine à F
Ajouter racine à P
Tant que F non vide:
\quad U $\leftarrow$ tête de F
\quad Pour V fils de U:
\qquad Enfiler V à F
\qquad Ajouter V à P
\quad Fin du Pour
\quad Défiler U de F
Fin du Tant que
\end{algorithme}\label{algo-largeur}

\subsection{Recherche dans un ABR}

La structure d'un ABR facilite grandement les recherches, et c'est la raison pour laquelle cette structure de données est intéressante. En effet, on sait par définition que chaque clé de n\oe uds-fils-gauches est inférieure à celle du n\oe ud courant et que chaque clé de n\oe uds-fils-droits est supérieure. Cela donne l'algorithme suivant :
\enlargethispage*{5em}

\begin{algorithme}{Algorithme (récursif) de recherche dans un ABR}
Recherche(ABR,val):
\quad Si ABR est vide:
\qquad Retourner Faux
\quad Sinon:
\qquad r $\leftarrow$ racine de ABR
\qquad Si val = r:
\qquad\quad Retourner ABR
\qquad Sinon:
\qquad\quad Si val $\leqslant$ r:
\qquad\qquad Retourner Recherche(gauche(ABR),val)
\qquad\quad Sinon:
\qquad\qquad Retourner Recherche(droite(ABR),val)
\qquad\quad Fin du Si val $\leqslant$ r
\qquad Fin du Si val = r
\quad Fin du Si ABR est vide
\end{algorithme}

\begin{prop}
Le coût d'une recherche dans un ABR est en $O(h)$, où $h$ est la hauteur de l'arbre.
%Le coût d'une recherche dans un ABR équilibré est en $O(\log h)$. <<- il faudrait définir ce que c'est avant... HP ?
\end{prop}

\subsection{Insertion dans un ABR}

Pour insérer une clé dans un ABR, il suffit de faire une recherche et de faire l'insertion à l'endroit où la recherche est infructueuse.

\begin{algorithme}{Algorithme d'insertion dans un ABR}
Insere(ABR,clé):
\quad Si ABR est vide:
\qquad return CreerABR(clé)
\quad Sinon:
\qquad Si clé $\leqslant$ racine(ABR):
\qquad\quad G $\leftarrow$ Insere(gauche(ABR),clé)
\qquad\quad gauche(ABR) $\leftarrow$ G
\qquad\quad Retourner ABR
\qquad Sinon:
\qquad\quad D $\leftarrow$ Insere(droit(ABR),clé)
\qquad\quad droit(ABR) $\leftarrow$ D
\qquad\quad Retourner ABR
\qquad Fin du Si clé $\leqslant$ racine(ABR)
\quad Fin du Si ABR est vide
\end{algorithme}

\begin{Remarque}
la fonction \texttt{CreerABR} est une fonction qui crée un arbre à partir d'une valeur; quant à \texttt{gauche(ABR)} et \texttt{droit(ABR)}, ce sont deux fonctions qui retournent respectivement les fils gauche et droit de ABR.
\end{Remarque}


\begin{aretenir}
\begin{tabular}{|Z{m{27mm}}|Z{m{73mm}}|}
\hline
Arbre binaire & Chaque n\oe ud admet au plus deux fils : un fils gauche et un fils droit.\\
\hline
Arbre AVL & Pour tout n\oe ud de l'arbre, les hauteurs des sous-arbre gauche et droit diffèrent d'au plus 1.\\
\hline
Arbre Binaire de Recherche (ABR) &
\begin{minipage}{\linewidth}
Arbre vide ou arbre étiqueté par des nombres où:
\begin{itemize}
\item la racine est supérieure ou égale à tout n\oe ud du sous-arbre gauche;
\item la racine est inférieure à tout n\oe ud du sous-arbre droit;
\item les deux sous-arbres de la racine sont eux-mêmes des ABR.
\end{itemize}
\end{minipage}\\[44pt]
\hline
\end{tabular}
\end{aretenir}

\newpage

\begin{solintro}
\begin{questions}
\item Le parcours en profondeur est le parcours suivant:

\Par

\begin{figure}
\begin{center}
\includegraphics{189_arbre-exintro02}
\end{center}
\end{figure}

\Par

Il donne alors l'opération: $3 + 4 \times 5 \div 2 - 6 + 4 \times 9 + 2 = 45$.

\item Nous pouvons nous inspirer de la classe \texttt{Arbre} de la page \pageref{classe-arbre} et de sa méthode \texttt{Affiche} (qui permet de parcourir en profondeur l'arbre avec un ordre préfixe). On obtient ainsi le programme suivant:

\qrset{height=1.1cm,version=5}\rput(-2,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/06-03.py}}}
\vspace*{-10pt}
\begin{listing}{}{06-03-1.txt}\end{listing}

\BreakWithoutItem

\begin{listing}{}{06-03-2.txt}\end{listing}

\Par\Par

Une fois l'arbre défini, on construit une liste \texttt{L} à l'aide de la méthode \texttt{parcours}, dans laquelle on ajoute tous les n\oe uds de l'arbre dans l'ordre voulu. La liste \texttt{L} est alors transformée en chaîne de caractères (avec la méthode \texttt{join}) afin de pouvoir l'interpréter comme un calcul (avec la fonction \texttt{eval}).
\end{questions}
\end{solintro}