\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}
%----------------------------

\usepackage{srcltx}
\usepackage{graphicx}

\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below 
  {\sl}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\bfseries}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
                                %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\newtheorem{teorema}             {Teorema}       
\newtheorem{Afirmativa}[teorema] {Afirmativa}         
\newtheorem{lema}      [teorema] {Lema}         
\newtheorem{corolario} [teorema] {Corolário}     
\newtheorem{fato}      [teorema] {Fato}          
\newtheorem{conjectura}[teorema] {Conjectura}    
\newtheorem{problema}  [teorema] {Problema}       

\theoremstyle{note}
\newtheorem{propriedade}  [teorema] {Propriedade}       
\newtheorem{definicao}  [teorema] {Definição}       
\newtheorem{exercicio}  [teorema] {Exercício}       

\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\let\:=\colon

\def\prof{\mathop{\text{\rm prof}}\nolimits}
\def\Ave{\mathop{\text{\rm Ave}}\nolimits}

\title{%
Árvores Binárias Aleatórias%
}

\author{%
  Yoshiharu Kohayakawa}
%
%\address{Instituto de Matem\'atica e Estat\'{\i}stica, Universidade de S\~ao
%  Paulo, Rua do Mat\~ao 1010, 05508--090~S\~ao Paulo, SP}
%
%\email{yoshi@ime.usp.br}

\date{16 de maio de 2007}

\begin{document}
\maketitle
\pagestyle{plain}
\footskip=20pt

\section{Árvores binárias}
\label{sec:arvores-binarias}

\subsection{Árvores binárias e o número delas}
\label{sec:arvores-binarias-e}
Começamos com a definição de árvores binárias.

\begin{definicao}
  \label{def:ABs}
  Uma \textit{árvore binária} pode ter apenas um \textit{nó externo} e nenhum
  \textit{nó interno}, ou pode consistir de um nó interno~$r$, chamado
  \textit{raiz}, e duas subárvores binárias: a \textit{subárvore
    esquerda}~$T_L$ de~$r$ e a \textit{subárvore direita}~$T_R$ de~$r$; essas
  subárvores são também árvores binárias.  A raiz de~$T_L$ é o \textit{filho
    esquerdo} de~$r$ e a raiz de~$T_R$ é o filho direito de~$r$.
  Naturalmente, o nó~$r$ é o \textit{pai} de seus filhos.
\end{definicao}

Há uma árvore com~$0$ nós internos, uma com~$1$ nó interno, e duas com~$2$ nós
internos.  As cinco árvores com~$3$ nós internos aparecem na
Figura~\ref{fig:3_nos_internos}.

\begin{figure}[h]
\includegraphics{123_out}\qquad\quad
\includegraphics{132_out}\qquad\quad
\includegraphics{213_out}\qquad\quad
\includegraphics{312_out}\qquad\quad
\includegraphics{321_out}
%\input{bad_tuples.tex}
% \begin{picture}(0,0)
% \includegraphics{123_out}
% \end{picture}
\caption{As 5 árvores binárias com 3 nós internos (nós externos não
  estão representados nos diagramas)}\label{fig:3_nos_internos}
\end{figure}

Na Tabela~\ref{tab:Catalans}, temos o número de árvores binárias~$t_N$ com~$N$
nós internos para valores pequenos de~$N$.

\begin{table}[h]
\begin{tabular}[c]{|c||c|c|c|c|c|c|c|c|c|c|}
\hline % Saída
$N$ &% 
1 &% 
2 &% 
3 &% 
4 &% 
5 &% 
6 &% 
7 &% 
8 &% 
9 &% 
10 % 
\\ \hline % Chegada
$t_N$ &%
1 &% 
2 &% 
5 &% 
14 &% 
42 &% 
132 &% 
429 &% 
1430 &% 
4862 &% 
16796 %  
\\ \hline
\end{tabular}
\vspace{7pt}
\caption{Número de árvores binárias~$t_N$ com~$N$ nós internos}
\label{tab:Catalans}
\end{table}

\begin{exercicio}
  \label{ex:4_nos_internos}
  Desenhe todas as~$14$ árvores binárias com~$4$ nós internos.
\end{exercicio}

