\documentclass[xcolor,10pt]{beamer}

\usepackage{pgf}
\usepackage{graphicx,ulem}
\usepackage{stmaryrd}
\usepackage{amssymb,amsmath,amsxtra,amstext}
\usepackage{float}
\usepackage{multirow}
\usepackage[utf8]{inputenc}
\usepackage{tikz,pgflibraryarrows,pgffor,pgflibrarysnakes,pgflibraryshapes}
\usetikzlibrary{automata,backgrounds,fit,patterns,decorations}
\usepackage{xcolor}
\usepackage{xspace}
\usepackage{pifont}
\usepackage{dsfont}


\usepackage{defs}

\usepackage{graphicx}
 \newcommand{\what}{Chapitre 1 : Les arbres binaires et tas -- Informatique pour tous -- MP}

\usepackage{beamerthemeVertecs}

\title[]{Chapitre 1 : Les arbres binaires et tas}
%\author[Am\'elie Stainer]{\footnotesize{Am\'elie Stainer}}

%\institute{Universit\'e de Rennes 1, France}
\date{Informatique pour tous -- MP}


\begin{document}


\setlength{\unitlength}{4mm}


\frame{\titlepage}

\frame{\frametitle{Structure arborescente : motivation}
\begin{itemize}
\vfill
\item arbres généalogiques
\vfill
\item tournois sportifs
\vfill
\item probabilités
\vfill
\item stockage d'expressions algébriques
\vfill
\item théorie des jeux...
\vfill
\end{itemize}
}

\begin{frame}<beamer>
    \frametitle{Table des matières}
    \tableofcontents
  \end{frame}

\section{Définition récursive des arbres binaires}
\frame{\frametitle{Définition récursive des arbres binaires}
{\bf Définition :} un arbre binaire étiqueté est \pause
\begin{itemize}
\item soit l'arbre vide\pause
\item soit de la forme $a=[e,fils\_g,fils\_d]$ où\pause
\begin{itemize}
\item $e \in E$ : étiquette de la racine\pause
\item $fils\_g$, $fils\_d$ : arbres binaires étiquetés disjoints\pause
\end{itemize}
\end{itemize}

\vspace{.2cm}

{\bf Rq :} on peut définir des arbres avec plus de fils (liste).\pause

\vspace{.5cm}

{\bf Représentation graphique :}\pause

\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,1.5) node [circle,draw,inner sep=1.5pt] (l0b) {$e$};
\draw(-.5,.8) node (l1b) {$fils\_g$};
\draw(.5,.8) node (l2b) {$fils\_g$};

\draw (l0b) -- (l1b);
\draw (l0b) -- (l2b);

\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$e$};
\draw(-.5,-.7) node (l1) {$vide$};
\draw(.5,-.7) node (l2) {$vide$};

\draw(0,-1.5) node [circle,draw,inner sep=1.5pt] (l3) {$e$};

\draw[dashed] (l0) -- (l1);
\draw[dashed] (l0) -- (l2);

\end{tikzpicture}\pause\hfill\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$1$};
\draw(-1,-.7) node [circle,draw,inner sep=1.5pt] (l1) {$2$};
\draw(1,-.7) node [circle,draw,inner sep=1.5pt] (l2) {$3$};

\draw(1,-2) node (l7) {};

\draw (l0) -- (l1);
\draw (l0) -- (l2);
\end{tikzpicture}\pause\hfill\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$1$};
\draw(-1,-.7) node [circle,draw,inner sep=1.5pt] (l1) {$2$};
\draw(1,-.7) node [circle,draw,inner sep=1.5pt] (l2) {$3$};
\draw(.4,-1.4) node [circle,draw,inner sep=1.5pt] (l3) {$4$};
\draw(0,-2.1) node [circle,draw,inner sep=1.5pt] (l4) {$5$};
\draw(0.8,-2.1) node [circle,draw,inner sep=1.5pt] (l5) {$6$};

\draw(1,-3) node (l7) {};

\draw (l0) -- (l1);
\draw (l0) -- (l2);
\draw (l2) -- (l3);
\draw (l3) -- (l5);
\draw (l3) -- (l4);

\end{tikzpicture}
}
\frame{\frametitle{Définition récursive des arbres binaires}

\begin{tabular}{ccc}\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$1$};
\draw(-1,-.7) node [circle,draw,inner sep=1.5pt] (l1) {$2$};
\draw(1,-.7) node [circle,draw,inner sep=1.5pt] (l2) {$3$};
\draw(.4,-1.4) node [circle,draw,inner sep=1.5pt] (l3) {$4$};
\draw(0,-2.1) node [circle,draw,inner sep=1.5pt] (l4) {$5$};
\draw(0.8,-2.1) node [circle,draw,inner sep=1.5pt] (l5) {$6$};

\draw(1.5,-2) node (l7) {};
\draw (l0) -- (l1);
\draw (l0) -- (l2);
\draw (l2) -- (l3);
\draw (l3) -- (l5);
\draw (l3) -- (l4);


\end{tikzpicture}&\visible<2->{\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$1$};
\draw(-1,-.7) node [circle,draw,inner sep=1.5pt] (l1) {$2$};
\draw(-.4,-1.4) node [circle,draw,inner sep=1.5pt] (l3) {$3$};
\draw(-.7,-2.1) node [circle,draw,inner sep=1.5pt] (l4) {$4$};

\draw(-1.5,-2) node (l7) {};
\draw(1.5,-2) node (l7) {};
\draw (l0) -- (l1);
\draw (l1) -- (l3);
\draw (l3) -- (l4);

\end{tikzpicture}}&\visible<3->{\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$1$};
\draw(-1,-.7) node [circle,draw,inner sep=1.5pt] (l1) {$2$};
\draw(1,-.7) node [circle,draw,inner sep=1.5pt] (l2) {$3$};
\draw(-1.5,-1.4) node [circle,draw,inner sep=1.5pt] (l3) {$4$};
\draw(-.5,-1.4) node [circle,draw,inner sep=1.5pt] (l4) {$5$};
\draw(.5,-1.4) node [circle,draw,inner sep=1.5pt] (l5) {$6$};
\draw(1.5,-1.4) node [circle,draw,inner sep=1.5pt] (l6) {$7$};
\draw(-1.8,-2.1) node [circle,draw,inner sep=1.5pt] (l7) {$8$};
\draw(-1.2,-2.1) node [circle,draw,inner sep=1.5pt] (l8) {$9$};
\draw(-.8,-2.1) node [circle,draw,inner sep=1.5pt] (l9) {\scriptsize{$10$}};
\draw(-.2,-2.1) node [circle,draw,inner sep=1.5pt] (l10) {\scriptsize{$11$}};
\draw(.2,-2.1) node [circle,draw,inner sep=1.5pt] (l11) {\scriptsize{$12$}};

\draw (l0) -- (l1);
\draw (l0) -- (l2);
\draw (l1) -- (l3);
\draw (l1) -- (l4);
\draw (l2) -- (l5);
\draw (l2) -- (l6);
\draw (l3) -- (l7);
\draw (l3) -- (l8);
\draw (l4) -- (l9);
\draw (l4) -- (l10);
\draw (l5) -- (l11);

\end{tikzpicture}}\\
Exemple 1&\visible<2->{Exemple 2}&\visible<3->{Exemple 3}\end{tabular}

\vspace{.5cm}

\visible<4->{{\bf Vocabulaire :}}
\begin{itemize}
\visible<5->{\item $fils\_g$ et $fils\_d$ sont les {\bf fils gauche et droit} de $a$}
\visible<6->{\item $a$ est le {\bf père} de $fils\_g$ et $fils\_d$}
\visible<7->{\item les triplets $[e,fils\_g,fils\_d]$ constituant $a$ sont les {\bf n\oe uds}}
\visible<8->{\item le seul n\oe ud qui n'a pas de père est la {\bf racine}}
\visible<9->{\item les n\oe uds avec fils vides sont les {\bf feuilles}}
\end{itemize}
}

