arvore-AVL.tex

% !TEX encoding = ISO-8859-1
\section{Árvore AVL}
\label{sec:arvore-AVL}

\index{árvore!AVL}
O nome AVL é proveniente das iniciais dos sobrenomes dos dois
pesquisadores russos G.~M.~\underline{A}delson-\underline{V}elsky e
E.~M.~\underline{L}andis, que foram os primeiros a definir e realizar
trabalhos com esse tipo de árvore.

\index{fator de balanceamento}
Seja $n$ um nó de uma árvore binária, $ad_n$ e $ae_n$ as alturas da
sub-árvore esquerda e direita de $n$, respectivamente, e seja $k_n =
ae_n - ad_n $ o {\em fator de balanceamento\/} do nodo (i.e.~o fator
de balanceamento é igual ao valor da diferença entre as alturas de
suas sub-árvores).

Uma árvore AVL é uma árvore de pesquisa binária na qual $\delta_n$ é
igual a 0 ou 1 ou -1, para todo nodo $n$.

Por exemplo, a ávore binária de pesquisa abaixo à esquerda é uma
árvore AVL, enquanto a da direita não é. 

\begin{verbatim}
      5                 5
     / \               /
    2   6             2 
   /                 / 
  1                 1   
\end{verbatim}

O algoritmo de pesquisa em uma árvore AVL é o mesmo do algoritmo de
pesquisa em uma árvore binária de pesquisa. 

Os algoritmos de inserção e remoção são apresentados nas subseções
seguintes.

\subsection{Inserção}
\label{sec:insercao-em-arvores-AVL-versao-func}

\index{inserção!em árvore AVL}
\index{árvore!AVL!inserção}
\index{rotação!em árvore AVL}
Após inserção de nodo em uma árvore AVL, é feita uma verificação do
fator de balanceamento de cada nodo que está no caminho da raiz até o
nodo inserido. Se a inserção tornar o fator de balanceamento maior que
1 ou menor que -1, a sub-árvore com raiz nesse nodo é rebalanceada,
por meio de uma {\em rotação}, para que a condição-AVL volte a ser
satisfeita. Como a inserção de elemento em uma árvore pode aumentar a
altura da árvore em no máximo 1, o fator de balanceamento deve ser,
logo após a inserção de nodo na sub-árvore esquerda e antes do
rebalanceamento, no máximo igual a 2; e, logo após a inserção de nodo
na sub-árvore direita e antes do rebalanceamento, no mínimo igual a
-2.

Quando o fator de balanceamento é igual a 2, existem duas
possibilidades (outras duas possibilidades, que existem quando o fator
de balanceamento é igual a -2, são análogas). 

\newcommand{\altura}{{\it altura\/}}

A primeira possibilidade é mostrada no caso \verb+sobE+ abaixo. Temos
$\text{\altura\ (\verb+ee+) = \altura\ (\verb+d+)}$ antes da inserção
e o elemento, inserido na sub-árvore \verb+ee+, aumenta a altura de
\verb+ee+.

 Note que:
  \begin{enumerate}
    \item se
      $\altura\ (\verb+ee+) < \altura\ (\verb+d+)$ então a
      árvore continuaria sendo uma árvore AVL após a inserção de um
      nodo em \verb+ee+;
    \item se $\altura\ (\verb+ee+) > \altura\ (\verb+d+)$ então a
      árvore já não seria uma árvore AVL antes da inserção de um nodo
      em \verb+ee+.
  \end{enumerate}
   
A segunda possibilidade é mostrada no caso \verb+sobED+ abaixo. Temos
$\text{\altura\ (\verb+ved+) = \altura\ (\verb+d+)}$ antes da inserção
e o elemento, inserido em uma das sub-árvores de \verb+ved+, aumenta a
altura de \verb+ve+. Neste caso incluímos as sub-árvores de \verb+ved+
na figura, por motivos didáticos.