\begin{teorema}
  \label{thm:Catalan}
  O número de árvores binárias~$t_N$ com~$N$ nós internos é dado por
  \begin{equation}
    \label{eq:Catalan}
    t_N={1\over N+1}{2N\choose N}={4^N\over\sqrt{\pi N^3}}\(1+O\(1\over N\)\).
  \end{equation}
\end{teorema}

\subsection{Profundidade média de um nó em uma árvore}
\label{sec:prof-media-de-1}
Definimos agora a profundidade de um nó em uma árvore.

\begin{definicao}
  \label{def:prof}
  A \textit{profundidade}~$\prof(x)$ de um nó~$x$ em uma árvore é~$0$ se~$x$ é
  a raiz da árvore e é~$\prof(p)+1$ se~$x$ tem pai~$p$.
\end{definicao}

Dada uma árvore binária~$T$, estamos interessados na profundidade média de
seus nós:
\begin{equation}
  \label{eq:Ave_prof}
  \Ave_x(\prof(x))={1\over N}\sum_x\prof(x),
\end{equation}
onde a soma é sobre todo nó interno~$x$ de~$T$ e~$N$ é o número de nós
internos em~$T$.

\section{Árvores binárias aleatórias}
\label{sec:arvor-binar-aleat}

\subsection{Árvores aleatórias uniformes}
\label{sec:arvor-aleat-unif}
Fixe um natural~$N$.  Podemos gerar uma árvore binária aleatória com~$N$ nós
internos simplesmente sorteando, uniformemente ao acaso, uma dentre as~$t_N$
árvores binárias com~$N$ nós internos.  Vamos denotar tal árvore aleatória
por~$U_N$.

\subsection{Árvores aleatórias de busca}
\label{sec:arvor-aleat-busca}
Podemos gerar uma árvore binária aleatória com~$N$ nós internos da seguinte
outra forma.  

Podemos usar árvores binárias para armazenar uma coleção de dados, armazenando
um dado por nó interno.  Neste contexto, supomos que os dados armazenados
admitem uma ordem total e que os dados são armazenados de acordo com a
\textit{propriedade de árvore binária de busca}: suponha que o dado armazenado
em um dado nó~$x$ é~$D$; então~$D$ é maior que os dados armazenados nos nós da
subárvore esquerda de~$x$ e~$D$ é menor que os dados armazenados nos nós da
subárvore direita de~$x$.  Quando usamos árvores binárias como tal estrutura
de dados, obtemos o que é usualmente conhecido como \textit{árvores binárias
  de busca}.

Para gerar uma árvore binária aleatória com~$N$ nós internos, podemos gerar
uma permutação aleatória~$\sigma$ de~$\{1,\dots,N\}$ uniformemente ao acaso, e
então inserir~$\sigma(1),\sigma(2),\dots$ em uma árvore binária de busca
inicialmente vazia (um dado inserido gera um novo nó no ``fundo'' da árvore).
Tal processo gera uma árvore binária de busca aleatória com~$N$ nós internos
e, se ignoramos os dados armazenados em tal árvore, temos uma árvore binária
aleatória.  Denotemos tal árvore aleatória por~$B_N$.

Naturalmente, o processo descrito acima induz uma distribuição de
probabilidade sobre as~$t_N$ árvores binárias com~$N$ nós internos.  Essa
distribuição não coincide com a distribuição uniforme (para~$N\geq3$).  

\begin{exercicio}
  \label{ex:dist_4_nos_internos}
  Qual é a distribuição de probabilidade induzida pelo processo acima sobre
  as~$5$ árvores da Figura~\ref{fig:3_nos_internos}?  Qual é a distribuição
  induzida sobre as~$t_4=14$ árvores binárias com~$4$ nós internos?
\end{exercicio}

\section{Profundidade média de nós em árvores aleatórias}
\label{sec:prof-media-de}

Estamos interessados na profundidade média dos nós internos em árvore
aleatórias (veja~\eqref{eq:Ave_prof}).  De fato, se usamos uma árvore binária
como uma árvore binária de busca, essa profundidade média é o valor esperado
do número de comparações necessárias para localizar um dado armazenado na
árvore, supondo que fazemos busca dos dados de acordo com a distribuição
uniforme (a probabilidade de buscarmos um particular dado é~$1/N$ se há~$N$
dados armazenados na árvore).