\frame{\frametitle{Notion de hauteur}
\begin{definition}[Hauteur]
\begin{itemize}\pause
\item La hauteur (ou profondeur, ou niveau) d'un n\oe ud est définie par :\pause

$$h(x)=\left\{\begin{array}{ll}0& \mbox{ si } x \mbox{ est la racine }\\
1 + h(y) & \mbox{ si } y \mbox{ est le père de }x\end{array}\right.$$\pause
\item La hauteur d'un arbre est la hauteur maximale d'un de ces n\oe uds\pause
\end{itemize}
\end{definition}

\vspace{.5cm}

{\bf Propriété :} la hauteur $h$ d'un arbre à $n$ n\oe uds vérifie \pause

\vspace{-.3cm}

$$\lfloor \log_2 n \rfloor \le h \le n-1$$



}
\frame{\frametitle{Notion de hauteur}
{\bf Propriété :} la hauteur $h$ d'un arbre à $n$ n\oe uds vérifie 

\vspace{-.3cm}

$$\lfloor \log_2 n \rfloor \le h \le n-1$$

\vspace{.2cm}

{\bf Preuve}

\begin{itemize}
\item \visible<1->{\underline{majoration de $h$} : }

\begin{itemize}
\item \visible<2->{$h+1$ niveaux}

\item \visible<3->{au moins $h+1$ n\oe uds}

\item \visible<4->{$n\ge h+1$}

\item \visible<5->{$h\le n-1$}
\end{itemize} 
\item \visible<1->{\underline{minoration de $h$} :}
\begin{itemize}
\item \visible<6->{Montrons ($\mathcal{P}_k$) : $\forall k\in\mathbb{N}$, il y a au plus $2^{k}$ n\oe uds au niveau $k$}

\visible<7->{(I) $k=0$ : une seule racine ($2^0=1$)}

\visible<8->{(H) soit $k\in\mathbb{N}$, tq ($\mathcal{P}_k$), chaque n\oe ud a au plus $2$ fils, ($\mathcal{P}_{k+1}$) vraie}

\visible<9->{(C) ($\mathcal{P}_k$) est vrai pour tout $k\in\mathbb{N}$}
\item \visible<10->{$\sum_{k=0}^{h}2^{k}\geq n$, donc $2^{h+1}-1\geq n$, donc $2^{h+1}> n$}

\visible<11->{Ainsi $\log
_{2}n<h+1$, donc $\lfloor \log_2 n \rfloor \le h$.}
\end{itemize}
 
\end{itemize}
}

\frame{\frametitle{Arbres parfaits}
{\bf Définition :} un arbre est {\bf parfait} : \pause
\begin{itemize}
\item si tous ses niveaux sont remplis\pause
\item sauf éventuellement le dernier\pause
\item le dernier niveau est groupé à gauche\pause
\end{itemize}

\vspace{.5cm}

{\bf Propriété :} 

\hfill la hauteur d'un arbre parfait à $n$ n\oe uds est exactement $\lfloor \log_2 n \rfloor$

\vspace{.5cm}\pause

{\bf Exemple 3 :}

\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$1$};
\draw(-1,-.7) node [circle,draw,inner sep=1.5pt] (l1) {$2$};
\draw(1,-.7) node [circle,draw,inner sep=1.5pt] (l2) {$3$};
\draw(-1.5,-1.4) node [circle,draw,inner sep=1.5pt] (l3) {$4$};
\draw(-.5,-1.4) node [circle,draw,inner sep=1.5pt] (l4) {$5$};
\draw(.5,-1.4) node [circle,draw,inner sep=1.5pt] (l5) {$6$};
\draw(1.5,-1.4) node [circle,draw,inner sep=1.5pt] (l6) {$7$};
\draw(-1.8,-2.1) node [circle,draw,inner sep=1.5pt] (l7) {$8$};
\draw(-1.2,-2.1) node [circle,draw,inner sep=1.5pt] (l8) {$9$};
\draw(-.8,-2.1) node [circle,draw,inner sep=1.5pt] (l9) {\scriptsize{$10$}};
\draw(-.2,-2.1) node [circle,draw,inner sep=1.5pt] (l10) {\scriptsize{$11$}};
\draw(.2,-2.1) node [circle,draw,inner sep=1.5pt] (l11) {\scriptsize{$12$}};

\draw (l0) -- (l1);
\draw (l0) -- (l2);
\draw (l1) -- (l3);
\draw (l1) -- (l4);
\draw (l2) -- (l5);
\draw (l2) -- (l6);
\draw (l3) -- (l7);
\draw (l3) -- (l8);
\draw (l4) -- (l9);
\draw (l4) -- (l10);
\draw (l5) -- (l11);

\end{tikzpicture}


}
\frame{\frametitle{Primitives du type abstrait {\tt arbre binaire}}
\begin{itemize}
\item \textcolor{black}{\tt est$\_$vide(a)} : \visible<2->{renvoie {\tt Vrai} si l'arbre {\tt a} est vide, {\tt Faux} sinon}
\vspace{.3cm}
\item \textcolor{black}{\texttt{arbre\_vide()}}~: \visible<3->{renvoie l'arbre vide~;}
\vspace{.3cm}

\item \textcolor{black}{\texttt{cons(e,g,d)}}~: \visible<4->{renvoie l'arbre d'\'{e}tiquette \texttt{e}, de
fils gauche (\textit{resp.} droit) \texttt{g} (\textit{resp.} \texttt{d})~;}
\vspace{.3cm}

\item \textcolor{black}{\texttt{contenu(a)}}~: \visible<5->{renvoie l'\'{e}tiquette de l'arbre \textbf{non
vide} \texttt{a}~;}
\vspace{.3cm}

\item \textcolor{black}{\texttt{f\_g(a)}} (\textit{resp.} \textcolor{black}{\texttt{f\_d(a)}})~: \visible<6->{renvoie le fils
gauche (\textit{resp.} droit) de l'arbre \textbf{non vide} \texttt{a}.}
\end{itemize}
}
\section{Implémentation par une liste}
\frame{\frametitle{Implémentation par une liste}
En Python, on peut simplement utiliser la structure de liste :\pause

$${\tt cons(e,g,d) = [e,g,d]}$$


\begin{itemize}
\item {\bf Exemple 1 : }

\visible<3->{\scalebox{.9}{$[1,[2,[],[]],[3,[4,[5,[],[]],[6,[],[]]],[]]]$}}

\vspace{.3cm}

\item {\bf Exemple 2 : }

\visible<4->{\scalebox{.9}{$[1,[2,[],[3,[4,[],[]],[]]],[]]$}}

\vspace{.3cm}

\item {\bf Exemple 3 : }

\visible<5->{\scalebox{.9}{$[1,[2,[4,[8,[],[]],[9,[],[]]],[5,[10,[],[]],[11,[],[]]]],[3,[6,[12,[],[]],[]],[7,[],[]]]]$}}
\end{itemize}
}


\section{Représentation par un tableau}

\frame{\frametitle{Représentation par un tableau}
{\bf ID :} stocker dans un tableau {\tt t} les étiquettes

\vspace{.5cm}\pause

{\bf Mise en \oe uvre}\pause
\begin{itemize}
\item on suppose les n\oe uds numérotés :\pause
\begin{itemize}
\item de haut en bas\pause
\item de gauche à droite\pause
\item à partir de $1$\pause
\end{itemize}
\item dans la case {\tt t[k]}, on stocke l'étiquette du n\oe ud numéro {\tt k} (ou $-1$)
\end{itemize}\pause

\vspace{.3cm}

{\bf Conséquences}\pause
\begin{itemize}
\item niveau {\tt i} : \visible<10->{indices $\llbracket 2^i, 2^{i+1}-1 \rrbracket$ }
\item fils de {\tt t[k]} : \visible<11->{{\tt t[2*k]} et {\tt t[2*k+1]}}
\item père de {\tt t[k]} : \visible<12->{{\tt t[k//2]}}
\end{itemize}

}

\frame{\frametitle{Représentation par un tableau : exemple}

\begin{itemize}
\item {\bf Exemple 1 : }

\scalebox{.9}{$\visible<2->{[\textcolor{gray}{-1,}}\visible<3->{1,}\visible<4->{\textcolor{black}{2,3,}}\visible<5->{\textcolor{red}{-1,-1,4,-1,}}\visible<6->{-1,-1,-1,-1,5,6]}$}

\vspace{.3cm}

\item {\bf Exemple 2 : }

\scalebox{.9}{$\visible<7->{[\textcolor{gray}{-1,}}\visible<8->{1,}\visible<9->{\textcolor{black}{2,-1,}}\visible<10->{\textcolor{red}{-1,3,-1,-1,}}\visible<11->{-1,-1,4]}$}

\vspace{.3cm}

\item {\bf Exemple 3 : }

\scalebox{.9}{$\visible<12->{[\textcolor{gray}{-1,}}\visible<13->{1,}\visible<14->{\textcolor{black}{2,3,}}\visible<15->{\textcolor{red}{4,5,6,7,}}\visible<16->{8,9,10,11,12]}$}
\end{itemize}

\vspace{.5cm}

\visible<17->{{\bf Conclusion}}
\begin{itemize}
\item \visible<18->{Adapté aux arbres parfaits (donc aux tas...)}
\item \visible<19->{sinon : complexité spatiale exponentielle}
\end{itemize}
}

\section{Définition des tas}

\frame{\frametitle{Définition des tas}
\begin{definition}[Tas]\pause
Un {\bf tas} est un arbre binaire :\pause
\begin{itemize}
\item parfait\pause
\item tq l'étiquette de chaque n\oe ud est supérieure à celle de son père\pause
\end{itemize}
\end{definition}

{\bf Conséquence :} l'étiquette de la racine est minimale

\vspace{.3cm}\pause

{\bf Exemple :} $[-1,3,5,9,6,8, 11, 10, 12, 18, 14]$ est un tas\pause

\vspace{.3cm}

\begin{minipage}{4cm}
Plus clair comme ça :\pause
\end{minipage} 
\begin{minipage}{6cm}
\includegraphics[scale=.7]{tas1.eps}
\end{minipage}

\vspace{.3cm}\pause

{\bf Point CG :} introduit par J.W.J. Williams en 1964 pour expliciter son algorithme de tri par tas...(sujet du TP)
}


\section{Affichage des arbres}
\frame{\frametitle{Affichage des arbres}


\begin{minipage}{4.5cm}
{\bf Objectif}

\footnotesize{$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;3$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;5\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;9$

$\;\;\;\;\;\;\;\;6\;\;\;\;\;\;\;\;\;\;\;\;\;\;8\;\;\;\;\;\;\;\;\;\;\;\;11\;\;\;\;\;\;\;\;\;\;\;\;10$

$\;\;12\;\;\;\;18\;\;\;\;14$}
\end{minipage}
\begin{minipage}{6cm}
\footnotesize{{\bf Indications :}
\begin{itemize}
\item ' '*{\tt n} construit une chaîne de {\tt n} espaces
\item '$\{:^{ }\,3\}'${\tt .format(e)} crée une chaîne de 3 caractères où {\tt e} est centré
\end{itemize}}
\end{minipage}\pause


\begin{EnvCode}{}
\small{
\textcolor{black}{\tt def afficher(t):}\pause

\hspace{.5cm}\textcolor{black}{\tt n=len(t)-1 }\pause

\hspace{.5cm}\textcolor{black}{\tt h=int(log2(n)) }\pause

\hspace{.5cm}\textcolor{black}{\tt nbsc=[1] }\pause

\hspace{.5cm}\textcolor{black}{\tt for i in range(h):}\pause

\hspace{1cm}\textcolor{black}{\tt nbsc=[2*nbsc[0]+1]+nbsc}\pause

\hspace{1cm}\textcolor{black}{\tt nbsi=[1]}\pause

\hspace{.5cm}\textcolor{black}{\tt for i in range(h):}\pause

\hspace{1cm}\textcolor{black}{\tt nbsi=[2*nbsi[0]+3]+nbsi}\pause

\hspace{.5cm}\textcolor{black}{\tt for i in range(h+1):}\pause

\hspace{1cm}\textcolor{black}{\tt ligne=' '*nbsc[i]}\pause

\hspace{1cm}\textcolor{black}{\tt for j in range(2**i,min(2**(i+1),n+1)):}\pause

\hspace{1.5cm}\textcolor{black}{\tt ligne=ligne+'$\{:\hat{ }\, 3\}$'.format(t[j])+' '*nbsi[i]}\pause

\hspace{1cm}\textcolor{black}{\tt print(ligne)}}

\end{EnvCode}
}
\end{document}




\frame{\frametitle{Rappel : structures de données}
\begin{definition}[Structure de données abstraite]
On appelle structure de données abstraite, un type de données muni d'opérations.
\end{definition}

\vspace{.2cm}\pause
{\bf Attention :} une structure de données être implémentée de plusieurs façons.
\vspace{.3cm}\pause

{\bf Exemple :}
Les files sont une structure de données abstraite de type FIFO. Ces opérations sont :
\begin{itemize}
\item \textcolor{black}{creationVide :} qui crée une file vide
\item \textcolor{black}{estVide :} qui teste si une file est vide
\item \textcolor{black}{ajouteFin :} qui ajoute un élément en fin de file
\item \textcolor{black}{retireTête :} qui renvoie le premier élément d'une file non vide. Cela enlève cet élément.
\end{itemize}


\vspace{.5cm}\pause

$\Rightarrow$ On va définir mathématiquement des arbres avant de les utiliser pour définir des structures de données abstraites
}

\frame{\frametitle{Définition des arbres, terminologie}
\begin{definition}[Arbres]
Un \textcolor{black}{arbre} est un triplet $(A,r,p)$ où :
\begin{itemize}
\item $A$ est un ensemble fini
\item $r\in A$
\item $p:A\setminus\{r\}\to A$ telle que $\forall x\in A, \exists k\in\mathbb{N}$ tq $r=p^k(x)$
\end{itemize}
\end{definition}\pause

{\bf Terminologie}
\begin{itemize}
\item \textcolor{black}{Racine :} $r$, qui est le seul élément à ne pas avoir de père\pause
\item \textcolor{black}{Père :} $\forall x\in A\setminus\{r\}$, $p(x)$ est le père de $x$\pause
\item \textcolor{black}{Fils :} $\forall x\in A$, les antécédents de $x$ sont les fils de $x$\pause
\item \textcolor{black}{N\oe ud :} tous les éléments de $A$\pause
\item \textcolor{black}{Feuille :} n\oe ud qui n'a pas de fils\pause
\item \textcolor{black}{Noeud interne :} n\oe ud qui n'est pas une feuille\pause
\end{itemize}

\small{{\bf Rq :} on ajoute souvent un ensemble $B$ et une application $\mathcal{L}:A \to B$ à la définition d'un arbre pour étiqueter les noeuds}
}

\frame{\frametitle{Exemple}
\begin{minipage}{0.6\textwidth}
\begin{itemize}
\item La racine est :

\vspace{.5cm}

\item Les feuilles sont :

\vspace{.5cm}

\item Les n\oe uds internes sont :

\vspace{.5cm}

\item Cet arbre a ......... n\oe uds.

\vspace{.5cm}

\item Les fils du n\oe ud $c$ sont :

\vspace{.5cm}

\item Le père du n\oe ud $b$ est :
\end{itemize}
\end{minipage}
\begin{minipage}{0.35\textwidth}
\begin{figure}[htbp]
\begin{center}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1,-1) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(1,-1) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(-1,-2) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(1.5,-2) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-2) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(0.5,-3) node [circle,draw,inner sep=1.5pt] (l6) {$g$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l5) -- (l6);

\end{tikzpicture}
\end{center}
\end{figure}
\end{minipage}
}

\frame{\frametitle{Terminologie (suite)}
\begin{definition}
\begin{itemize}
\item \textcolor{black}{Taille :} la taille d'un arbre est le nombre de n\oe ud, $|A|$\pause
\item \textcolor{black}{Profondeur d'un n\oe ud :} la profondeur de $r$ est $0$ et la profondeur de $x\in A$ est $1$ de plus que celle de son père\pause
\item \textcolor{black}{Hauteur d'un arbre :} profondeur maximale d'un de ses n\oe ud\pause
\end{itemize}
\end{definition}

{\bf Rqs :}
\begin{itemize}
\item la profondeur d'un n\oe ud $x$ est donc le plus petit entier $k$ tq $p^k(x)=r$\pause
\item en pratique, on parle indifféremment de hauteur et de profondeur\pause
\item Par convention, l'arbre vide est de hauteur $-1$\pause
\end{itemize}

\vspace{.8cm}

\textcolor{black}{{\bf ATTENTION :} Il arrive de trouver une convention différente prenant la racine de hauteur $1$.}
}


\frame{\frametitle{Exemple}
\begin{minipage}{0.6\textwidth}
\begin{itemize}
\item Taille :

\vspace{.3cm}

\item Hauteur :

\vspace{.3cm}

\item Profondeur de $d$ :

\vspace{.3cm}

\item Profondeur de $c$ :


\vspace{1cm}

\item Taille :

\vspace{.3cm}

\item Hauteur :

\vspace{.3cm}

\item Profondeur de $d$ :

\vspace{.2cm}

\item Profondeur de $c$ :

\end{itemize}
\end{minipage}
\begin{minipage}{0.35\textwidth}
\begin{figure}[htbp]
\begin{center}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1,-1) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(1,-1) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(-1,-2) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(1.5,-2) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-2) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(0.5,-3) node [circle,draw,inner sep=1.5pt] (l6) {$g$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l5) -- (l6);

\end{tikzpicture}
\end{center}
\end{figure}

\vspace{-1cm}

\begin{figure}[htbp]
\begin{center}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1.5,-0.75) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(0,-0.75) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(1.5,-0.75) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(-0.5,-1.5) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-1.5) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(1,-1.5) node [circle,draw,inner sep=1.5pt] (l6) {$g$};
\draw(2,-1.5) node [circle,draw,inner sep=1.5pt] (l7) {$h$};
\draw(0,-2.25) node [circle,draw,inner sep=1.5pt] (l8) {$i$};
\draw(1,-2.25) node [circle,draw,inner sep=1.5pt] (l9) {$j$};
\draw(2,-2.25) node [circle,draw,inner sep=1.5pt] (l10) {$k$};
\draw(0,-3) node [circle,draw,inner sep=1.5pt] (l11) {$l$};
\draw(0,-3.75) node [circle,draw,inner sep=1.5pt] (l12) {$m$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l0) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l3) -- (l6);
\draw[-latex'] (l3) -- (l7);
\draw[-latex'] (l5) -- (l8);
\draw[-latex'] (l5) -- (l9);
\draw[-latex'] (l7) -- (l10);
\draw[-latex'] (l8) -- (l11);
\draw[-latex'] (l11) -- (l12);


\end{tikzpicture}
\end{center}
\end{figure}
\end{minipage}
}

\frame{\frametitle{Arbres binaires}
\begin{itemize}
\item \textcolor{black}{Arité de $x\in A$ :} nombre de fils de $x$\pause
\end{itemize}

{\bf Rq :} Les feuilles sont d'arité $0$\pause

\vspace{.8cm}

\begin{Definition}[Arbres binaires]
\begin{itemize}
\item Un arbre est \textcolor{black}{binaire} si tous ses noeuds internes sont d'arité au plus $2$\pause
\item  Un arbre binaire est \textcolor{black}{entier} si tous ses noeuds internes sont d'arité $2$\pause
\item Un arbre binaire entier est \textcolor{black}{parfait} si toutes ses feuilles ont la même profondeur\pause
\end{itemize}
\end{Definition}

{\bf Rqs :} 
\begin{itemize}
\item Mathématiquement, les arbres binaires sont un sous-cas des arbres.
\item En pratique, on ordonne les fils dans les arbres binaires (fils gauche et fils droit). Ils ne sont alors plus un sous-cas des arbres.
\end{itemize}
}


\frame{\frametitle{Exemple}
Lesquels de ces arbres sont binaires ? entiers ? parfaits ?
\begin{center}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,-0.5) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1,-1) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(1,-1) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(-1.5,-2) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(1.5,-2) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-2) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(0,-3) node [circle,draw,inner sep=1.5pt] (l6) {$g$};
\draw(-0.5,-2) node [circle,draw,inner sep=1.5pt] (l7) {$h$};
\draw(1,-3) node [circle,draw,inner sep=1.5pt] (l8) {$i$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l5) -- (l6);
\draw[-latex'] (l1) -- (l7);
\draw[-latex'] (l5) -- (l8);

\end{tikzpicture}
\hspace{2cm}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1.5,-0.75) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(0,-0.75) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(1.5,-0.75) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(-0.5,-1.5) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-1.5) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(1,-1.5) node [circle,draw,inner sep=1.5pt] (l6) {$g$};
\draw(2,-1.5) node [circle,draw,inner sep=1.5pt] (l7) {$h$};
\draw(0,-2.25) node [circle,draw,inner sep=1.5pt] (l8) {$i$};
\draw(1,-2.25) node [circle,draw,inner sep=1.5pt] (l9) {$j$};
\draw(2,-2.25) node [circle,draw,inner sep=1.5pt] (l10) {$k$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l0) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l3) -- (l6);
\draw[-latex'] (l3) -- (l7);
\draw[-latex'] (l5) -- (l8);
\draw[-latex'] (l5) -- (l9);
\draw[-latex'] (l7) -- (l10);


\end{tikzpicture}

\vspace{.8cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,-0.5) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1,-1) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(1,-1) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(-1,-2) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(1.5,-2) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-2) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(0.5,-3) node [circle,draw,inner sep=1.5pt] (l6) {$g$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l5) -- (l6);

\end{tikzpicture}
\hspace{2cm}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,-0.5) node [circle,draw,inner sep=1.5pt] (l0) {$a$};
\draw(-1,-1) node [circle,draw,inner sep=1.5pt] (l1) {$b$};
\draw(1,-1) node [circle,draw,inner sep=1.5pt] (l2) {$c$};
\draw(-1.5,-2) node [circle,draw,inner sep=1.5pt] (l3) {$d$};
\draw(1.5,-2) node [circle,draw,inner sep=1.5pt] (l4) {$e$};
\draw(0.5,-2) node [circle,draw,inner sep=1.5pt] (l5) {$f$};
\draw(-0.5,-2) node [circle,draw,inner sep=1.5pt] (l6) {$g$};
\draw(0.5,-3) node [circle,draw,inner sep=1.5pt,color=white] (l7) {$g$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l1) -- (l6);

\end{tikzpicture}
\end{center}
}

\frame{\frametitle{Exercice : hauteur d'un arbre}
\begin{enumerate}
\item Quelle est la taille d'un arbre binaire complet de hauteur $h$ ? Combien a-t-il de feuilles ?

\vspace{.8cm}

\item Justifier que si un arbre binaire est de taille $n$ et de hauteur $h$ alors : $$h+1\le n \le 2^{h+1}-1$$
En déduire un encadrement de la hauteur en fonction de la taille.

\vspace{.8cm}

\item Reprendre l'exercice avec un arbre dont les noeuds sont d'arité maximale $a$.
\end{enumerate}
}

\section{Implémentation}

\begin{frame}<beamer>
    \frametitle{Table des matières}
    \tableofcontents[currentsection]
  \end{frame}



\frame{\frametitle{Définition des types d'arbres}
 Définition du type \textcolor{black}{arbre binaire étiqueté}

\begin{EnvCode}{}
 \texttt{type 'a arbreBin =}

\hspace{1cm}$|$\texttt{Vide}

\hspace{1cm}$|$\texttt{N of 'a arbreBin * 'a * 'a arbreBin;;}
\end{EnvCode}

\vspace{.8cm}\pause

 Définition du type \textcolor{black}{arbre étiqueté}

\begin{EnvCode}{}

 \texttt{type 'a noeud = Noeud of 'a * ('a noeud list);;}

\textcolor{white}{l}

 \texttt{type 'a arbre =}

\hspace{1cm}$|$\texttt{Vide}

\hspace{1cm}$|$\texttt{Racine of 'a noeud;;}
\end{EnvCode}

\vspace{.2cm}
{\bf Attention :} si on définit ces deux types, le \tt{Vide} sera du dernier type défini
}

\frame{\frametitle{Induction structurelle}
{\bf ID :} Utiliser la façon dont les arbres sont constuits pour montrer qu'un prédicat est vrai pour tous les arbres.\pause

\vspace{.5cm}

\begin{EnvRes}{Méthode d'induction structurelle}
\begin{itemize}
\item Montrer que le prédicat est vrai pour le cas de base\pause
\item Montrer que le prédicat est vrai pour un arbre obtenu par construction à partir de données pour lesquelles le prédicat est déjà vrai.\pause
\end{itemize}
\end{EnvRes}

\vspace{.5cm}

{\bf Exemple :} Remontrons que si un arbre binaire est de taille $n$ et de hauteur $h$ alors :
$$h+1\le n \le 2^{h+1}-1$$
}

\frame{\frametitle{Exemple de preuve par induction}
\textcolor{black}{Supposons qu'il existe un arbre de taille $n$ et de hauteur $h$ et montrons que \hspace{3.4cm} $h+1\le n \le 2^{h+1}-1$.}\pause

\begin{itemize}
\item \textcolor{black}{Cas de base :} pour l'arbre vide, $n=0$ et $h=-1$. On a bien 
\begin{center}$0\le 0\le 2^0-1$\end{center}\pause
\item \textcolor{black}{Induction :} on considère un arbre de la forme $N(g,x,d)$. On note $n_g$, $n_d$, $h_g$ et $h_d$ les tailles et hauteurs de $d$ et $g$.\pause

\vspace{.4cm}

\textcolor{black}{Par hypothèse :} $h_g+1\le n_g \le 2^{h_g+1}-1$ et $h_d+1\le n_d \le 2^{h_d+1}-1$

\vspace{.4cm}\pause

En sommant : $h_g+h_d+3\le n_g+n_d+1 \le 2^{h_g+1}+2^{h_d+1}-1$

\vspace{.4cm}\pause

Or $h=1+\max{(h_d,h_g)}$, donc \pause
\begin{center}$h+1\le h_d+h_g+3 \mbox{ et } 2^{h_g+1}+2^{h_d+1}-1\le 2^{h+1}-1$\end{center}

\vspace{.4cm}\pause

On a donc bien \hspace{1.5cm} $h+1\le n \le 2^{h+1}-1$
\end{itemize}
}

\frame{\frametitle{Exemples de fonctions}
\textcolor{black}{Fonction qui calcule la hauteur d'un arbre binaire de type \texttt{'a arbreBin}.}
\begin{EnvCode}{}

 \texttt{let rec hauteur a =}

\hspace{.5cm} \texttt{match a with}

\hspace{.5cm}$|$\texttt{Vide -> \visible<2->{-1}}

\hspace{.5cm}$|$\texttt{N(g,$\_$,d) -> \visible<3->{1 + max (hauteur g) (hauteur d)};;}
\end{EnvCode}

\vspace{.5cm}

\visible<4->{\textcolor{black}{Fonction qui calcule la taille d'un arbre binaire de type \texttt{'a arbreBin}.}}
\visible<4->{\begin{EnvCode}{}

 \visible<5->{\texttt{let rec taille a =}}

\visible<6->{\hspace{.5cm} \texttt{match a with}}

\hspace{.5cm}\visible<6->{$|$}\texttt{\visible<6->{Vide ->} \visible<7->{0}}

\hspace{.5cm}\visible<6->{$|$}\texttt{\visible<6->{N(g,$\_$,d) ->} \visible<8>{1 + (taille g) + (taille d);;}}
\end{EnvCode}}
}

\frame{\frametitle{Exemples de fonctions}
\textcolor{black}{Fonction qui calcule le nombre de feuilles d'un arbre binaire de type \texttt{'a arbreBin}.}
\visible<2->{\begin{EnvCode}{}

 \texttt{let rec feuille a =}

\hspace{.5cm} \texttt{match a with}

\hspace{.5cm}\visible<3->{$|$\texttt{Vide -> 0}}

\hspace{.5cm}\visible<4->{$|$\texttt{N(Vide,$\_$,Vide) -> 1}}

\hspace{.5cm}\visible<5->{$|$\texttt{N(g,$\_$,d) -> (feuille g) + (feuille d);;}}
\end{EnvCode}}

\vspace{.5cm}

\visible<6->{\textcolor{black}{Fonction qui calcule le nombre de  n\oe uds internes d'un arbre binaire de type \texttt{'a arbreBin}.}}
\visible<7->{
\begin{EnvCode}{}

 \texttt{let rec noeudint a =}

\hspace{.5cm} \texttt{match a with}

\hspace{.5cm}$|$\texttt{Vide -> \visible<8->{0}}

\hspace{.5cm}$|$\texttt{N(Vide,$\_$,Vide) -> \visible<9->{0}}

\hspace{.5cm}$|$\texttt{N(g,$\_$,d) -> \visible<10->{1 + (noeudint g) + (noeudint d);;}}
\end{EnvCode}}
}

\frame{\frametitle{Variante : 2 types d'étiquettes}
On travaille fréquemment avec des arbres à 2 types d'étiquettes : \texttt{'a} pour les feuilles et \texttt{'b} pour les n\oe uds internes.\pause

\begin{EnvCode}{}
 \texttt{type ('a,'b) arbreBin =}

\hspace{1cm}$|$\texttt{Vide}

\hspace{1cm}$|$\texttt{F of \visible<3->{'a}}

\hspace{1cm}$|$\texttt{N of \visible<4->{('a,'b) arbreBin * 'b * ('a,'b) arbreBin;;}}
\end{EnvCode}

\vspace{.3cm}

\visible<5->{{\bf Application :} Les arbres de calcul

\vspace{.3cm}

\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,-0.5) node [inner sep=1.5pt,fill=white] (l0) {$-$};
\draw(-1,-1) node [inner sep=1.5pt,fill=white] (l1) {$*$};
\draw(1,-1) node [inner sep=1.5pt,fill=white] (l2) {$+$};
\draw(-1.5,-2) node [inner sep=1.5pt,fill=white] (l3) {$3$};
\draw(1.5,-2) node [inner sep=1.5pt,fill=white] (l4) {$5$};
\draw(0.5,-2) node [inner sep=1.5pt,fill=white] (l5) {$2$};
\draw(-0.5,-2) node [inner sep=1.5pt,fill=white] (l6) {$7$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l2) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l1) -- (l6);

\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.5\textwidth}
Formule :

\vspace{2cm}
\end{minipage}}
}

\section{Arbres binaires de recherche}

\begin{frame}<beamer>
    \frametitle{Table des matières}
    \tableofcontents[currentsection]
  \end{frame}


\frame{\frametitle{Motivation : dictionnaire}
\begin{Definition}
La structure de données abstraite de dictionnaire est un ensemble de couple (clés,données) tq les clés soient un ensemble totalement ordonné (des entiers) avec les opérations :\pause
\begin{itemize}
\item \textcolor{black}{Créer un dictionnaire vide}\pause
\item \textcolor{black}{Insertion :} insertion d'un nouveau couple\pause
\item \textcolor{black}{Recherche :} chercher une clé et la renvoyer si elle est présente\pause
\item \textcolor{black}{Suppression :} suppression d'un couple\pause
\end{itemize}
\end{Definition}

\vspace{.5cm}

{\bf Implémentations naïves :}
\begin{itemize}
\item \textcolor{black}{Une liste de couple :} la recherche et la suppression se font en complexité \textcolor{red}{linéaire} par rapport à la taille du dictionnaire\pause
\item \textcolor{black}{Un tableau de couple ordonné par les clés :} la recherche est \textcolor{red}{logarithmique} et la suppression et l'insertion se font en temps \textcolor{red}{linéaire}
\end{itemize}
}


\frame{\frametitle{Définition d'arbre binaire de recherche (ABR)}
\begin{Definition}
\begin{minipage}{0.6\textwidth}
Un arbre binaire de recherche (ABR) est un arbre binaire étiqueté tq l'étiquette de chaque n\oe ud est supérieur à tous les éléments du sous-arbre de gauche et inférieur à tous les éléments du sous-arbre de droite.
\end{minipage}
\begin{minipage}{0.38\textwidth}
\begin{center}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [draw,circle,inner sep=1.5pt,fill=white] (l0) {};
\draw(-1,-1.2) node [draw,circle,inner sep=1.5pt] (l1) {$-$};
\draw(1,-1.2) node [draw,circle,inner sep=1.5pt] (l2) {$+$};
\draw[-latex'] (l0) -- (-1,-.5);
\draw[-latex'] (l0) -- (1,-.5);
\draw (-1,-.5) -- (-1.75,-1.5) -- (-.25,-1.5) -- (-1,-.5);
\draw (1,-.5) -- (.25,-1.5) -- (1.75,-1.5) -- (1,-.5);

\end{tikzpicture}
\end{center}
\end{minipage}\pause
\end{Definition}

\vspace{.3cm}

{\bf Rq :} On utilisera souvent des entiers comme clés, mais on peut aussi utiliser des mots triés par ordre alphabétique.\pause

\vspace{.3cm}

\begin{minipage}{0.3\textwidth}
{\bf Exemple :}

\vspace{2cm}

\end{minipage}
\begin{minipage}{0.65\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$8$};
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$2$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$9$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$12$};
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$7$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);

\end{tikzpicture}
\end{minipage}
}

\frame{\frametitle{Exemples}
Lesquels de ces arbres sont des ABR ?

\vspace{.3cm}

\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$75$};
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$57$};
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$82$};
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$4$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$60$};
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$92$};
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$45$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$97$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);

\end{tikzpicture}
\end{minipage}
 \hspace{.1cm} 
\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$18$};
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$21$};
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$2$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$19$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$32$};
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$7$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);

\end{tikzpicture}
\end{minipage}

\vspace{1cm}

\begin{minipage}{0.55\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$76$};
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$13$};
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$81$};
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$2$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$90$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$92$};
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$7$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);

\end{tikzpicture}
\end{minipage}
 \hspace{.1cm} 
\begin{minipage}{0.4\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$8$};
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$9$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$12$};
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$7$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$2$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Principe de la recherche dans un ABR}
\begin{minipage}{0.5\textwidth}
\begin{EnvRes}{Recherche dans un ABR}
La structure d'ABR est faite pour faciliter la recherche d'un élément $x$ :\pause
\begin{itemize}
\item \textcolor{black}{arbre vide :} échec\pause
\item \textcolor{black}{si $x$ est la racine :} réussie\pause
\item \textcolor{black}{si $x>r$ :} poursuite dans le sous-arbre droit\pause
\item \textcolor{black}{si $x<r$ :} poursuite dans le sous-arbre gauche\pause
\end{itemize}
\end{EnvRes}