\begin{verbatim}
       Caso sobE      Caso sobED
           v              v
         /   \          /   \   
        ve    d        ve    d
       /  \           /  \                    
      ee  ed         ee   ved
                         / \
                       ede  edd                   

Árvore depois de rotacionada:

    Caso sobE          Caso sobED
     ve                   ved
    /  \                /     \ 
   ee   v             ve       v
       / \           /  \     / \ 
      ed  d         ee  ede edd  d

\end{verbatim}

O caso \verb+sobED+ pode ser expresso como \verb+sobE+ (aplicado ao
nodo com raiz \verb+ved+) seguido de \verb+sobD+ (aplicado ao mesmo
nodo).

%É importante notar que apenas um fator de balanceamento não é
%suficiente para determinar se uma árvore AVL necessita de rotação após
%uma inserção. Por exemplo, considere as duas árvores AVL a seguir:
%
%\begin{verbatim}
%      7                  7
%     /  \               /
%    3    8             3 
%   / \    \ 
%  2   5    9
% /     \ 
%1       6
%\end{verbatim}
%
%O fator de balanceamento da árvore com raiz \verb+7+ é igual a 1, nas
%duas árvores acima, antes da inserção.  No entanto, a inserção de
%\verb+4+ não quebra a condição de a árvore à esquerda ser AVL, ao
%contrário do que ocorre no caso da árvore à direita; após a inserção,
%e antes da rotação, que deve ser feita apenas na árvore à direita,
%temos:
%
%\begin{verbatim}
%     AVL              Não AVL 
%      7                  7
%     / \                /
%    3   8              3 
%   / \   \             \ 
%  2   5   9             4
% /   / \ 
%1   4   6
%\end{verbatim}

%A tarefa de determinar, usando apenas o próprio fator de
%balanceamento, a variação do fator de balanceamento após uma inserção,
%e demonstrar que tal variação é verificada em todos os casos, é
%deixada para trabalho futuro. Não encontramos na literatura textos que
%abordam o assunto de forma clara e precisa.

O armazenamento da altura em cada nodo evita ter que calcular a altura
de cada nodo que está no caminho da árvore até o nodo inserido, o que
seria desnecessariamente ineficiente.

\subsubsection{Versão funcional}

\index{inserção!em árvore AVL!versão funcional}
\index{árvore!AVL!inserção}
A inserção de elemento em árvore AVL pode ser feita em Haskell como a
seguir:

\index{\inh{ins}}
\index{\inh{sobE}}
\index{\inh{sobED}}
\index{\inh{sobD}}
\index{\inh{sobDE}}
\begin{center}
\begin{tabular}{l}
\begin{hask}{ins}{\decremento}
module AVL (ArvoreAVL, arvVazia, ins) where

type Altura      = Integer
data ArvoreAVL a = Vazia | Nodo a Altura (ArvoreAVL a) (ArvoreAVL a)

arvVazia = Vazia

ins:: (Show a, Ord a) => a -> ArvoreAVL a -> ArvoreAVL a
ins k Vazia              = Nodo k 1 Vazia Vazia
ins k arv@(Nodo v _ e d) = 
 case compare k v of 
  LT -> let e1@(Nodo v1 a1 _ _) = ins k e 
            ad = altura d
         in if a1 - ad == 2 -- condição AVL precisa ser restaurada
            then if k < v1  
                 then sobE  (Nodo v undefined e1 d)  
                 else sobED (Nodo v undefined e1 d)
            else Nodo v (max a1 ad + 1) e1 d
  GT -> let d1@(Nodo v1 a1 _ _) = ins k d 
            ae = altura e
         in if a1 - ae == 2 -- condição AVL precisa ser restaurada 
            then 
               if k > v1
               then sobD  (Nodo v undefined e d1) 
               else sobDE (Nodo v undefined e d1) 
            else Nodo v (max ae a1 + 1) e d1
  _ -> arv