Lembre que definimos as árvores binárias aleatórias~$U_N$ e~$B_N$ (veja
Seções~\ref{sec:arvor-aleat-unif} e~\ref{sec:arvor-aleat-busca}).

\begin{teorema}
  \label{thm:random_Ave_prof}
  O valor esperado da profundidade média dos nós internos de~$U_N$ é
  \begin{equation}
    \label{eq:random_Ave_prof}
    \(1+{1\over N}\)4^N{2N\choose N}^{-1}-3-{1\over N}
    =\sqrt{\pi N}-3+O(1/\sqrt N).
  \end{equation}
\end{teorema}

\begin{teorema}
  \label{thm:random_BST}
  O valor esperado da profundidade média dos nós internos de~$B_N$ é
  \begin{equation}
    \label{eq:random_BST}
    2(H_{N+1}-1)\(1+{1\over N}\)-2
    =2\log N-2(2-\gamma)+O\(\log N\over N\),
  \end{equation}
  onde~$H_{N+1}=1+1/2+\dots+1/(N+1)$ é o $(N+1)$-ésimo número harmônico
  e~$\gamma=0.5772156694\dots$ é a constante de Euler.
\end{teorema}

Vemos de~\eqref{eq:random_Ave_prof} e~\eqref{eq:random_BST} que a profundidade
média dos nós em~$U_N$ é \textit{muito maior} que a profundidade média dos nós
em~$B_N$: a primeira é~$\sim\sqrt{\pi N}=\Theta(\sqrt N)$ e a segunda
é~$\sim2\log N=\Theta(\log N)$.

\begin{exercicio}
  \label{ex:prof_rBST}
  Seja~$C_N$ o valor esperado da profundidade média dos nós internos de~$B_N$.
  Prove que~$C_1=0$ e que, para~$N>0$, 
  \begin{equation}
    \label{eq:prof_rBST}
    NC_N=N-1+{1\over N}\sum_{1\leq k\leq N}\big((k-1)C_{k-1}+(N-k)C_{N-k}\big).
  \end{equation}
\end{exercicio}

\begin{exercicio}
  \label{ex:prof_rBST.sol}
  Prove que~$C_N$ é dado pela equação~\eqref{eq:random_BST}.
\end{exercicio}

\section{Algumas árvores aleatórias}
\label{sec:algum-arvor-aleat}
Para visualizarmos a diferença dramática entre~\eqref{eq:random_Ave_prof}
e~\eqref{eq:random_BST}, podemos gerar algumas~$U_N$ e algumas~$B_N$ e podemos
desenhá-las.  As seis árvores a seguir tem~$N=400$ nós internos.  Três delas
foram geradas com a distribuição de~$U_{400}$ e as outras três foram geradas
com a distribuição de~$B_{400}$.

\begin{figure}[h]
\includegraphics[scale=.95,angle=90]{400_Catalan_out}
\caption{Uma $U_{400}$}\label{fig:400_Catalan}
\end{figure}

\begin{figure}[h]
\includegraphics[scale=.95,angle=90]{400_Catalan_2_out}
\caption{Outra $U_{400}$}\label{fig:400_Catalan.2}
\end{figure}

\begin{figure}[h]
\includegraphics[scale=.95,angle=90]{400_Catalan_3_out}
\caption{Outra $U_{400}$}\label{fig:400_Catalan.3}
\end{figure}

\begin{figure}[h]
\includegraphics[scale=.95,angle=180]{400_BST_out}
\qquad
\qquad
\includegraphics[scale=.95,angle=180]{400_BST_2_out}
\caption{Duas $B_{400}$}\label{fig:400_BST}
\end{figure}

% \begin{figure}[h]
% \includegraphics[scale=.95,angle=180]{400_BST.2_out}
% \caption{Outra $B_{400}$}\label{fig:400_BST.2}
% \end{figure}

\begin{figure}[h]
\includegraphics[scale=.95,angle=180]{400_BST_3_out}
\caption{Outra $B_{400}$}\label{fig:400_BST.3}
\end{figure}

\begin{exercicio}
  \label{ex:rBST}
  Escreva um programa que, dado~$N$, gera uma~$B_N$.  
\end{exercicio}

\begin{exercicio}
  \label{ex:rU_N}
  Escreva um programa que, dado~$N$, gera uma~$U_N$.
\end{exercicio}



\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 