\vspace{.3cm}

\visible<18->{{\bf Complexité :}}\visible<19->{ la hauteur de l'ABR}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\textcolor{red}{\visible<6->{Recherche du $6$}\visible<11->{ : réussie}}

\vspace{.5cm}

 \textcolor{black}{\visible<12->{Recherche du $30$ }\visible<17->{: échec}}
\end{center}

\vspace{.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$18$};
\visible<7->{\draw(0.5,0) node [inner sep=1.5pt,fill=white] (l9) {\textcolor{red}{$>6$}};}
\visible<13->{\draw(0.5,.3) node [inner sep=1.5pt,fill=white] (l10) {\textcolor{black}{$<30$}};}
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};
\visible<9->{\draw(-1.8,-.75) node [inner sep=1.5pt,fill=white] (l11) {\textcolor{red}{$6>$}};}
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$21$};
\visible<15->{\draw(2,-.75) node [inner sep=1.5pt,fill=white] (l12) {\textcolor{black}{$<30$}};}
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$2$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};
\visible<11->{\draw(-.8,-1.5) node [inner sep=1.5pt,fill=white] (l13) {\textcolor{red}{$6=$}};}
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$19$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$32$};
\visible<17->{\draw(2,-1.5) node [inner sep=1.5pt,fill=white] (l14) {\textcolor{black}{$30<$}};}
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$7$};