sobE :: ArvoreAVL a -> ArvoreAVL a
sobE (Nodo v _ (Nodo ve _ ee ed) d) = Nodo ve a ee (Nodo v ad ed d) 
  where ad = max (altura ed) (altura d) + 1
        a  = max (altura ee) ad         + 1

sobD :: ArvoreAVL a -> ArvoreAVL a
sobD (Nodo v _ e (Nodo vd _ de dd)) = Nodo vd a (Nodo v ae e de) dd
  where ae = max (altura e) (altura de) + 1
        a  = max ae         (altura dd) + 1

sobED :: ArvoreAVL a -> ArvoreAVL a
sobED (Nodo v _ (Nodo ve _ ee (Nodo ved _ ede edd)) d) = 
       Nodo ved a (Nodo ve ae ee ede) (Nodo v ad edd d)
  where a  = max ae           ad           + 1
        ae = max (altura ee ) (altura ede) + 1
        ad = max (altura edd) (altura d  ) + 1

sobDE :: ArvoreAVL a -> ArvoreAVL a
sobDE (Nodo v _ e (Nodo vd _ (Nodo vde _ dee ded) dd)) = 
       Nodo vde a (Nodo v ae e dee) (Nodo vd ad ded dd)
  where a  = max ae           ad           + 1
        ad = max (altura ded) (altura dd ) + 1
        ae = max (altura e  ) (altura dee) + 1 

altura (Nodo _ a _ _) = a
altura Vazia          = 0

vazia Vazia = True
vazia _     = False
\end{hask}
\end{tabular}
\end{center}

No pior caso, temos $T(h) = T(h-1) + k$, onde $h$ é a altura da árvore
e $k$ é o tempo de execução referente aos cálculos de i) altura de uma
sub-árvore, ii) condição AVL e iii) rotação (uma das funções
\inh{sobE}, \inh{sobED}, \inh{sobD}, \inh{sobDE}). Todos os tempos de
i) a iii) têm complexidade $O(1)$. Logo (cf.~seção
\ref{sec:maior-elemento}): $T(h) \asymp h$, ou seja, considerando que
$h \asymp lg n$ em uma árvore balanceada (onde $n$ é o número de
elementos da árvore):

  \[ T(n) \asymp lg n \]

\subsubsection{Versão imperativa}

\index{inserção!em árvore AVL!versão imperativa}
\index{árvore!AVL!inserção}
A versão imperativa, mostrada abaixo, usa:
  
  \begin{itemize}

    \item função \ina{novoNodo} e função \ina{malloc}, como em \C:
      \ina{malloc} i) aloca área de memória para conter registro
      \ina{AVL} --- o tamanho da área a ser alocada é passada para
      \ina{malloc}, sendo o tamanho calculado pela função \ina{sizeof}
      ---, e ii) retorna apontador para área alocada;

    \item expressões condicionais, como em \C\ (introduzida na seção
      \ref{pesquisa-sequencial-em-arranjo-versao-imp});

    \item em \C, é necessário definir: \ina{typedef struct AVL AVL;}
      para poder usar apenas \ina{AVL} em vez de \ina{struct AVL};
      além disso, o uso de \ina{struct AVL} em vez de apenas \ina{AVL}
      em campo de \ina{AVL} é devido a como é definido (requerido) na
      linguagem \C.

 \end{itemize}

\index{\ina{ins}}
\index{\ina{sobE}}
\index{\ina{sobED}}
\index{\ina{sobD}}
\index{\ina{sobDE}}
\begin{center}
\begin{tabular}{l}
\begin{alg}{ins}{\decremento}
struct AVL 
  int chave, altura
  struct AVL *esq, *dir

int altura (AVL *p)
  return (p == NULL ? 0 : p->altura)
 
int max (int a, int b) 
  return (a > b ? a : b)
 
AVL* novoNodo (int chave)
    AVL* nodo    = (AVL*) malloc(sizeof(AVL))
    nodo->chave  = chave
    nodo->esq    = nodo->dir = NULL
    nodo->altura = 1
    return nodo