\draw[-latex'] (l0) -- (l1);
\visible<8->{\draw[-latex',red] (l0) -- (l1);}
\draw[-latex'] (l0) -- (l2);
\visible<14->{\draw[-latex',black] (l0) -- (l2);}
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\visible<10->{\draw[-latex',red] (l1) -- (l4);}
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\visible<16->{\draw[-latex',black] (l2) -- (l6);}
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);

\end{tikzpicture}
\end{minipage}
}

\frame{\frametitle{Recherche dans un ABR : implémentation}
\begin{itemize}
\item Type simple d'ABR\pause
\end{itemize}
\begin{EnvCode}{}
\texttt{type arbreBin =}

\hspace{.5cm}\texttt{| Vide}

\hspace{.5cm}\texttt{| N of int * arbreBin * arbreBin;;}
\end{EnvCode}\pause

\vspace{.5cm}

\begin{itemize}
\item Fonction de recherche d'un élément \texttt{x}
\end{itemize}
\begin{EnvCode}{}\pause
\texttt{let rec cherche x t = match t with}\pause

\hspace{.5cm}\texttt{| Vide -> false}\pause

\hspace{.5cm}\texttt{\visible<6->{| N(y,$\_$,$\_$)} \visible<7->{when x = y}\visible<8->{ -> true}}

\visible<9->{\hspace{.5cm}\texttt{| N(y,$\_$,d) when x > y -> cherche x d}}

\visible<10->{\hspace{.5cm}\texttt{| N(y,g,$\_$) -> cherche x g;;}}
\end{EnvCode}
}

\frame{\frametitle{Fonction de recherche dans un ABR (suite)}
\begin{EnvCode}{}
\texttt{type 'a arbreBin =}

\hspace{.5cm}\texttt{| Vide}

\hspace{.5cm}\texttt{| N of 'a * 'a arbreBin * 'a arbreBin;;}
\end{EnvCode}\pause

\vspace{.5cm}

\begin{itemize}
\item {\bf Adapter la fonction de recherche} d'un élément \texttt{x} si l'on dispose d'une fonction \textcolor{black}{\texttt{comparaison x y}} qui est $=0$ si \texttt{x = y}, $>0$ si \texttt{x > y} et $<0$ si \texttt{x < y}.
\end{itemize}
\begin{EnvCode}{}\pause
\texttt{let rec cherche x t = match t with}\pause

\hspace{.5cm}\texttt{| Vide -> false}\pause

\hspace{.5cm}\texttt{\visible<5->{| N(y,$\_$,$\_$) when} \visible<6->{comparaison x y = 0} \visible<7->{-> true}}

\visible<8->{\hspace{.5cm}\texttt{| N(y,$\_$,d) when comparaison x y < 0 -> cherche x d}}

\visible<9->{\hspace{.5cm}\texttt{| N(y,g,$\_$) -> cherche x g;;}}
\end{EnvCode}
}

\frame{\frametitle{Opérations sur les ABR : insertion}
\begin{minipage}{0.5\textwidth}
\begin{EnvRes}{Insertion dans un ABR}
On veut insérer \texttt{x} dans un ABR en préservant sa structure

\vspace{.5cm}\pause

\textcolor{black}{Recherche de \texttt{x}}\pause
\begin{itemize}
\item \textcolor{black}{si réussie :} on ne fait rien\pause
\item \textcolor{black}{si échec :} on insert ici\pause
\end{itemize}
\end{EnvRes}

\vspace{.3cm}

\visible<12->{{\bf Complexité :}} \visible<13->{la hauteur de l'ABR}
\end{minipage}
\hspace{.2cm}
\begin{minipage}{0.45\textwidth}
\begin{center}
 \textcolor{black}{Insertion du $30$}
\end{center}

\vspace{.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$18$};
\visible<6->{\draw(0.5,.3) node [inner sep=1.5pt,fill=white] (l10) {\textcolor{black}{$<30$}};}
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$21$};
\visible<8->{\draw(2,-.75) node [inner sep=1.5pt,fill=white] (l12) {\textcolor{black}{$<30$}};}
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$2$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$19$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$32$};
\visible<10->{\draw(2,-1.5) node [inner sep=1.5pt,fill=white] (l14) {\textcolor{black}{$30<$}};}
\visible<11->{\draw(1.5,-2.25) node [inner sep=1.5pt,fill=white] (l15) {\textcolor{red}{$30$}};}
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$7$};

\draw[-latex'] (l0) -- (l1);
\draw[-latex'] (l0) -- (l2);
\visible<7->{\draw[-latex',black] (l0) -- (l2);}
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\visible<9->{\draw[-latex',black] (l2) -- (l6);}
\draw[-latex'] (l4) -- (l7);
\draw[-latex'] (l4) -- (l8);
\visible<11->{\draw[-latex',red] (l6) -- (l15);}

\end{tikzpicture}
\end{minipage}
}

\frame{\frametitle{Insertion dans les ABR : implémentation}
\begin{itemize}
\item Type simple d'ABR
\end{itemize}
\begin{EnvCode}{}
\texttt{type arbreBin =}

\hspace{.5cm}\texttt{| Vide}

\hspace{.5cm}\texttt{| N of int * arbreBin * arbreBin;;}
\end{EnvCode}\pause

\vspace{.5cm}

\begin{itemize}
\item Fonction d'insertion d'un élément \texttt{x}
\end{itemize}
\begin{EnvCode}{}\pause
\texttt{let rec insert x t = match t with}\pause

\hspace{.5cm}\texttt{| Vide -> N(x,Vide,Vide)}\pause

\hspace{.5cm}\texttt{| N(y,$\_$,$\_$) when x = y -> t}\pause

\hspace{.5cm}\texttt{| N(y,g,d) when x > y -> N(y,g,insert x d)}\pause

\hspace{.5cm}\texttt{| N(y,g,d) -> N(y,insert x g,d);;}
\end{EnvCode}
}

\frame{\frametitle{Insertion dans les ABR : exemple}
\begin{minipage}{0.45\textwidth}
\begin{itemize}
\item Insertions de :

6, 9, 3, 7, 1, 5 et 11


\vspace{2cm}

\item Insertions de :

9, 6, 3, 7, 1, 5 et 11
\end{itemize}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<2->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$6$};}
\visible<4->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};}
\visible<3->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$9$};}
\visible<6->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$1$};}
\visible<7->{\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$5$};}
\visible<5->{\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$7$};}
\visible<8->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$11$};}

\visible<4->{\draw[-latex'] (l0) -- (l1);}
\visible<3->{\draw[-latex'] (l0) -- (l2);}
\visible<6->{\draw[-latex'] (l1) -- (l3);}
\visible<7->{\draw[-latex'] (l1) -- (l4);}
\visible<5->{\draw[-latex'] (l2) -- (l5);}
\visible<8->{\draw[-latex'] (l2) -- (l6);}

\end{tikzpicture}

\vspace{1.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<9->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$9$};}
\visible<10->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$6$};}
\visible<15->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};}
\visible<11->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$3$};}
\visible<12->{\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$7$};}
\visible<14->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$5$};}
\visible<13->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$1$};}

\visible<10->{\draw[-latex'] (l0) -- (l1);}
\visible<15->{\draw[-latex'] (l0) -- (l2);}
\visible<11->{\draw[-latex'] (l1) -- (l3);}
\visible<12->{\draw[-latex'] (l1) -- (l4);}
\visible<14->{\draw[-latex'] (l3) -- (l5);}
\visible<13->{\draw[-latex'] (l3) -- (l6);}

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Attention !}
L'ordre d'insertion des éléments importe sur :\pause

\begin{itemize}
\item la forme de l'arbre\pause
\item donc sur la hauteur\pause
\item donc sur la complexité de la recherche\pause
\end{itemize}
\begin{minipage}{0.45\textwidth}
Insertions de :

 1, 3, 12, 23 et 36\pause

\vspace{.2cm}

\visible<11->{\textcolor{black}{Liste triée $\Rightarrow$ arbre dégénéré}}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<6->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$1$};}
\visible<7->{\draw(-1,-.5) node [inner sep=1.5pt,fill=white] (l1) {$3$};}
\visible<8->{\draw(-2.,-1) node [inner sep=1.5pt,fill=white] (l2) {$12$};}
\visible<9->{\draw(-3,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$23$};}
\visible<10->{\draw(-4,-2) node [inner sep=1.5pt,fill=white] (l4) {$36$};}

\visible<7->{\draw[-latex'] (l0) -- (l1);}
\visible<8->{\draw[-latex'] (l1) -- (l2);}
\visible<9->{\draw[-latex'] (l2) -- (l3);}
\visible<10->{\draw[-latex'] (l3) -- (l4);}

\end{tikzpicture}
\end{minipage}

\vspace{.5cm}

\visible<12->{{\bf Solution :} on permute aléatoirement les éléments de la liste}

\vspace{.2cm}

\hspace{1cm} \visible<13->{$\to$ hauteur moyenne : $2\log n$ où $n$ est la taille.}

\vspace{.2cm}

\hspace{1cm} \visible<14->{$\to$ On peut construire un ABR en $O(n\log n)$ où $n$ est la taille.}
}


\frame{\frametitle{Opérations sur les ABR : suppression}
\begin{minipage}{0.5\textwidth}
\begin{EnvRes}{Suppression dans un ABR}
\'Etant donnés un ABR et un élément \texttt{x}, on veut supprimer \texttt{x} en préservant la structure d'ABR\pause

\vspace{.5cm}

\textcolor{black}{Recherche de \texttt{x}}\pause
\begin{itemize}
\item \textcolor{black}{si \texttt{x} est une feuille :} on la supprime\pause
\item \textcolor{black}{si \texttt{x} est un n\oe ud interne :} \pause
\begin{itemize}
\item chercher le + grand n\oe ud du ss-arbre gauche (feuille)\pause
\item remplacer \texttt{x} par ce n\oe ud\pause
\end{itemize}


\end{itemize}
\end{EnvRes}

\vspace{.3cm}

\visible<10->{{\bf Complexité :} la hauteur de l'ABR}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
 \textcolor{black}{Suppression du $16$}
\end{center}

\vspace{.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$20$};
\visible<8->{\draw(0.5,0) node [inner sep=1.5pt,fill=white] (l9) {\textcolor{red}{$>16$}};}
\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};
\visible<10->{\draw(-2,-.75) node [inner sep=1.5pt,fill=white] (l11) {\textcolor{red}{$16>$}};}
\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$21$};
\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$2$};
\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$16$};
\visible<12->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l13) {\textcolor{red}{$16=$}};}
\visible<19-20>{\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {\textcolor{black}{12}};}
\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$19$};
\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$32$};
\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7b) {$10$};
\visible<14->{\draw(-1,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$\textcolor{green}{10}$};}
\draw(-0,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$18$};
\draw(-1.25,-3) node [inner sep=1.5pt,fill=white] (l20) {$9$};
\visible<-19>{\draw(-0.75,-3) node [inner sep=1.5pt,fill=white] (l21b) {$12$};}
\visible<16-19>{\draw(-0.75,-3) node [inner sep=1.5pt,fill=white] (l21) {\textcolor{green}{12}};}
\visible<17-19>{\draw(-0.75,-3) node [draw,inner sep=1.5pt,fill=white] (l21) {\textcolor{black}{\sout{12}}};}
\draw(-.25,-3) node [inner sep=1.5pt,fill=white] (l22) {$17$};
\draw(.25,-3) node [inner sep=1.5pt,fill=white] (l23) {$19$};

\draw[-latex'] (l0) -- (l1);
\visible<9->{\draw[-latex',red] (l0) -- (l1);}
\draw[-latex'] (l0) -- (l2);
\draw[-latex'] (l1) -- (l3);
\draw[-latex'] (l1) -- (l4);
\visible<11->{\draw[-latex',red] (l1) -- (l4);}
\draw[-latex'] (l2) -- (l5);
\draw[-latex'] (l2) -- (l6);
\draw[-latex'] (l4) -- (l7);
\visible<13->{\draw[-latex',green] (l4) -- (l7);}
\draw[-latex'] (l4) -- (l8);
\draw[-latex'] (l7) -- (l20);
\visible<-19>{\draw[-latex'] (l7) -- (l21);}
\visible<15-19>{\draw[-latex',green] (l7) -- (l21);}
\visible<17-19>{\draw[-latex',black,dashed] (l7) -- (l21);}
\draw[-latex'] (l8) -- (l22);
\draw[-latex'] (l8) -- (l23);
\visible<18-19>{\draw[-latex',dashed,black] (l21)to[bend right](l4);}

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Suppression dans les ABR : implémentation}

\begin{minipage}{0.5\textwidth}
{\bf \'Etape 1 :} Une fois qu'on a trouvé l'élément à supprimer, cela revient à supprimer la racine

\vspace{1cm}

 \visible<6->{On utilise une sous-fonction {\bf \texttt{recMax}}}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\visible<2->{\begin{tikzpicture}
\everymath{\scriptstyle}
\draw(0,0) node [draw,circle,inner sep=1.5pt,fill=white] (l0) {};
\visible<5->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l3) {\textcolor{red}{\Large{m}}};}
\draw(-.5,-1.4) node [draw,circle,inner sep=1.5pt] (l1) {m};
\visible<3->{\draw(-.5,-1.4) node [inner sep=1.5pt] (l2) {\textcolor{red}{\Large{X}}};}
\draw[-latex'] (l0) -- (-1,-.5);
\draw[-latex'] (l0) -- (1,-.5);
\visible<4->{\draw[-latex',dashed,red] (-.25,-1.5)to[bend right](l0);}
\draw (-1,-.5) -- (-1.75,-1.5) -- (-.25,-1.5) -- (-1,-.5);
\draw (1,-.5) -- (.25,-1.5) -- (1.75,-1.5) -- (1,-.5);

\end{tikzpicture}}

\vspace{.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<9->{\draw(.5,-1.4) node [draw,circle,inner sep=1.5pt] (l1) {m};
\draw(.5,-1.4) node [inner sep=1.5pt] (l2) {\textcolor{red}{\Large{X}}};
\draw(-.8,-1) node [inner sep=1.5pt] (l3) {\textcolor{red}{\Large{m, }}};}
\visible<7->{\draw(-2.5,-1.4) node [draw,circle,inner sep=1.5pt] (l6) {m};}
\visible<8->{\draw(-1.7,-.7) node [inner sep=1.5pt] (l5) {\texttt{recMax}};}
%\draw[-latex',dashed,red] (-.25,-1.5)to[bend right](l0);
\visible<9->{\draw (0,-.5) -- (-.75,-1.5) -- (.75,-1.5) -- (0,-.5);}
\visible<7->{\draw (-3,-.5) -- (-3.75,-1.5) -- (-2.25,-1.5) -- (-3,-.5);}
\visible<8->{\draw[-latex',line width=2pt] (-2.25,-1) -- (l3);}

\end{tikzpicture}
\end{center}
\end{minipage}

\visible<10->{
\begin{EnvCode}{}
\footnotesize{
\texttt{let rec supprimerRacine a = match a with}

\visible<11->{\hspace{.5cm}\texttt{| Vide -> failwith "impossible"}}

\hspace{.5cm}\texttt{\visible<12->{| N(x,Vide,d) }\visible<13->{-> d}}

\visible<14->{\hspace{.5cm}\texttt{| N(x,g,d) -> let rec recMax a = match a with}}

\visible<15->{\hspace{3cm}\texttt{| Vide -> failwith "impossible"}}

\visible<16->{\hspace{3cm}\texttt{| N(x,g,Vide) -> (x,g)}}

\visible<17->{\hspace{3cm}\texttt{| N(x,g,d) -> let (v,ab) = recMax d in (v,N(x,g,ab))}

\hspace{2.6cm}\texttt{in let (v,ab) = recMax g in N(v,ab,d);;}}}
\end{EnvCode}}
}

\frame{\frametitle{Suppression dans les ABR : implémentation}

\begin{minipage}{0.5\textwidth}
{\bf \'Etape 2 :} On cherche l'élément à supprimer et on applique l'étape 1.\pause

\vspace{1cm}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<4->{\draw(0,-1.6) node [draw,circle,inner sep=1.5pt,color=red] (l1) {x};}
\visible<9->{\draw(0,-1.6) node [draw,circle,inner sep=1.5pt,color=red] (l8) {\large{\textcolor{black}{m}}};}
\visible<6->{\draw(-.7,-3.6) node [inner sep=1.5pt,color=red] (l2) {\textcolor{black}{étape 1}};}
\visible<7->{\draw(-.2,-3.8) node [draw,circle,inner sep=1.5pt,color=red] (l9) {\large{\textcolor{black}{X}}};}
\visible<2->{\draw (0,0) -- (2.5,-4) -- (-2.5,-4) -- (0,0);}
\visible<3->{\draw[red] (0,0) -- (-.5,-.8) -- (l1);}
\visible<5->{\draw (-.5,-2.4) -- (-1.5,-4) -- (0,-4) -- (-.5,-2.4);}
\visible<6->{\draw[black] (-.5,-2.4) -- (-1.5,-4) -- (0,-4) -- (-.5,-2.4);}
\visible<5->{\draw (.5,-2.4) -- (1.5,-4) -- (0,-4) -- (.5,-2.4);
\draw (l1)--(-.5,-2.4);
\draw (l1)--(.5,-2.4);}
\visible<8->{\draw[-latex',dashed,red] (l9)to[bend right](l8);}


\end{tikzpicture}

\vspace{.5cm}

\end{center}
\end{minipage}

\visible<10->{
\begin{EnvCode}{}
\footnotesize{
\texttt{let rec supprime x a = match a with}

\visible<11->{\hspace{.5cm}\texttt{| Vide -> Vide}}

\visible<12->{\hspace{.5cm}\texttt{| N(y,g,d) when x > y -> N(y,g,supprime x d)}}

\visible<13->{\hspace{.5cm}\texttt{| N(y,g,d) when x < y -> N(y,supprime x g,d)}}

\visible<14->{\hspace{.5cm}\texttt{| N(y,g,d) -> supprimerRacine a;;}}}
\end{EnvCode}}
}

\frame{\frametitle{Suppression dans les ABR : exemples}
\begin{minipage}{0.45\textwidth}
\begin{itemize}
\item Suppressions de :

6 et 11


\vspace{2cm}

\item Suppressions de :

6 et 5
\end{itemize}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1>{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$6$};}
\visible<2->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l144) {$5$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$9$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$1$};}
\visible<1>{\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$5$};}
\visible<1->{\draw(.5,-1.5) node [inner sep=1.5pt,fill=white] (l5) {$7$};}
\visible<1-2>{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l6) {$11$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1>{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l2) -- (l5);}
\visible<1-2>{\draw[-latex'] (l2) -- (l6);}

\end{tikzpicture}

\vspace{1.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$9$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$6$};}
\visible<4>{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l144) {$5$};}
\visible<5->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l145) {$3$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$3$};}
\visible<5->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l35) {$1$};}
\visible<1->{\draw(-.5,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$7$};}
\visible<1-3>{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$5$};}
\visible<1-4>{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$1$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1-3>{\draw[-latex'] (l3) -- (l5);}
\visible<1-4>{\draw[-latex'] (l3) -- (l6);}

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Conclusion sur les dictionnaires}
On peut donc réaliser un dictionnaire efficace en utilisant un ABR :

\vspace{.5cm}\pause

\begin{itemize}
\item Insertion : \textcolor{red}{hauteur de l'ABR}

\vspace{.3cm}\pause

\item Suppression : \textcolor{red}{hauteur de l'ABR}

\vspace{.3cm}\pause

\item Recherche : \textcolor{red}{hauteur de l'ABR}
\end{itemize}

\vspace{.5cm}\pause

Donc attention à l'équilibre de l'arbre...

\vspace{.5cm}\pause

L'exemple classique est le dictionnaire dont les n\oe uds contiennent des définitions et les clés sont les étiquettes.

}

\section{Tas et listes de priorité}

\begin{frame}<beamer>
    \frametitle{Table des matières}
    \tableofcontents[currentsection]
  \end{frame}


\frame{\frametitle{Motivation : listes de priorité}
On s'intéresse à la structure de liste de priorité.

\vspace{.3cm}

\textcolor{black}{{\bf ID :} file d'attente avec des personnes $+$ ou $-$ importantes }

\textcolor{black}{$\to$ on veut traiter la personne la $+$ importante}

\vspace{.3cm}

{\bf Exemple d'application :} processus qui arrivent à un processeur

\vspace{.3cm}

\textcolor{black}{{\bf Opérations :}
\begin{itemize}
\item Trouver le maximum
\item Insérer un élément
\item Retirer le maximum
\end{itemize}}

\vspace{.3cm}

{\bf Implémentations na\"ives :}
\begin{itemize}
\item \underline{Tableau ou liste non ordonné :} 

\textcolor{black}{Insertion} \textcolor{red}{en temps constant} / \textcolor{black}{Recherche du max} \textcolor{red}{en temps linéaire}
\item \underline{Tableau ou liste ordonné :} 

\textcolor{black}{Insertion} \textcolor{red}{en temps constant} / \textcolor{black}{Recherche du max} \textcolor{red}{en temps linéaire}
\end{itemize}



}

\frame{\frametitle{Définition d'un tas}
\begin{definition}
Un tas (maximal) de hauteur $h$ est un arbre binaire tel que :
\begin{itemize}
\item Profondeur des feuilles : $h$ ou $h-1$
\item $\forall p$ tq $p<n$, il y a $2^p$ n\oe uds de profondeur $p$
\item Tous les n\oe uds de profondeur $h$ sont "à gauche"
\item Chaque n\oe ud a une étiquette $\ge$ à celles de ses fils.
\end{itemize}
\end{definition}


\vspace{.3cm}

{\bf Rq :} On peut aussi définir des tas minimaux.

%\end{minipage}

\vspace{.3cm}

\begin{minipage}{0.5\textwidth}
Encadrement du nombre de n\oe uds :

\vspace{.3cm}

$2^h=1+2+4+...+2^{h-1}+1\le n \le 1+2+4+...+2^{h}=2^{h+1}-1$

\vspace{.3cm}

Encadrement de la hauteur :

\vspace{.3cm}

$\log_2(n+1)-1\le h \le \log_2(n)$

\vspace{.3cm}



\end{minipage}
\begin{minipage}{0.45\textwidth}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$12$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$4$};}
\visible<1->{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1->{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$3$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$9$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l4) -- (l7);}
\visible<1->{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}
\end{minipage}
}



\frame{\frametitle{Exemples}
\begin{center}
Lesquels de ces arbres sont des tas ?
\end{center}

\begin{minipage}{0.45\textwidth}
\scalebox{.9}{
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$12$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$3$};}
\visible<1->{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1->{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$4$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$9$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l4) -- (l7);}
\visible<1->{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}}
\end{minipage}
\hspace{.5cm}
\begin{minipage}{0.45\textwidth}
\scalebox{.9}{
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$12$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$8$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$9$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$3$};}
\visible<1->{\draw(1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1->{\draw(.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$4$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$6$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l9) -- (l7);}
\visible<1->{\draw[-latex'] (l9) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}}
\end{minipage}

\begin{minipage}{0.45\textwidth}
\scalebox{.9}{
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$22$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$21$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$3$};}
\visible<1->{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1->{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$4$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$19$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$12$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l4) -- (l7);}
\visible<1->{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}}
\end{minipage}
\hspace{.5cm}
\begin{minipage}{0.45\textwidth}
\scalebox{.9}{
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$22$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$7$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$6$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$9$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$3$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$8$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}}
\end{minipage}
}

\frame{\frametitle{Opérations sur les tas : insertion}
\begin{minipage}{0.5\textwidth}
\begin{EnvRes}{Insertion dans un tas}
\'Etant donnés un tas et un élément \texttt{x}, on veut insérer \texttt{x} en préservant la structure de tas\pause

\vspace{.5cm}

\begin{itemize}
\item \textcolor{black}{Insertion :} de \texttt{x} en bas\pause
\item \textcolor{black}{Remonte \texttt{x} :} jusqu'à ce que son père soit $+$ grand\pause

\end{itemize}
\end{EnvRes}

\vspace{.3cm}

\visible<8->{{\bf Complexité :} la hauteur du tas}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
 \textcolor{black}{Insertion du $12$}
\end{center}

\vspace{.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$14$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$11$};}
\visible<7->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$12$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$4$};}
\visible<1->{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1->{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$3$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$9$};}
\visible<6->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$12$};}
\visible<7->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9c) {$11$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}
\visible<5->{\draw(.5,-2.25) node [inner sep=1.5pt,fill=white] (l11) {$12$};}
\visible<6->{\draw(.5,-2.25) node [inner sep=1.5pt,fill=white] (l11b) {$9$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l4) -- (l7);}
\visible<1->{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}
\visible<5->{\draw[-latex'] (l9) -- (l11);}

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Insertion dans les tas : exemples}
\begin{minipage}{0.45\textwidth}
\begin{itemize}
\item Insertions de :

6, 9, 3, 7, 1, 5 et 11


\vspace{2cm}

\item Insertions de :

9, 3, 6, 7, 1, 5 et 11

\end{itemize}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<2->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$6$};}
\visible<4->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0b) {$9$};}
\visible<13->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0c) {$11$};}
\visible<3->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$9$};}
\visible<4->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1b) {$6$};}
\visible<7->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1c) {$7$};}
\visible<5->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$3$};}
\visible<10->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2b) {$5$};}
\visible<12->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2c) {$11$};}
\visible<13->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2c) {$9$};}
\visible<6->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<7->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3b) {$6$};}
\visible<8->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$1$};}
\visible<9->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$5$};}
\visible<10->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$3$};}
\visible<11->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$11$};}
\visible<12->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10b) {$5$};}

\visible<3->{\draw[-latex'] (l0) -- (l1);}
\visible<5->{\draw[-latex'] (l0) -- (l2);}
\visible<6->{\draw[-latex'] (l1) -- (l3);}
\visible<8->{\draw[-latex'] (l1) -- (l4);}
\visible<9->{\draw[-latex'] (l2) -- (l9);}
\visible<11->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}

\vspace{1.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<14->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$9$};}
\visible<23->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0b) {$11$};}
%\visible<13->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0c) {$11$};}
\visible<15->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$3$};}
\visible<18->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1b) {$7$};}
%\visible<7->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1c) {$7$};}
\visible<16->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$6$};}
\visible<22->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2b) {$11$};}
\visible<23->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2c) {$9$};}
%\visible<13->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2d) {$9$};}
\visible<17->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<18->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3b) {$3$};}
\visible<19->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$1$};}
\visible<20->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$5$};}
%\visible<10->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$3$};}
\visible<21->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$11$};}
\visible<22->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10b) {$6$};}

\visible<15->{\draw[-latex'] (l0) -- (l1);}
\visible<16->{\draw[-latex'] (l0) -- (l2);}
\visible<17->{\draw[-latex'] (l1) -- (l3);}
\visible<19->{\draw[-latex'] (l1) -- (l4);}
\visible<20->{\draw[-latex'] (l2) -- (l9);}
\visible<21->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Opérations sur les tas : suppression}
\begin{minipage}{0.5\textwidth}
\begin{EnvRes}{Supression du maximum dans un tas}
\'Etant donné un tas, on veut supprimer l'élément maximal en préservant la structure de tas\pause

\vspace{.5cm}

\begin{itemize}
\item \textcolor{black}{\'Echange :} le max et l'élément \texttt{x} du bas\pause
\item \textcolor{black}{Supprime :} l'élément du bas (max)\pause
\item \textcolor{black}{Descend \texttt{x} :} en l'échangeant avec son + gd fils jusqu'à ce qu'il soit $+$ grand que ces 2 fils\pause

\end{itemize}
\end{EnvRes}

\vspace{.3cm}

\visible<11->{{\bf Complexité :} la hauteur du tas}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
 \textcolor{black}{Suppression du max}
\end{center}

\vspace{.5cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$14$};}
\visible<6->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0b) {$3$};}
\visible<8->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0c) {$12$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$12$};}
\visible<8->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1b) {$3$};}
\visible<9->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1c) {$7$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$10$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<9->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3b) {$3$};}
\visible<10->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3c) {$4$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$4$};}
\visible<10->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6b) {$3$};}
\visible<1->{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1-5>{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$3$};}
\visible<6>{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8b) {$14$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$9$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l4) -- (l7);}
\visible<1-6>{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}
\end{minipage}
}