AVL* sobE (AVL* v)
    AVL* ve    = v ->esq
    AVL* ved   = ve->dir
    ve->dir    = v
    v ->esq    = ved
    v ->altura = max (altura (v->esq ), altura (v->dir ))+1
    ve->altura = max (altura (ve->esq), v->altura       )+1
    return ve
 
AVL* sobD (AVL* v) 
    AVL* vd    = v ->dir
    AVL* vde   = vd->esq
    vd->esq    = v
    v ->dir    = vde
    v ->altura = max (altura (v->esq ), altura (v->dir ))+1
    vd->altura = max (v->altura       , altura (vd->dir))+1
    return vd

AVL* sobED (AVL* v) 
  v->esq = sobD (v->esq)  // v->esq->dir sobe (se torna v->esq)
  return sobE(v)          // v->esq      sobe (se torna v)

AVL* sobDE (AVL* v)
  v->dir = sobE (v->dir)  // v->dir->esq sobe (se torna v->dir)
  return sobD(v)          // v->dir      sobe (se torna v)

AVL* ins (AVL* nodo, int chave)
    if (nodo == NULL) return novoNodo (chave)
    if (chave < nodo->chave)
      nodo->esq    = ins (nodo->esq, chave)
      nodo->altura = max (altura (nodo->esq), altura (nodo->dir)) + 1
     if (altura (nodo->esq) - altura (nodo->dir) == 2) // condição AVL precisa ser restaurada
	if (chave < nodo->esq->chave) 
	  return sobE (nodo)
	else return sobED (nodo)
    else if (chave > nodo->chave) 
            nodo->dir    = ins (nodo->dir, chave)
            nodo->altura = max (altura (nodo->esq), altura (nodo->dir)) + 1
            if (altura(nodo->dir) - altura(nodo->esq) == 2)  // condição AVL precisa ser restaurada
	       if (chave > nodo->dir->chave)
	          return sobD (nodo)
	       else return sobDE (nodo)

    return nodo;
\end{alg}
\end{tabular}
\end{center}

A complexidade de tempo de \inh{ins} é a mesma da versão funcional:
$T(n) \asymp lg n$.

\subsection{Remoção}

\index{remoção!de árvore AVL!versão funcional}
\index{árvore!AVL!remoção}
A remoção de um nodo de uma árvore AVL é feita de modo similar à
inserção, com a verificação do fator de balanceamento de cada nodo que
está no caminho da raiz até o removido. 

A versão funcional é apresentada a seguir. A versão imperativa é
deixada como exercício (exercício \ref{ex:alg-rem-arv-AVL}).

\subsubsection{Versão funcional}

A remoção de um elemento de uma árvore AVL pode ser feita em Haskell
como a seguir:

\begin{center}
\begin{tabular}{l}
\begin{hask}{del}{\decremento}
del:: (Show a, Ord a) => a -> ArvoreAVL a -> ArvoreAVL a
del k Vazia              = Vazia
del k arv@(Nodo v _ e d) = 
 case compare k v of 
  LT -> let e1 = del k e; ad = altura d; a1 = altura e1
         in if ad - a1 == 2 -- condição AVL precisa ser restaurada: _d_ sobe 
            then sobD (Nodo v undefined e1 d)
            else Nodo v (max a1 ad + 1) e1 d
  GT -> let d1 = del k d; ae = altura e; a1 = altura d1
         in if ae - a1 == 2 -- condição AVL precisa ser restaurada: _e_ sobe 
            then sobE (Nodo v undefined e d1)
            else Nodo v (max ae a1 + 1) e d1
  _  -> if vazia e then d else
        if vazia d then e else Nodo v' (max (altura e') (altura d') + 1) e' d'
  where
    (Nodo v' _ e1 d1, e', d')  
       | altura e >= altura d = (sobE (Nodo v undefined e d), e1, del k d1) 
       | otherwise            = (sobD (Nodo v undefined e d), del k e1, d1) 

\end{hask}
\end{tabular}
\end{center}