\frame{\frametitle{Suppression dans les tas : exemples}
\begin{minipage}{0.45\textwidth}
\begin{itemize}
\item Suppressions du max :

2 fois


\vspace{2cm}

\item Suppression du max :

3 fois

\end{itemize}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$11$};}
\visible<2->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0b) {$3$};}
\visible<4->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0c) {$9$};}
\visible<6->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0d) {$5$};}
\visible<8->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0e) {$7$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$9$};}
\visible<4->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1b) {$3$};}
\visible<5->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1c) {$7$};}
\visible<8->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1d) {$5$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$6$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<5->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3b) {$3$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$1$};}
\visible<1-5>{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$5$};}
\visible<6>{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$9$};}
\visible<1>{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$3$};}
\visible<2>{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10b) {$11$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1-6>{\draw[-latex'] (l2) -- (l9);}
\visible<1-2>{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}

\vspace{1.5cm}
\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$14$};}
\visible<9->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0b) {$9$};}
\visible<11->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0c) {$12$};}
\visible<13->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0d) {$3$};}
\visible<15->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0e) {$11$};}
\visible<17->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0f) {$5$};}
\visible<19->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0g) {$10$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$10$};}
\visible<19->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1b) {$5$};}
\visible<20->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1c) {$7$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$12$};}
\visible<11->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2b) {$9$};}
\visible<12->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2c) {$11$};}
\visible<15->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2d) {$3$};}
\visible<16->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2d) {$9$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<20->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3b) {$5$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$4$};}
\visible<1-16>{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<17>{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7b) {$11$};}
\visible<1-12>{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$3$};}
\visible<13>{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8b) {$12$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$11$};}
\visible<12->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$9$};}
\visible<16->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$3$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}
\visible<1-8>{\draw(.5,-2.25) node [inner sep=1.5pt,fill=white] (l11) {$9$};}
\visible<9>{\draw(.5,-2.25) node [inner sep=1.5pt,fill=white] (l11b) {$14$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1-17>{\draw[-latex'] (l4) -- (l7);}
\visible<1-13>{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}
\visible<1-9>{\draw[-latex'] (l9) -- (l11);}

\end{tikzpicture}
\end{minipage}
}

\frame{\frametitle{Implémentation des tas avec un tableau}
\begin{EnvRes}{Implémentation d'un tas avec un tableau}\pause
\begin{itemize}
\item \textcolor{black}{t.(0) :} taille du tas\pause
\item \textcolor{black}{t.(1) :} racine\pause
\item \textcolor{black}{t.(2k) et t.(2k+1) :} fils t.(k)\pause
\item \textcolor{black}{t.(E(k/2)) :} père de t.(k)\pause

\end{itemize}
\end{EnvRes}

\vspace{.2cm}

\begin{center}
 \textcolor{black}{Tableau :}

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\visible<7->{11}&\visible<8->{14}&\visible<9->{12}&\visible<9->{10}&\visible<10->{7}&\visible<10->{6}&\visible<11->{9}&\visible<11->{2}&\visible<12->{4}&\visible<12->{1}&\visible<13->{5}&\visible<13->{3}\\
\hline
\end{array}$

\vspace{.1cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$14$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$12$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$10$};}
\visible<1->{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<1->{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<1->{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<1->{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$4$};}
\visible<1->{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<1->{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$3$};}
\visible<1->{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$9$};}
\visible<1->{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1->{\draw[-latex'] (l1) -- (l3);}
\visible<1->{\draw[-latex'] (l1) -- (l4);}
\visible<1->{\draw[-latex'] (l3) -- (l5);}
\visible<1->{\draw[-latex'] (l3) -- (l6);}
\visible<1->{\draw[-latex'] (l4) -- (l7);}
\visible<1->{\draw[-latex'] (l4) -- (l8);}
\visible<1->{\draw[-latex'] (l2) -- (l9);}
\visible<1->{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}

\end{center}
}


\frame{\frametitle{Constructeur et fonctions de base}

\begin{itemize}
\item \textcolor{black}{Création d'un tas vide de taille maximale \texttt{taille\_max}}

\begin{EnvCode}{}
 \visible<2->{\texttt{let creTasVide taille\_max = Array.make taille\_max 0;;}}
\end{EnvCode}

\vspace{.6cm}

\item \textcolor{black}{Test du vide}

\begin{EnvCode}{}
  \visible<3->{\texttt{let estVide t = (t.(0)=0);;}}
\end{EnvCode}

\vspace{.6cm}

\item \textcolor{black}{Recherche de l'élément maximal}

\begin{EnvCode}{}
  \visible<4->{\texttt{let maxiFile t = }}

\hspace{1cm} \visible<5->{\texttt{if estVide(t) then failwith "tas vide"}}

\hspace{1cm} \visible<6->{\texttt{else t.(1);;}}
\end{EnvCode}
\end{itemize}
}

\frame{\frametitle{Implémentation de l'insertion}


{\bf Rq :} on utilise la fonction \texttt{echange t i j} qui échange les cases \texttt{i} et \texttt{j} du tableau \tt{t}.

\vspace{.5cm}

\begin{EnvCode}{}
 \texttt{let insert x t =}\pause

\hspace{1cm}\texttt{t.(0) <- t.(0) + 1;}\pause

\hspace{1cm}\texttt{t.(t.(0)) <- x;}\pause

\hspace{1cm}\texttt{let k = ref t.(0) in}\pause

\hspace{1cm}\texttt{let p = ref (!k/2) in}\pause

\hspace{1cm}\texttt{while !k <> 1 \&\& t.(!k) > t.(!p) do}\pause

\hspace{2cm}\texttt{echange t !k !p;}\pause

\hspace{2cm}\texttt{k := !p;}\pause

\hspace{2cm}\texttt{p := !k/2}\pause

\hspace{2cm}\texttt{done ;;}


%\hspace{1cm}$|$\texttt{Vide}
\end{EnvCode}

}

\frame{\frametitle{Implémentation de la suppression}
{\bf Rq :} on peut supprimer n'importe quel élément d'indice \texttt{k} du tas de la même façon.

\vspace{.3cm}

\begin{EnvCode}{}
\scalebox{.9}{\texttt{let supprime k t =}}

\visible<2->{\scalebox{.9}{\hspace{1cm}\texttt{echange t t.(0) k;}}}

\visible<3->{\scalebox{.9}{\hspace{1cm}\texttt{t.(0) <- t.(0) - 1;}}}

\visible<4->{\scalebox{.9}{\hspace{1cm}\texttt{descente t k;;}}}

%\hspace{1cm}$|$\texttt{Vide}
\end{EnvCode}

\vspace{.3cm}

 \begin{EnvCode}{}
\scalebox{.9}{\texttt{let rec descente t i =}}

\visible<5->{\scalebox{.9}{\hspace{1cm}\texttt{let n = ref i in}}}

\visible<6->{\scalebox{.9}{\hspace{1cm}\texttt{if 2*i < t.(0) \&\& t.(2*i) > t.(i) then n := 2*i;}}}

\visible<7->{\scalebox{.9}{\hspace{1cm}\texttt{if 2*i+1 < t.(0) \&\& t.(2*i+1) > t.(!n) then n := 2*i+1;}}}

\visible<8->{\scalebox{.9}{\hspace{1cm}\texttt{if !n <> i then}}}

\visible<9->{\scalebox{.9}{\hspace{2cm}\texttt{(echange t i !n;}}}

\visible<10->{\scalebox{.9}{\hspace{2cm}\texttt{descente t !n);;}}}

%\hspace{1cm}$|$\texttt{Vide}
\end{EnvCode}
}


\frame{\frametitle{Application : tri par tas}
{\bf ID :} on peut utiliser la structure de tas pour trier des données.

\vspace{.5cm}

$\to$ à partir d'un tas, on peut extraire le maximum jusqu'à vider le tas

\vspace{.5cm}

$\to$ complexité en $O(n\log(n))$ s'il y a $n$ éléments

\vspace{.5cm}

{\bf Rq :} il reste à considérer la construction du tas $\to$ ex 16

\vspace{.5cm}

$\Rightarrow$ On obtient un algorithme de tri par comparaison en $O(n\log(n))$ (optimal)
}

\frame{\frametitle{Tri par tas : exemple}
\begin{center}
 \textcolor{black}{Tableau :}

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\textcolor{red}{\only<1-2>{11}\only<3-7>{10}\only<8-11>{9}\only<12-15>{8}\only<16-19>{7}\only<20-23>{6}\only<24-26>{5}\only<27-29>{4}\only<30->{3}}&
\only<1>{14}\only<2-3,15-16,26-27,31>{3}\only<4-6>{12}\only<7-8,25>{5}\only<9-10>{10}\only<11-12,23-24>{1}\only<13-14>{9}\only<17-18>{7}\only<19-20,29-30>{2}\only<21-22>{6}\only<28>{4}&
\only<1-3>{12}\only<4,17,28-30>{3}\only<5-16>{7}\only<18-20>{6}\only<21,31->{2}\only<22-27>{4}&
\only<1-8>{10}\only<9,14-24>{5}\only<10-12>{9}\only<13,25->{1}&
\only<1-4>{7}\only<5>{3}\only<6-21>{4}\only<22-28>{2}\only<29->{\textcolor{black}{4}}&
\only<1-17>{6}\only<18-25>{3}\only<26->{\textcolor{black}{5}}&
\only<1-9>{9}\only<10-13>{5}\only<14-22>{1}\only<23->{\textcolor{black}{6}}&
\only<1-18>{2}\only<19->{\textcolor{black}{7}}&
\only<1-5>{4}\only<6-14>{3}\only<15->{\textcolor{black}{9}}&
\only<1-10>{1}\only<11->{\textcolor{black}{10}}&
\only<1-6>{5}\only<7->{\textcolor{black}{12}}&
\only<1>{3}\only<2->{\textcolor{black}{14}}\\
\hline
\end{array}$

\vspace{1cm}

\begin{tikzpicture}
\everymath{\scriptstyle}
\visible<1->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0) {$14$};}
\visible<2->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0b) {$3$};}
\visible<4->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0c) {$12$};}
\visible<7->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0d) {$5$};}
\visible<9->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0e) {$10$};}
\visible<11->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0f) {$1$};}
\visible<13->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0g) {$9$};}
\visible<15->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0h) {$3$};}
\visible<17->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0i) {$7$};}
\visible<19->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0j) {$2$};}
\visible<21->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0k) {$6$};}
\visible<23->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0l) {$1$};}
\visible<25->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0k) {$5$};}
\visible<26->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0k) {$3$};}
\visible<28->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0k) {$4$};}
\visible<29->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0k) {$2$};}
\visible<31->{\draw(0,0) node [inner sep=1.5pt,fill=white] (l0k) {$3$};}
\visible<1->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1) {$12$};}
\visible<4->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1b) {$3$};}
\visible<5->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1c) {$7$};}
\visible<17->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1d) {$3$};}
\visible<18->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1e) {$6$};}
\visible<21->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1f) {$2$};}
\visible<22->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1g) {$4$};}
\visible<28->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1h) {$3$};}
\visible<31->{\draw(-1.5,-.75) node [inner sep=1.5pt,fill=white] (l1h) {$2$};}
\visible<1->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2) {$10$};}
\visible<9->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2b) {$5$};}
\visible<10->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2c) {$9$};}
\visible<13->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2d) {$1$};}
\visible<14->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2e) {$5$};}
\visible<25->{\draw(1.5,-.75) node [inner sep=1.5pt,fill=white] (l2f) {$1$};}
\visible<1-27>{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3) {$7$};}
\visible<5-27>{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3b) {$3$};}
\visible<6-27>{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3c) {$4$};}
\visible<22-28>{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3d) {$2$};}
\visible<29>{\draw(-2.5,-1.5) node [inner sep=1.5pt,fill=white] (l3e) {$4$};}
\visible<1-25>{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4) {$6$};}
\visible<18-25>{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4b) {$3$};}
\visible<26>{\draw(-1,-1.5) node [inner sep=1.5pt,fill=white] (l4c) {$5$};}
\visible<1-10>{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5) {$1$};}
\visible<11>{\draw(-2,-2.25) node [inner sep=1.5pt,fill=white] (l5b) {$10$};}
\visible<1-14>{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6) {$4$};}
\visible<6-14>{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6b) {$3$};}
\visible<15>{\draw(-3,-2.25) node [inner sep=1.5pt,fill=white] (l6c) {$9$};}
\visible<1-6>{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7) {$5$};}
\visible<7>{\draw(-1.5,-2.25) node [inner sep=1.5pt,fill=white] (l7b) {$12$};}
\visible<1>{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8) {$3$};}
\visible<2>{\draw(-.5,-2.25) node [inner sep=1.5pt,fill=white] (l8b) {$14$};}
\visible<1-22>{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9) {$9$};}
\visible<10-22>{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9b) {$5$};}
\visible<14-22>{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9c) {$1$};}
\visible<23>{\draw(1,-1.5) node [inner sep=1.5pt,fill=white] (l9d) {$6$};}
\visible<1-18>{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10) {$2$};}
\visible<19>{\draw(2.5,-1.5) node [inner sep=1.5pt,fill=white] (l10b) {$7$};}

\visible<1->{\draw[-latex'] (l0) -- (l1);}
\visible<1->{\draw[-latex'] (l0) -- (l2);}
\visible<1-29>{\draw[-latex'] (l1) -- (l3);}
\visible<1-26>{\draw[-latex'] (l1) -- (l4);}
\visible<1-11>{\draw[-latex'] (l3) -- (l5);}
\visible<1-15>{\draw[-latex'] (l3) -- (l6);}
\visible<1-7>{\draw[-latex'] (l4) -- (l7);}
\visible<1-2>{\draw[-latex'] (l4) -- (l8);}
\visible<1-23>{\draw[-latex'] (l2) -- (l9);}
\visible<1-19>{\draw[-latex'] (l2) -- (l10);}

\end{tikzpicture}

\end{center}
}
\end{document}