ÛßßßßßÛ
                                   Û TDA Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

TDA (Tipo de Dato Abstracto) ‚ unha abstracci¢n matem tica, un conxunto de                              
operaci¢ns. Na definici¢n do tipo de dato na secci¢n type (morfolox¡a do TDA)
non se fai menci¢n a como son esas operaci¢ns que definen o TDA, sen¢n que 
estas van despois en forma de procedementos e funci¢ns (sintaxe do TDA).
As avantaxes dun TDA son:
     -As operaci¢ns escr¡bense unha soa vez e son empregadas polos
     restantes m¢dulos do programa.
     -As correci¢ns nos m¢dulos das operaci¢ns que definen o TDA
     son transparentes ¢ usuario e ¢s programas que empreguen o TDA.



                              ÛßßßßßßßßßßßÛ
                              Û CONXUNTOS Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß
 
Un conxunto ‚ un TDA (tipo de dato abstracto) que ‚ unha colecci¢n de 
elementos na cal non hai elementos repetidos (un elemento aparece unha
vez ou non aparece) e adem is non est n almacenados en ning£nha orde 
determinada.

exemplo:
          { 1 , 3 , 6 , 2 , 4 , 5 } ‚ un conxunto
          { 1 , 2 , 3 , 4 , 5 , 6 } ‚ o mesmo conxunto
          { 1 , 2 , 2 , 4 , 5 , 6 } non ‚ un conxunto

Os conxuntos def¡nense mediante unha enumeraci¢n dos elementos:

          X = { 1 , 2 , 3 , 4 }

ou mediante unha serie de condici¢ns que os definen:

          X = { x î Z / 1 ó x ó 4 }

A relaci¢n b sica ‚ a de pertencia (î) ou non dun elemento a un conxunto.
O conxunto baleiro ‚ aquel que non t‚n elementos.
Dise que un conxunto A est  inclu¡do noutro conxunto B se t¢dolos
elementos de A tam‚n pertencen a B.

operaci¢ns:
UNION          A U B = { x / x î A   ¢   x î B }
INTERSECCION   A ï B = { x / x î A   e   x î B }
DIFERENCIA     A - B = { x / x î A   e   x NON î B }

Implementaci¢n dun conxunto mediante un vector booleano ("mapa de bits"):
Para representar un conxunto de enteiros 1..n p¢dese empregar un array de 
valores booleanos. Un elemento pertence ¢ conxunto se e so se o valor da 
s£a compo¤ente ‚ true. Esta representaci¢n p¢dese xeralizar para calquera
tipo de conxunto e non so para conxuntos de enteiros.

type
     tipoelemento : 1 .. n ;
     conxunto : array [ tipoelemento ] of boolean ;

o conxunto { 1 , 4 } dentro do universo 1..6 repres‚ntase como 
|true|false|false|true|false|false|
   1    2     3     4    5     6      ¡ndices

Caracter¡sticas:
-‚ un vector unidimensional onde os elementos gardan valores booleanos
-‚ v lido cando hai un n£mero finito de elementos
-os datos do conxunto deben ser datos simples de tipo ordinal

Avantaxes:
-operaci¢ns de uni¢n e intersecci¢n real¡zanse de xeito moi r pido
-se o conxunto colle nunha palabra do ordenador (word) o ordenador
realiza a operaci¢n dunha soa vez (procesa o conxunto dunha vez);
as operaci¢ns polo tanto son rapid¡simas

Inconvintes:
-limitaci¢n polo n£mero finito de elementos
-deben estar nun subrango
-datos de tipo simple

Agora imos implementar algunha das funci¢ns b sicas para este tipo de
conxuntos:

*Ca declaraci¢n TYPE que definimos arriba e a idea anterior, a
inicializaci¢n a baleiro sup¢n rechear t¢dalas compo¤entes a false.

procedure conxuntobaleiro ( var a : conxunto ) ;
var
   i : integer ;
begin
     for i := 1 to n do { a complexidade da operaci¢n ‚ n }
         a[i]:= false ;
end ;

*Para mirar se un conxunto ‚ baleiro ou non buscamos a primeira compo¤ente que
sexa true. Se non atopamos ningunha o conxunto ‚ baleiro.

function e_baleiro ( a : conxunto ) : boolean ;
var
   i : integer ;
   nonbaleiro : boolean ;
begin
     i := 1 ;
     repeat { a complexidade da operaci¢n ‚ n, a¡nda que en media ‚ menos }
            nonbaleiro := a[i] ;
            i := i + 1 ;
     until (i>n) or nonbaleiro ;
     e_baleiro := not nonbaleiro ;
end ;

*A pertencia dec¡dese simplemente mirando se a compo¤ente do elemento
que buscamos est  a true ou no. An logamente insertar un elemento consiste en
colocar a s£a compo¤ente a true e borrar colocala a false.

function pertence ( a : conxunto ; i : tipoelemento ) : boolean ;
begin
     pertence := a[i] ; { a complexidade da operaci¢n ‚ 1 }
end ;

procedure insertar ( var a : conxunto ; i : tipoelemento ) ;
begin
     a[i] := true ; { a complexidade da operaci¢n ‚ 1 }
end ;

procedure borrar  ( var a : conxunto ; i : tipoelemento ) ;
begin
     a[i] := false ; { a complexidade da operaci¢n ‚ 1 }
end ;

*Para a uni¢n, intersecci¢n e diferencia utilizaremos os conectivos l¢xicos

*Para a uni¢n empr‚gase a disxunci¢n (pertence a un ou pertence ¢ outro)

procedure union ( a , b : conxunto ; var c : conxunto ) ;
var
   i : integer ;
begin
     for i := 1 to n do
         c[i] := a[i] or b[i] ; { a complexidade da operaci¢n ‚ n }
end ;

*Para a intersecci¢n empr‚gase a conxunci¢n (pertence a un e pertence
¢ outro)

procedure interseccion ( a , b : conxunto ; var c : conxunto ) ;
var
   i : integer ;
begin
     for i := 1 to n do
         c[i] := a[i] and b[i] ; { a complexidade da operaci¢n ‚ n }
end ;

*Para a diferencia empr‚gase a conxunci¢n e a negaci¢n (pertence a un e non
¢ outro)

procedure diferencia ( a , b : conxunto ; var c : conxunto ) ;
var
   i : integer ;
begin
     for i := 1 to n do
         c[i] := a[i] and not b[i] ; { a complexidade da operaci¢n ‚ n }
end ;

*Realizaci¢n mediante un vector cos elementos.
Esta realizaci¢n prop¢n gardar t¢dolos elementos do conxunto nun vector
un detr s do outro, utilizando so as primeiras compo¤entes necesarias.

const
     maxel = { estimaci¢n do m ximo n£mero de elementos posibles no conxunto }
type
    tipoelemento = { tipo de dato que se quere gardar no conxunto }
    conxunto = record
                     elementos : array [ 1 .. maxel ] of tipoelemento ;
                     cardinal : 0 .. maxel ;
               end ;

cardinal indica o derradeiro elemento do vector utilizado. Empr‚gase o nome
cardinal porque tam‚n indica o n£mero de elementos que t‚n o conxunto.

exemplo:      1  2  3  ... maxel     ¡ndices
              1  4

              este ‚ o conxunto {1,4}, cardinal val 2

*Desta maneira, o conxunto baleiro queda definido se colocamos cardinal a 0.
A decisi¢n de se un conxunto ‚ baleiro ‚ agora inmediata.

procedure conxuntobaleiro ( var a : conxunto ) ;
begin
     a . cardinal := 0 ; { complexidade 1 }
end ;

function e_baleiro ( a : conxunto ) : boolean ;
begin
     e_baleiro := a . cardinal = 0 ; { complexidade 1 }
end ;

*Para determinar se un elemento pertence ou non ¢ conxunto, simplemente 
faise unha b£squeda no vector dende a compo¤ente 1 ata a cardinal do
conxunto.

procedure insertar ( var a : conxunto ; i : tipoelemento ) ;
begin
     if not pertence ( a , i ) then
        with a do
             if cardinal = maxel
             then erro ( 'non hai sitio dispo¤ible' )
             else begin
                  cardinal := cardinal + 1 ; { complexidade n }
                  elemento [ cardinal := i ;
             end ;
end ;

function pertence ( a : conxunto ; i : tipoelemento ) : boolean ;
var
   j : integer ;
   esta : boolean ;
begin
     esta := false ;
     with a do
          while ( j <= cardinal ) and not esta do
                if elementos [ j ] = i
                then esta := true
                else j := j + 1 ;
     pertence := esta ;
end ;

*Cando se tenta insertar e non queda sitio dispo¤ible no vector para
almacenalo prod£cese un erro. Este procedemento erro tam‚n se
utilizar  para a uni¢n.

*Borrado: primeiro local¡zase o elemento dentro do vector. Conseguido
isto reempr zase polo derradeiro elemento e decrem‚ntase cardinal nunha
unidade.

procedure borrar ( var a : conxunto ; i : tipoelemento ) ;
var
   j : integer ;
   esta : boolean ;
begin
     j := 0 ;
     esta := false ;
     with a do begin
          while ( j < cardinal ) and not esta do begin
                j := j + 1 ;                            { complexidade n }
                esta := elemento [ j ] = i ;
          end ;
          if esta then begin
             elementos [ j ] := elementos [ cardinal ] ;
             cardinal := cardinal - 1 ;
          end ;
     end ;
end ;

*Uni¢n: todo o conxunto a e os elementos de b que non estean en a.

procedure union ( a , b : conxunto ; var c : conxunto ) ;
var
   i , j : integer ;
begin
     with c do begin
          for i := 1 to a . cardinal do
              elementos [ i ] := a . elementos [ i ] ;
          j := a . cardinal ;
          for i := 1 to b . cardinal do
          if not pertence ( a , b . elementos [ i ] ) then
             if j = maxel
             then erro ( 'non hai sitio dispo¤ible' )
             else begin
                  j := j + 1 ;   { complexidade card(a) + card(b) }
                  elementos [ j ] := b . elementos [ i ] ;
             end ;
          cardinal := j ;
     end ;
end ;

*Intersecci¢n: perc¢rrese o conxunto a insertando en c so aqueles
elementos que estean tam‚n en b.

procedure interseccion ( a , b : conxunto ; var c : conxunto ) ;
var
   i , j : integer ;
begin
     with c do begin
          j := 0 ;
          for i := 1 to a . cardinal do
              if pertence ( b , a . elementos [ i ] )
              then begin
                   j := j + 1 ;  { complexidade card(a) + card(b) }
                   elementos [ j ] := a . elementos [ i ] ;
              end ;
              cardinal := j ;
     end ;
end ;

*Diferencia : perc¢rrese o conxunto a e g rdanse en c so os elementos
que non estean en b.

procedure diferencia ( a , b : conxunto ; var c : conxunto ) ;
var
   i , j : integer ;
begin
     with c do begin
          j := 0 ;
          for i := 1 to a . cardinal do
              if not pertence ( b , a . elementos [ i ] )
              then begin
                   j := j + 1 ;  { complexidade card(a) + card(b) }
                   elementos [ j ] := a . elementos [ i ] ;
              end ;
              cardinal := j ;
     end ;
end ;

                              
                              ÛßßßßßßßÛ
                              Û COLAS Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

As colas son un tipo de dato abstracto que se caracter¡zan por unha
estructura FIFO. O primeiro elemento que entra ‚ o primeiro que sae.
A entrada   cola so se pode facer por un dos dous extremos
e a sa¡da polo outro extremo.

As colas caracter¡zanse polo xeito en que se tratan os elementos que hai
nelas. Se accedemos a un elemento intermedio da cola inmediatamente
deixa de ser unha cola porque non a estamos tratando como tal.

De cote ch mase final da cola ¢ sitio polo que entran os elementos
e principio ou cabeza por onde saen, como nunha cola normal.

A lectura nunha cola implica que o elemento lido sae da cola.
Non se pode ler d£as veces o mesmo elemento.

Deque ou bicola ‚ o TDA no que se pode producir a e/s polo principio 
ou polo final.
A bicola de entrada restrinxida ‚ o TDA no que se pode sacar
elementos polo principio ou polo final pero so se poden meter polo
final.

As colas de prioridades soen ser colas de colas ordenadas por unha
xerarqu¡a arbitraria.
­Nalgunhas implementaci¢ns de colas de prioridades d se o fen¢meno curioso 
de que se accede ¢s elementos intermedios! sen que isto supo¤a que se viola
o concepto de cola.

IMPLEMENTACION ESTATICA DAS COLAS (en Pascal, mediante arrays)

PRIMEIRA IMPLEMENTACION
A entrada (final) ‚ fixa mentres que a sa¡da (principio) var¡a dentro
do rango reservado.
-Avantaxes: sinxeleza.
-Inconvinte: limitaci¢n de memoria; desprazamento cada vez que se
inserta un elemento na cola.
{--------------------------------------------------------------------------}
program
       colas ;
const
     ini = 1 ; { ­chamo ini ¢ final da cola, por onde entran os elementos! }
     max = 5 ;
type
   tcola = record
                 arreglo : array [ ini .. max ] of char ;
                 cabeza : integer ;
           end ;
var
   cola : tcola ; c : char ; i : integer ;
{--------------------------------------------------------------------------}
procedure cls ;
          var
             i : integer ;
          begin
               for i := 1 to 24 do writeln ;
          end ;
{--------------------------------------------------------------------------}
procedure inicializar ( var cola : tcola ) ;
          begin
               cola . cabeza := ini - 1 ;
          end ;
{--------------------------------------------------------------------------}
function e_baleira ( cola : tcola ) : boolean ;
         begin
              e_baleira := cola . cabeza = ini - 1 ;
         end ;
{--------------------------------------------------------------------------}
function e_chea ( cola : tcola ) : boolean ;
         begin
              e_chea := cola . cabeza = max ;
         end ;
{--------------------------------------------------------------------------}
procedure insertar ( var cola : tcola ; c : char ) ;
          var
             i : integer ;
          begin
               if not e_chea ( cola ) then begin
                  for i := cola . cabeza downto ini do
                      cola . arreglo [ i + 1 ] := cola . arreglo [ i ] ;
                  cola . cabeza := cola . cabeza + 1 ;
                  cola . arreglo [ ini ] := c ;
               end ;
          end ;
{--------------------------------------------------------------------------}
procedure sacar ( var cola : tcola ) ;
          var
             i : integer ;
          begin
               if not e_baleira ( cola ) then begin
                  write ( 'Saiu o elemento: ' ) ;
                  writeln ( cola . arreglo [ cola . cabeza ] ) ;
                  cola . cabeza := cola . cabeza - 1 ;
               end ;
          end ;
{--------------------------------------------------------------------------}
procedure amosa_cola ( cola : tcola ) ;
          var
             i : integer ;
          begin
               for i := ini to cola . cabeza do
                   write ( cola . arreglo [ i ] , ' ' ) ;
               writeln ;
          end ;
{--------------------------------------------------------------------------}
begin
     inicializar ( cola ) ; randomize ; cls ;
     repeat
           write ( 'a cola ‚: ' ) ; amosa_cola ( cola ) ;
           writeln ( '1 - e_baleira' ) ;
           writeln ( '2 - e_chea' ) ;
           writeln ( '3 - insertar' ) ;
           writeln ( '4 - sacar' ) ;
           readln ( i ) ;
           case i of
                1 : writeln ( e_baleira ( cola ) ) ;
                2 : writeln ( e_chea ( cola ) ) ;
                3 : insertar ( cola , chr ( random ( 256 ) ) ) ;
                4 : sacar ( cola ) ;
           end ;
     until false ;
end .

--------------------------------------------------------------------------
SEGUNDA IMPLEMENTACION
Para evitar o desprazamento dos elementos da cola que se produc¡a
na anterior implementaci¢n cando se introduc¡a un novo elemento, 
nesta segunda implementaci¢n tanto a fronte da cola (a cabeza, o inicio)
como o final son ¡ndices variables.

A cola ‚ circular: o seguinte ¢ derradeiro ‚ o primeiro e o anterior ¢
primeiro ‚ o derradeiro.

O problema que se plantexa ‚ o de determinar cando a cola est  baleira e
cando est  chea.

cola de 5 elementos, O ‚ out (fronte) e I ‚ in (final):

1 2 3 4 5   1 2 3 4 5   1 2 3 4 5   1 2 3 4 5   1 2 3 4 5   1 2 3 4 5
_ _ _ _ _   _ _ _ _ d   _ _ _ g d   _ _ v g d   _ k v g d   _ k v g _
      O I           I         I O       I   O     I     O     I   O
                    O

1 2 3 4 5   1 2 3 4 5  Vimos de cagala porque a situaci¢n inicial incit banos
x k v g _   x k v g h  a pensar que cola_baleira := fronte = final - 1
I     O           O I  pero aqu¡ est  chea e esta condici¢n c¢mprese.

Soluci¢ns posibles:

-Considerar que o rango v lido ‚ de 1 a n e a posici¢n 0 ‚ nula.
 As¡, cando O + 1 = I (ousexa fronte ‚ final -1) a cola est  chea, e cando
 a cola est  baleira tanto fronte como final apuntan a 0 (valen 0).

-Levar un simple contador de elementos que hai na cola.
-Perder unha celda, fronte apunta ¢ anterior do que hai que sacar e final
 apunta ¢ derradeiro que entrou.

 Inicializar : fronte := final := calquera posici¢n v lida do rango
 Baleira := final = fronte
 Chea := final + 1 = fronte
                                              (final=I fronte=O)
1 2 3 4 5   1 2 3 4 5   1 2 3 4 5   1 2 3 4 5   1 2 3 4 5   1 2 3 4 5
_ _ _ _ _   _ _ _ _ x   ¤ _ _ _ x   ¤ s _ _ x   ¤ s h _ d   ¤ s h _ _
      O           O I   I     O       I   O         I   O       I   O
      I                                          (cheo)


A implementaci¢n din mica de colas faise mediante listas simplemente
enlazadas nas que se inserta polo principio e se extrae polo final
ou ins‚rtase polo final e se extrae polo principio.

Nas colas de prioridades existe un n£mero asociado   informaci¢n que
indica un grao de xerarqu¡a.

A implementaci¢n dunha cola de prioridades pode ser mediante unha lista
ordenada por prioridades (­d se o fen¢meno curioso de que se accede ¢s
elementos intermedios!) ou mediante unha lista de colas. En calquera caso o
primeiro criterio de ordenaci¢n ‚ o de prioridade e o segundo o fifo.
A lista de colas ‚ unha cola principal de nodos cabeceira contendo o
n£mero de prioridade, de cada un dos cales pendura unha cola fifo de
elementos desa mesma prioridade.

Inserci¢n nunha cola de prioridades:

SE a lista principal ‚ baleira
ENT crear nodo cabeceira, gardar nel a prioridade do elemento que entra
    e crear un nodo £nico pendurando deste que garde ¢ elemento que entra
SENON
    SE a prioridade do que entra ‚ maior que a do primeiro nodo cabeceira
    ENT insertar ¢ principio da lista de colas
    SENON
        MENTRES o seguinte cabeceira non sexa nulo
              E a prioridade do seguinte cabeceira sexa maior ou igual
                                                  que a do que entra
        FACER avanzar unha posici¢n
                   ------------------------------------------------------
                   exemplo 10=maxprio 1=minprio insertar 3

                   ...-> 7 -> 5 -> X  ou ben ...-> 7 -> 3 -> X  ou ben
                              ^                         ^
                   ...-> 7 -> 5 -> 2 ->... ou ben ...-> 7 -> 5 -> 3 ->...
                              ^                                   ^
                   ------------------------------------------------------
        SE o actual cabeceira ‚ da mesma prioridade que o que entra
        ENT insertar na cola que pendura de ‚l
        SENON
            crear novo nodo cabeceira
            insertalo na lista principal entre o actual e o seguinte
            crear primeiro nodo que pendura do novo cabeceira e meter o novo
                                                                   elemento

                              ÛßßßßßßßÛ
                              Û PILAS Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß 

As pilas son un tipo de dato abstracto que se caracterizan por unha
estructura LIFO. O derradeiro elemento que entra ‚ o primeiro que sae.
A entrada e a sa¡da so se poden facer por un dos dous extremos.

As pilas caracter¡zanse polo xeito en que se tratan os elementos que hai
nelas. Se accedemos a un elemento intermedio da pila inmediatamente
deixa de ser unha pila porque non a estamos tratando como tal.

Na memoria RAM hai unha parte que se chama stack que ‚ unha pila onde
se gardan as variables dos procesos. Para as variables globais 
res‚rvase espacio en tempo de compilaci¢n mentres que para as locais se
reserva espacio en tempo de execuci¢n a¡nda que se definen en tempo de
compilaci¢n. As variables locais so as permiten as linguaxes que
te¤en estructuras din micas.

O sitio por onde se inserta e se extrae ch mase cabeza ou cumio da pila.
Nalgunhas implementaci¢ns consid‚rase unha operaci¢n de lectura non
destructiva, ousexa mirar_cumio, que toma unha copia do elemento que est  no
cumio da pila sen que este saia da mesma. Pero normalmente a lectura
dun elemento da pila implica que este elemento sae da mesma.

Nas implementaci¢ns din micas escoller se meter e sacar polo principio
ou facer ambalas d£as cosas polo final. O normal ‚ facelo polo principio xa
que isto evita percorrer constantemente a pila ou manter un punteiro ¢
final da mesma.

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio:  Convertir unha pila de caracteres nun n£mero real.
~~~~~~~~~~

       pila de caracteres
          1
          2
          3     => n§real 123.5
          .
          5                  sen usar ningunha estructura auxiliar.


program
       pasa_pila_a_real ;

type
    tpila = ^ tnodopila ;

    tnodopila = record
                      car : char ;
                      sig : tpila ;
               end ;
{--------------------------------------------------------------------------}
procedure inipila ( var pila : tpila ) ;
begin
     pila := nil ;
end ;
{--------------------------------------------------------------------------}
function pilabaleira ( pila : tpila ) : boolean ;
begin
     pilabaleira := pila = nil ;
end ;
{--------------------------------------------------------------------------}
procedure metepila ( var pila : tpila ; c : char ) ;
var
   aux : tpila ;
begin
     if pilabaleira ( pila )
     then begin
          new ( pila ) ;
          pila ^ . car := c ;
          pila ^ . sig :=  nil ;
     end
     else begin
          new ( aux ) ;
          aux ^ . car := c ;
          aux ^ . sig := pila ;
          pila := aux ;
     end ;
end ;
{--------------------------------------------------------------------------}
procedure sacapila ( var pila : tpila ; var c : char ) ;
var
   aux : tpila ;
begin
     if not pilabaleira ( pila ) then begin
        c := pila ^ . car ;
        aux := pila ;
        pila := pila ^ . sig ;
        dispose ( aux ) ;
     end ;
end ;
{--------------------------------------------------------------------------}
procedure le_pila ( var pila : tpila ) ;
var
   str : string ;
   i : integer ;
begin
     writeln ( 'Escriba t¢dolos elementos da pila por orde dende o' ) ;
     writeln ( 'cumio ata o fondo, seguidos e sen espacios, e pulse Enter' ) ;
     readln ( str ) ;
     for i := length ( str ) downto 1 do
         metepila ( pila , str [ i ] ) ;
end ;
{--------------------------------------------------------------------------}
function convirte ( var pila : tpila ) : real ;
var
   c : char ;
   r : real ;
   parte_enteira : boolean ;
   divisor : real ;
begin
     r := 0 ;
     parte_enteira := true ;
     divisor := 10 ;
     while not pilabaleira ( pila ) do begin
           sacapila ( pila , c ) ;
           parte_enteira := parte_enteira and (c<>'.') ;
           if parte_enteira
           then r := r * 10 + (ord (c) - ord ('0'))
           else
               if c <> '.' then begin
                     r := r + ((ord (c) - ord ('0')) / divisor) ;
                     divisor := divisor * 10 ;
               end ;
     end ;
     convirte := r ;
end ;
{--------------------------------------------------------------------------}

var
   pila : tpila ;
begin
     le_pila ( pila ) ;
     writeln ( convirte ( pila ) ) ;
{
        exemplo da execuci¢n:
Escriba t¢dolos elementos da pila por orde dende o
cumio ata o fondo, seguidos e sen espacios, e pulse Enter
123.92837
 1.2392837000E+02
}
end.

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio: crear un conversor de expresi¢ns en notaci¢n infixa a notaci¢n
~~~~~~~~~~ prefixa e postfixa.

           -de prefixa a infixa, empezar polo final
           -de postfixa a infixa, empezar polo principio

           Ir ¢ final do c¢digo.

program
       convirte_de_infixa ;
const
     operadores = [ '*' , '+' , '-' , '/' ] ;
type
    tlista = ^ tnodolista ;

    tnodolista = record
                      car : char ;
                      sig : tlista ;
               end ;

    tpila = ^ tnodopila ;

    tnodopila = record
                      str : string ;
                      sig : tpila ;
                end ;

{--------------------------------------------------------------------------}
procedure metepila ( var pila : tpila ; str : string ) ;
var
   aux : tpila ;
begin
     if pila = nil
     then begin
          new ( pila ) ;
          pila ^ . str := str ;
          pila ^ . sig :=  nil ;
     end
     else begin
          new ( aux ) ;
          aux ^ . str := str ;
          aux ^ . sig := pila ;
          pila := aux ;
     end ;
end ;
{--------------------------------------------------------------------------}
procedure sacapila ( var pila : tpila ; var str : string ) ;
var
   aux : tpila ;
begin
     if pila <> nil then begin
        str := pila ^ . str ;
        aux := pila ;
        pila := pila ^ . sig ;
        dispose ( aux ) ;
     end ;
end ;
{--------------------------------------------------------------------------}
procedure metelista ( var lista : tlista ; c : char ) ;
var
   aux : tlista ;
begin
     if lista = nil then begin
        new ( lista ) ;
        lista ^ . car := c ;
        lista ^ . sig := nil ;
     end
     else begin
          new ( aux ) ;
          aux ^ . car := c ;
          aux ^ . sig := lista ;
          lista := aux ;
     end ;
end ;
{--------------------------------------------------------------------------}
procedure le_expr ( var lista : tlista ) ;
var
   str : string ;
   i : integer ;
begin
     writeln ( 'Escriba a expresi¢n en infixa, e pulse Enter' ) ;
     readln ( str ) ;
     for i := length ( str ) downto 1 do
         metelista ( lista , str [ i ] ) ;
end ;
{--------------------------------------------------------------------------}
procedure le_expr_¢_reves ( var lista : tlista ) ;
var
   str : string ;
   i : integer ;
begin
     writeln ( 'Escriba a expresi¢n, e pulse Enter' ) ;
     readln ( str ) ;
     for i := 1 to length ( str ) do
         metelista ( lista , str [ i ] ) ;
end ;
{--------------------------------------------------------------------------}
procedure in_a_pre ( in_ : tlista ; var pre : tpila ) ;
var
   str1 , str2 , str3 : string ;
begin
     while in_ <> nil do begin
           if ( in_ ^ . car <> '(' ) and ( in_ ^ . car <> ')' )
           then metepila ( pre , in_ ^ . car ) ;
           if in_ ^ . car = ')' then begin
              sacapila ( pre , str1 ) ;
              sacapila ( pre , str2 ) ;
              sacapila ( pre , str3 ) ;
              metepila ( pre , str2 + str3 + str1 ) ;
           end ;
           in_ := in_ ^ . sig ;
     end ;
     while pre ^ . sig <> nil do begin
              sacapila ( pre , str1 ) ;
              sacapila ( pre , str2 ) ;
              sacapila ( pre , str3 ) ;
              metepila ( pre , str2 + str3 + str1 ) ;
     end ;
end ;
{--------------------------------------------------------------------------}
procedure in_a_pos ( in_ : tlista ; var pos : tpila ) ;
var
   str1 , str2 , str3 : string ;
begin
     while in_ <> nil do begin
           if ( in_ ^ . car <> '(' ) and ( in_ ^ . car <> ')' )
           then metepila ( pos , in_ ^ . car ) ;
           if in_ ^ . car = ')' then begin
              sacapila ( pos , str1 ) ;
              sacapila ( pos , str2 ) ;
              sacapila ( pos , str3 ) ;
              metepila ( pos , str3 + str1 + str2 ) ;
           end ;
           in_ := in_ ^ . sig ;
     end ;
     while pos ^ . sig <> nil do begin
              sacapila ( pos , str1 ) ;
              sacapila ( pos , str2 ) ;
              sacapila ( pos , str3 ) ;
              metepila ( pos , str3 + str1 + str2 ) ;
     end ;
end ;
{--------------------------------------------------------------------------}

var
   lista : tlista ;
   pila : tpila ;
begin
     lista := nil ;
     le_expr ( lista ) ;
     in_a_pre ( lista , pila ) ;
     writeln ( 'En prefixa ‚: ' , pila ^ . str ) ;
     pila := nil ;
     in_a_pos ( lista , pila ) ;
     writeln ( 'En posfixa ‚: ' , pila ^ . str ) ;
end.

{ exemplo de execuci¢n deste programa:

Escriba a expresi¢n en infixa, e pulse Enter
((a+b)*c)-(((f+h)+((l-g)*a))/(f-l))
En prefixa ‚: -*+abc/++fh*-lga-fl
En posfixa ‚: ab+c*fh+lg-a*+fl-/-

}

{===========================================================================}
POSFIXA A INFIXA
~~~~~~~~~~~~~~~~
                    A  B  C  *  D  E  F  ^  /  G  *  -  H  *  +

                    emp‚zase polo principio, A

>----------------------------------<
WHILE NOT COLABALEIRA DO
     
     [saca da cola]

     IF OPERANDO THEN METEPILA

     ELSE
          SACAPILA -> Y
          SACAPILA -> X
          METEPILA ( X OPERADOR Y )
>----------------------------------<
                    
exemplo:

A  B  C  *  D  E  F  ^  /  G  *  -  H  *  +
===========================================  ‚ o estado inicial da cola

a evoluci¢n da pila ‚:

                   F
               E   E  E^F             G
    C      D   D   D   D   D/(E^F) D/(E^F) (D/(E^F))*G   
  B B B*C B*C B*C B*C B*C    B*C     B*C       B*C     B*C - (D/(E^F))*G
A A A  A   A   A   A   A      A       A         A              A
- - - --- --- --- --- ---  ------- ------- ----------- -----------------

       H
B*C - (D/(E^F))*G  ( B*C - (D/(E^F))*G )* H
       A                      A              A + ( ( B*C - (D/(E^F))*G )* H )
-----------------  ------------------------  --------------------------------
                                             a expresi¢n final hai que 
                                             sacala da pila tralo bucle

{===========================================================================}
PREFIXA A INFIXA
~~~~~~~~~~~~~~~~
                    A  B  C  *  D  E  F  ^  /  G  *  -  H  *  +

                    emp‚zase polo final, +

>----------------------------------<
WHILE NOT COLABALEIRA DO
     
     [saca da cola]

     IF OPERANDO THEN METEPILA

     ELSE
          SACAPILA -> X
          SACAPILA -> Y
          METEPILA ( X OPERADOR Y )
>----------------------------------<

{===========================================================================}
INFIXA A POSFIXA
~~~~~~~~~~~~~~~~
                    (1.2+(4/2))*(2.3-(21.1*6.3))

                    emp‚zase polo principio, 1.2

>----------------------------------<
WHILE NOT COLABALEIRA DO
     
     [saca da cola]

     IF )
         SACAPILA -> Y
         SACAPILA -> OPERADOR
         SACAPILA -> X
         SACAPILA (
         METEPILA X,Y,OPERADOR

     ELSE METEPILA
>----------------------------------<
                    
exemplo:

(1.2+(4/2))*(2.3-(21.1*6.3))
============================ ‚ o estado inicial da cola

a evoluci¢n da pila ‚:

                       2
                   /   /
               4   4   4    
           (   (   (   (    4,2,/   
       +   +   +   +   +      +                                   (
  1.2 1.2 1.2 1.2 1.2 1.2    1.2                     *            *
(  (   (   (   (   (   (      (     1.2,4,2,/,+  1.2,4,2,/,+  1.2,4,2,/,+
- --- --- --- --- --- --- ) ----- ) -----------  -----------  -----------

                                                                    6.3
                                                        *            *
                                         21.1         21.1          21.1
                              (            (            (            (
                 -            -            -            -            -
   2.3          2.3          2.3          2.3          2.3          2.3
    (            (            (            (            (            (
    *            *            *            *            *            *
1.2,4,2,/,+  1.2,4,2,/,+  1.2,4,2,/,+  1.2,4,2,/,+  1.2,4,2,/,+  1.2,4,2,/,+
-----------  -----------  -----------  -----------  -----------  ----------- )


21.1,6.3,*
    -
   2.3         
    (         2.3,21.1,6.3,*,-
    *               *
1.2,4,2,/,+     1.2,4,2,/,+
----------- ) ----------------  ou ben se obriga a que toda a expresi¢n
                                estea rodeada por derradeiros par‚nteses, ou 
                                ben hai que repetir unha vez a operaci¢n de 
                                sacar da pila, tralo bucle. O resultado ‚:
                                       1.2,4,2,/,+,2.3,21.1,6.3,*,-,*

{===========================================================================}
INFIXA A PREFIXA
~~~~~~~~~~~~~~~~
                    (1.2+(4/2))*(2.3-(21.1*6.3))

                    emp‚zase polo principio, 1.2

>----------------------------------<
WHILE NOT COLABALEIRA DO
     
     [saca da cola]

     IF )
         SACAPILA -> Y
         SACAPILA -> OPERADOR
         SACAPILA -> X
         SACAPILA (
         METEPILA OPERADOR,X,Y

     ELSE METEPILA
>----------------------------------<



                              ÛßßßßßßßßßßßßßßßÛ
                              Û RECURSIVIDADE Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

A recursividade apl¡case cando para solucionar un problema, este se pode
dividir noutros m is pequenos e todos se resolven do mesmo xeito.

Hai recursividade cando un subprograma se chama a s¡ mesmo directa ou 
indirectamente:
-recursividade directa: no c¢digo que conforma dito subprograma existe
                        unha chamada a s¡ mesmo.
-recursividade indirecta: existe unha secuencia de chamadas entre 
                          subprogramas a cal ¢ final se convirte nun 
                          lazo pechado.

¨Cando hai que aplicar a recursividade?
-cando as estructuras de datos usadas se definen de maneira recursiva.
-cando un problema se autodefine de maneira recursiva.
-cando un problema se divide en subprogramas m is pequenos que precisan o
mesmo tratamento.

TODO problema resolto de forma recursiva se pode resolver por un m‚todo
iterativo.

As implementaci¢ns recursivas soen ser m is claras pero menos eficientes
c s iterativas.

A recursividade so ‚ posible en linguaxes que permitan asignaci¢n din mica 
de memoria, pois nun programa recursivo non se sabe de antem n cantas
chamadas se van facer ¢ algoritmo (p.ex., no c lculo do factorial
non se sabe cantas variables se van utilizar):
     A's variables locais res‚rvaselles espacio de memoria en tempo
     de execuci¢n.

Hai que ter tino de que o programa recursivo non se chame a s¡ mesmo
indefinidamente e t‚n que haber un cami¤o ou condici¢n co cal non se
volve chamar ¢ caso base. E' dicir:

As normas son

1¦) Inclusi¢n do caso base: no c¢digo debe aparecer o caso "parvo"
do problema, o que t‚n resoluci¢n inmediata. No exemplo do factorial,
if n = 0 then fact := 1.
2¦) Reducci¢n do problema: debemos comprobar que en cada paso o problema
se achega   soluci¢n, que queda menos traballo por facer. No exemplo do 
factorial, fact := n * factorial (n-1).
3¦) Rexeitamento de par metros non v lidos: antes de aplicar a recursividade 
d‚bese confirmar que os par metros son axeitados. No exemplo do factorial,
if n >= 0 then begin ... 

O que estamos consumindo na aplicaci¢n da recursividade ‚ espacio
da pila de memoria (STACK). A¡nda que o "nome" da variable ‚ o mesmo,
estamos gardando valores distintos, variables diferentes (distintas 
direcci¢ns de memoria) referidas a distintos niveis de chamada.

O' usar un m‚todo iterativo e non o recursivo, empr‚gase o HEAP en troques do 
stack.

RECURSION DE COLA ‚ aquela que se produce cando un subprograma se chama
a s¡ mesmo na derradeira li¤a do c¢digo.

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio: Dado un n£mero enteiro, crear un procedemento recursivo que
~~~~~~~~~~ escriba os d¡xitos dese n£mero en orde.

{---------------------------------------------------------------------------}

program numero ; uses crt ;

procedure escribe ( n : longint ) ;
begin
     if n div 10 = 0
     then write ( n )
     else begin
          escribe ( n div 10 ) ; write ( '  ' , n mod 10 ) ;
     end ;
end ;

begin clrscr ;
     escribe ( 110293 ) ;
end.

{ na pantalla aparece: 1  1  0  2  9  3 }

{---------------------------------------------------------------------------}

Vemos que esta soluci¢n ‚ pouco eficiente porque se van deixando operaci¢ns
pendientes. A soluci¢n iterativa ser¡a m is r pida. A conversi¢n dun
programa recursivo a iterativo faise siempre mediante bucles (e.g. while)
e o uso de pilas.

So se pode pasar de recursividade a iteraci¢n sen usar pilas cando a
chamada recursiva vai ¢ final do c¢digo do subprograma recursivo.

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Outro exemplo do pouco eficiente que pode chegar a ser un programa
recursivo: os n£meros de Fibonacci.

function fibo ( n : integer ) : integer ;
begin
     if n > 0
     then
       if (n = 1) or (n = 0)
       then fibo := n
       else fibo := fibo ( n-1 ) + fibo ( n-2 )
     else fibo := 0 ;
end ;

exemplo:                                   fibo(5)
                            fibo(4)           +            fibo(3)
                    fibo(3)    +   fibo(2)         fibo(2)  +    fibo(1)
               fibo(2)+fibo(1)  fibo(1)+fibo(0)  fibo(1)+fibo(0)
           fibo(1)+fibo(0)

Xa para un n£mero pequeno como 5 se acumulan moitos c lculos repetidos.

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio: Construir un reco¤ecedor de pal¡ndromos.
~~~~~~~~~~

function palindromo ( s : string ) : boolean ;
begin
     if length ( s ) < 2
     then palindromo := true
     else palindromo := ( s [ 1 ] = s [ length (s) ] )
                        and
                        ( palindromo ( copy ( s , 2 , length (s) -2 ) ) ) ;
end ;

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio: procedemento copiador de lista simplemente enlazada.
~~~~~~~~~~
procedure copia ( lista1 : tlista ; var lista2 : tlista ) ;
begin
     if lista1 = nil
     then lista2 := nil
     else begin
         new ( lista2 ) ;
         lista2 ^ . info := lista1 ^ . info ;
         copia ( lista1 ^ . sig , lista2 ^ . sig ) ;
     end ;
end ;

Supo¤endo o mesmo procedemento pero:

procedure copia ( lista1 , lista2 : tlista ) ;

(sen var) e referido a listas con nodo cabeceira ¨funcionar¡a?
A resposta ‚ que s¡.

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio: Funci¢n copiadora de lista simplemente enlazada.
~~~~~~~~~~
function copia ( lista : tlista ) : tlista ;
var
   c : tlista ;
begin
     if lista = nil
     then c := nil
     else begin
         new ( c ) ;
         c ^ . info := lista ^ . info ;
         c ^ . sig := copia ( lista ^ . sig ) ;
     end ;
     copia := c ;
end ;

A L G O R I T M O S   D E   B A C K T R A C K I N G (VOLTA ATRAS):

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicio: as oito ra¡¤as: atopar como deben disporse nun taboleiro para 
~~~~~~~~~~ que non se maten mutuamente.


X _ _ _ _ _ _ _
_ _ X _ _ _ _ _
_ _ _ _ X _ _ _
_ _ _ _ _ _ X _
_ X _ _ _ _ _ _
_ _ _ X _ _ _ _
_ _ _ _ _ X _ _
_ _ _ _ _ _ _ X

{est  en seudoc¢digo}

procedure coloca ( i : integer { fila } ; var q : boolean ) ;
{ para cada ra¡¤a busca unha posici¢n correcta en cada fila }
var
   j : integer ;
begin
     j := 0 ; { columna }
     q := false ;
     repeat
           j := j + 1 ;
           if e_valido ( i , j ) then
                coloca ( i , j ) ;
                if i < 8 then
                     coloca ( i+1 , q ) ;
                     if not q then quitar ( i , j )
                else q := true ;
     until (j = 8) or q ;
end ;

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
Exercicios propostos:
~~~~~~~~~~~~~~~~~~~~~
1) salto do cabalo: se a casi¤a inicial dun cabalo de xadrez ‚
aleatoria ¨pode visitar t¢dalas casi¤as do taboleiro unha e so unha vez?
2) laberinto construido cunha matriz 20x20 de booleans, 0 paso ceibe,
1 paso cortado, situaci¢n inicial aleatoria ¨p¢dese sair?
3) funci¢n comparadora de d£as listas simplemente enlazadas.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

ORDEACION POR MISTURA
ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ
Div¡dese o array en d£as partes. Ord‚nanse por separado ambalas d£as partes 
e mist£ranse. A subdivisi¢n do array rep¡tese ata que cada subarray t‚n
un so elemento, i.e. est  ordeado.

{est  en seudoc¢digo}

procedure ord_mistura ( var datos : arreglo ; primeiro , derradeiro : integer ) ;
var
   metade : integer ;
begin
     if primeiro < derradeiro then 
     begin
          metade := ( primeiro + derradeiro ) div 2 ;
          ord_mistura ( datos , primeiro , metade ) ;
          ord_mistura ( datos , metade +1 , derradeiro ) ;
          mistura ( datos , primeiro , metade , metade +1 , derradeiro ) ;
          { percorre as d£as partes tomando o menor de cada par e 
          despois emborcando o contido }
     end ;
end ;

Este algoritmo sup¢n unha mellora en canto   velocidade: t‚n complexidade
n log 2 (n) onde n < n log 2 (n) < ný
O £nico inconvinte que t‚n ‚ que usa un array auxiliar para almacenar datos.

ORDEACION RAPIDA
ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ
procedure division ( var datos : arreglo ; primeiro , derradeiro : integer ;
var puntodivision : integer ) ;
{
Separa os elementos do arreglo datos entre os ¡ndices primeiro e derradeiro
segundo sexan os elementos menores ou maiores que puntodivisi¢n.
T¢manse dous ¡ndices, un ¢ principio e outro ¢ final.
}
var
   dereita , esquerda , v : integer ;
begin
     v := datos [ primeiro ] ;
     dereita := primeiro + 1 ;
     esquerda := derradeiro ;

     repeat
           { mover dereita ata elemento > v }
           while ( dereita < esquerda ) and ( datos [ dereita ] <= v )
           do dereita := dereita + 1 ;
           { comprobar condici¢n de fin }
           if ( dereita = esquerda ) and ( datos [ dereita ] <= v )
           then dereita := dereita + 1 ;
           { mover esquerda ata elemento <= v }
           while ( dereita <= esquerda ) and ( datos [ esquerda ] > v )
           do esquerda := esquerda - 1 ;
           if dereita < esquerda then begin
              trocar ( datos [ esquerda ] , datos [ dereita ] ) ;
              dereita := dereita + 1 ;
              esquerda := esquerda - 1 ;
           end ;
     until dereita > esquerda ;

     trocar ( datos [ primeiro ] , datos [ esquerda ] ) ;
     puntodivisi¢n := esquerda ;
end ;

No mellor dos casos prod£cense n-1 comparaci¢ns, daquela no mellor
dos casos a complexidade do algoritmo de divisi¢n ‚ n.

procedure ord_rapida ( x , i , j ) ;
var
   p : integer ;
begin
     if i < j then begin
        division ( x , i , j  , p ) ;
        ord_rapida ( x , i , p-1 ) ;
        ord_rapida ( x , p+1 , j ) ;
     end ;
end ;

chamadas arrays
   0       1
   1       2
   2       4
   3       8
      ...
A complexidade de ord_rapida ‚ lg 2 (n)

Ent¢n a complexidade do algoritmo de ordenaci¢n r pida ‚ de nùlg 2 (n)
no mellor dos casos (i.e. os subarrays te¤en o mesmo tama¤o)

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

function busca_nodo ( d : tdato ; l : tlista ) : tnodo ;
var
   atopado : boolean ;
begin
     atopado := false ;
     while l <> nil and not atopado do
           if ( l ^ . info . info1 = d . info . info1 )
           and ( l ^ . info . info2 = d . info . info2 )
           then atopado := true
           else l := l ^ . sig ;
           busca_nodo := l ;
end ;

procedure ins_nodo ( d : tdato ; var l : tlista ) ;
var
   ptr : tlista ;
   atopado : boolean ;
begin
     if listabaleira ( l ) then begin
        crearnodo ( d , ptr ) ;
        l := ptr ;
     end
     else begin
          ptr := busca_nodo ( d , l ) ;
          if ptr <> nil
          then ptr ^. rep := ptr ^ . rep + 1 ;
          else begin
               atopado := false ;
               if ( l ^ . info . info1 > d . info . info1 )
               and ( l ^ . info . info2 > d . info . info2 )
               then
               ...
          end ;
     end ;
end ;

                              

                              ÛßßßßßßßßßÛ
                              Û ARBORES Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

Def.- Unha  rbore tipo T ‚ unha estructura homox‚nea que ‚ a concatenaci¢n
dun elemento de tipo T cun n£mero finito de  rbores disxuntas chamadas
sub rbores. Unha forma particular de  rbore pode ser a estructura baleira.
Disxunto significa que so hai unha forma posible de chegar a cada punto da
 rbore.

Unha  rbore ‚ unha lista non lineal.
-Lista porque cont‚n elementos homox‚neos.
-Non lineal porque dado un elemento, este pode ter cero, un ou m is dun 
sucesor (elemento "seguinte"). O antecesor ‚ £nico.

Podemos definir unha  rbore como un TDA formado por un elemento diferenciado
chamado raiz e por varias  rbores que suceden ¢ elemento raiz (definici¢n
recursiva de  rbore)

representaci¢ns:

a) diagrama de Venn

 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
 ³ A                                             ³
 ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³
 ³ ³ B          ÚÄÄÄÄ¿        ³ ³ C   ÚÄÄÄÄÄ¿  ³ ³
 ³ ³ ÚÄÄÄÄÄÄÄÄ¿ ³ E  ³        ³ ³     ³  G  ³  ³ ³
 ³ ³ ³ D ÚÄÄÄ¿³ ÀÄÄÄÄÙ        ³ ³     ÀÄÄÄÄÄÙ  ³ ³
 ³ ³ ³   ³ I ³³ ÚÄÄÄÄÄÄÄÄÄÄÄ¿ ³ ³              ³ ³
 ³ ³ ³   ÀÄÄÄÙ³ ³ F         ³ ³ ³ ÚÄÄÄÄÄÄÄÄÄÄ¿ ³ ³
 ³ ³ ÀÄÄÄÄÄÄÄÄÙ ³ ÚÄÄÄ¿ÚÄÄÄ¿³ ³ ³ ³ H  ÚÄÄÄ¿ ³ ³ ³
 ³ ³            ³ ³ J ³³ K ³³ ³ ³ ³    ³ L ³ ³ ³ ³
 ³ ³            ³ ÀÄÄÄÙÀÄÄÄÙ³ ³ ³ ³    ÀÄÄÄÙ ³ ³ ³
 ³ ³            ÀÄÄÄÄÄÄÄÄÄÄÄÙ ³ ³ ÀÄÄÄÄÄÄÄÄÄÄÙ ³ ³
 ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³
 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ

b) grafo

       A
     /   \
   B       C
 / / \    / \
D E   F   G H
|    / \    |
I    J K    L


Caracter¡sticas (segundo Cair¢)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-toda  rbore non baleira t‚n un £nico NODO RAIZ.
-un nodo X ‚ DESCENDENTE DIRECTO ou FILLO dun nodo Y se o nodo X ‚
apuntado polo nodo Y.
-un nodo X ‚ ANTECESOR DIRECTO ou PAI dun nodo Y se o nodo X apunta ¢
nodo Y.
-dise que t¢dolos nodos que son descendentes directos dun mesmo nodo
(fillos dun mesmo pai) son IRMANS.
-todo nodo que non t‚n ramificaci¢ns ch mase NODO TERMINAL ou FOLLA.
-todo nodo non raiz nin terminal dise INTERIOR.
-GRAO DUN NODO ‚ o n£mero de descendentes directos do mesmo.
-GRAO DUNHA ARBORE ‚ o n£mero m ximo de descendentes directos dun nodo 
calquera da  rbore.
-NIVEL ‚ o n£mero de arcos que deben ser percorridos para chegar a un 
determinado nodo. Por definici¢n a raiz t‚n nivel 1.
-ALTURA da  rbore ‚ o m ximo n£mero de niveis de t¢dolos nodos da  rbore.
(o nivel m ximo de t¢dolos nodos da  rbore)
-BOSQUE ‚ un conxunto de ¢ menos unha  rbore disxunta.


Def¡nese lonxitude de cami¤o como o n£mero de arcos que deben ser percorridos 
para chegar dende a raiz a determinado nodo.

LONXITUDE DE CAMI¥O INTERNO 
~~~~~~~~~~~~~~~~~~~~~~~~~~~
L.C.I.: E' a suma das lonxitudes de cami¤o de t¢dolos nodos da  rbore.
Pode calcularse por medio da seguinte f¢rmula:

          h                          h : altura da  rbore
         ÄÄÄ                         n : n£mero de nodos no nivel i
L.C.I. =  >  n * i                    i
         ÄÄÄ  i                      i : nivel da  rbore 
         i=1                             (altura do nivel)

exemplo:                 ni (n£mero de nodos no nivel i)
                           * i (altura do nivel)
       A    -----------> 1 * 1 = 1
     /   \
   B       C ----------> 2 * 2 = 4
 / ³ \    
D  E  F  --------------> 3 * 3 = 9 
     / \    
     J K  -------------> 2 * 4 = 8  
                               -----
                              LCI=22

Agora ben, a Media de Lonxitude de Cami¤o Interno L.C.I.M. calc£lase 
dividindo a L.C.I. entre o n£mero de nodos existentes na  rbore:

            L.C.I.M.
L.C.I.M. = ÄÄÄÄÄÄÄÄÄ
               n

no exemplo LCIM ser¡a 22/8

LONXITUDE DE CAMI¥O EXTERNO 
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Arbore extendida ‚ aquela na que o n£mero de fillos de cada nodo ‚ igual
¢ grao da  rbore. Se alg£n dos nodos da  rbore non compre esta condici¢n 
debe incorpor rselle ¢ mesmo nodos especiais, tantos como sexan necesarios.

                 A
               / ³ \
             /   ³   \
           /     ³     \
         B       _      C
     /   ³   \        / ³ \
   /     ³     \     ³  ³  ³
  D      E       F   _  _  _
/ ³ \  / ³ \   / ³ \
_ _ _  _ _ _   _ _  L
                  / ³ \
                  _ _ _

L.C.E.: E' a suma das lonxitudes de cami¤o de t¢dolos nodos ESPECIAIS
da  rbore. Calc£lase por medio da seguinte f¢rmula:

         h+1
         ÄÄÄ
L.C.E. =  >  ne * i                    
         ÄÄÄ   i                      
         i=2                         

exemplo:
                 A  ------------------> nivel 1 , 0 nodos especiais = 1 * 0
               / ³ \
             /   ³   \
           /     ³     \
         B       _      C  -----------> nivel 2 , 1 nodo especial   = 2 * 1
     /   ³   \        / ³ \
   /     ³     \     ³  ³  ³
  D      E       F   _  _  _  --------> nivel 3 , 3 nodos especiais = 3 * 3
/ ³ \  / ³ \   / ³ \
_ _ _  _ _ _   _ _  L   --------------> nivel 4 , 8 nodos especiais = 4 * 8
                  / ³ \
                  _ _ _  -------------> nivel 5 , 3 nodos especiais = 5 * 3
                                                                      ÄÄÄÄÄÄÄ
                                                                      LCE=58
A Media de Lonxitude de Cami¤o Externo L.C.E.M. calc£lase as¡:

            L.C.E.M.
L.C.E.M. = ÄÄÄÄÄÄÄÄÄ
               ne

no exemplo ser¡a 58/15


ARBORES BINARIAS
~~~~~~~~~~~~~~~~
Unha  rbore ordenada ‚ aquela na que as ramas dos nodos da  rbore est n
ordenadas.
Unha  rbore binaria ‚ unha  rbore ordenada de grao 2.

Def.- Unha  rbore binaria de tipo T ‚ unha estructura homox‚nea que se 
comp¢n mediante a concatenaci¢n dun elemento de tipo T chamado raiz, con 
d£as  rbores binarias disxuntas chamadas sub rbore esquerda e 
sub rbore dereita da raiz.

As  rbores binarias non son directamente comparables cas  rbores 
ordinarias.

ARBORES BINARIAS DISTINTAS son aquelas con estructuras diferentes
~~~~~~~~~~~~~~~~~~~~~~~~~~ (independientemente da informaci¢n que se 
                           garda nos nodos).

ARBORES BINARIAS SEMELLANTES son aquelas con estructuras id‚nticas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~ pero a informaci¢n que conte¤en ‚ distinta.

ARBORES BINARIAS EQUIVALENTES son aquelas que te¤en igual estructura e
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ contido.

exemplo:

dada a  rbore:
     
      A
    /   \
   B     C
       /   \
      D     E

‚ EQUIVALENTE:

      A
    /   \
   B     C
       /   \
      D     E

‚ SEMELLANTE: 

      A
    /   \
   B     C
       /   \
      E     D

‚ DISTINTA:

      A
    /   \
   B     C
 /   \
D     E

Arbores binarias completas: t¢dolos seus nodos, ag s os do derradeiro nivel, 
te¤en dous fillos.
                                                     h
N£mero m ximo de nodos dunha  rbore con altura h ‚= 2 -1

N£mero m ximo de nodos no nivel i dunha  rbore ‚= 2ùi -1

Lema: se n0 ‚ o n£mero de nodos terminais e n2 o n£mero de nodos de grao
2, daquela n0 = n2 + 1. Demostralo.

-se a  rbore ‚ baleira n0 = 0 e n2 = 0 daquela non se compre

-se a  rbore non ‚ binaria non se compre

      o
     / \                   n0 = 4
    o   o
   /³\                     n2 = 1
  o o o

Ent¢n as hip¢teses son que a  rbore ‚ non baleira e binaria.

--demostraci¢n:          sexa n1 o n£mero de nodos de grao 1
                         sexa B o n£mero de conexi¢ns existentes na  rbore

n£mero de nodos da  rbore n = n0 + n1 + n2 (a)

obviamente n = B + 1 (para unir n nodos son necesarias n-1 aristas)

como por cada nodo de grao 1 hai unha conexi¢n e por cada nodo de grao 2 hai 
d£as conexi¢ns daquela: B = n1 + 2 * n2  

destas d£as expresi¢ns ded£cese que: n - 1 = n1 + 2 * n2 //
// n = n1 + 2 * n2 + 1 (b)

de (a) - (b) ded£cese:

n = n0 + n1 + n2 (a)
n = n1 + 2 * n2 + 1 (b)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
0 = n0 + n2 - 2 * n2 -1 // 0 = n0 - n2 -1 // n0 = n2 + 1    c.q.d. 
                                             ~~~~~~~~~~~
para toda  rbore binaria non baleira

XERALES COMO BINARIAS
~~~~~~~~~~~~~~~~~~~~~ 
               conversi¢n de  rbore multicami¤o (grao>2) en binaria (grao=2)

pasos a seguir:

a) d‚bese enlazar os fillos de cada nodo en forma horizontal.
b) d‚bese enlazar en forma vertical o nodo pai co fillo que se
atopa m is   esquerda. Adem is, debe eliminarse o v¡nculo dese
pai co resto dos seus fillos.
c) d‚bese virar toda a estructura.

exemplo:
--a  rbore orixinal ‚:

                 A
               /   \
             /       \
           /           \
         B               C
     /   ³   \         /   \
   /     ³     \      ³     ³
  D      E       F    G     H    
  ³            /   \        |
  I           J     K       L
                  
--tralos pasos 1 e 2 queda:

                 A
               /   
             /       
           /           
         B ------------> C
     /                 /    
   /                  ³      
  D ---> E ----> F    G --> H    
  ³            /            |
  I           J --> K       L

--tralo paso 3 queda:

               A
             /    
           /
         B                
      /     \      
    /         \    
   D            C  
 /   \         /
I      E     G
         \      \
           F      H
         /      /
       J       L
         \
           K

REPRESENTACION DE ARBORES BINARIAS EN MEMORIA
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Existen d£as formas tradicionais de representar unha  rbore binaria en 
memoria:
--mediante arreglos
--por medio de datos de tipo punteiro

Neste derradeiro caso empr‚ganse os seguintes recursos:

type
     tipoinfo = ...
     tipoarbore = ^ tiponodo ;
     tiponodo = record
                      info : tipoinfo ;
                      fillo_esq , fillo_der : tipoarbore ;
                end ;
var
   raiz : tipoarbore ;

PERCORRIDOS EN ARBORES BINARIAS
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consiste en visitar os nodos da  rbore dun xeito sistem tico de modo que os
nodos sexan visitados todos e cada un unha soa vez.

1.-Percorrido en INORDE:
     -percorrer a sub rbore esquerda
     -visitar a raiz
     -percorrer a sub rbore dereita

2.-Percorrido en PREORDE:
     -visitar a raiz
     -percorrer a sub rbore esquerda
     -percorrer a sub rbore dereita

3.-Percorrido en POSTORDE:
     -percorrer a sub rbore esquerda
     -percorrer a sub rbore dereita
     -visitar a raiz

exemplo:

        P                          Inorde: B F G H P R S T W Y Z 
      /   \                   
    /       \                      Preorde: P F B H G S R Y T W Z
   F         S
 /   \     /   \                   Postorde: B G H F R W T Z Y S P 
B     H   R     Y                  
     /        /   \                Inorde invertida: Z Y W T S R P H G F B 
    G        T     Z               ( D , raiz , E )
              \                    
               W                   Postorde invertida: Z W T Y R S G H B F P
                                   ( D , E , raiz )

PERCORRIDOS RECURSIVOS
{-----------------------------------}
procedure inorde ( a : tipoarbore ) ;
begin
     if ptr <> nil then begin
          inorde ( a ^ . fillo_esq ) ;
          procesar ( a ^ . info ) ;
          inorde ( a ^ . fillo_der ) ;
     end ;
end ;
{------------------------------------}
procedure preorde ( a : tipoarbore ) ;
begin
     if ptr <> nil then begin
          procesar ( a ^ . info ) ;
          preorde ( a ^ . fillo_esq ) ;
          preorde ( a ^ . fillo_der ) ;
     end ;
end ;
{-------------------------------------}
procedure postorde ( a : tipoarbore ) ;
begin
     if ptr <> nil then begin
          postorde ( a ^ . fillo_esq ) ;
          postorde ( a ^ . fillo_der ) ;
          procesar ( a ^ . info ) ;
     end ;
end ;
{-------------------------------------}

PERCORRIDOS ITERATIVOS
{--------------------------------------------}
procedure inorde ( raizarbore : tipoarbore ) ;
var
   pilaptr : tipopila ;
   ptr : tipopunteiro ;
begin
     limparpila ( pilaptr ) ;
     ptr := raizarbore ;
     repeat
          { procesar ata que se acabe a  rbore }
          { tam‚n poder¡a ser while (ptr<>nil) }
          { and not pilabaleira(pila) then ... }
          { ir   esquerda todo canto se poida }
          while ptr <> nil do begin
               meterpila ( pilaptr , ptr ) ;
               ptr := ptr ^ . fillo_esq ;
          end ; { while }
          { se existe algo na pila, sacar, procesar e mover   dereita }
          if not pilabaleira ( pila ) then begin
               sacar ( pilaptr , ptr ) ;
               procesarnodo ( ptr ) ;
               ptr := ptr ^ . fillo_der ;
          end ; { if }
     until ( ptr = nil ) and pilabaleira ( pilaptr ) ;
end ; { procedure }
{---------------------------------------------}
procedure preorde ( raizarbore : tipoarbore ) ;
var
   pilaptr : tipopila ;
   ptr : tipopunteiro ;
begin
     limparpila ( pilaptr ) ;
     ptr := raizarbore ;
     repeat
          { procesar ata que se acabe a  rbore }
          { tam‚n poder¡a ser while (ptr<>nil) }
          { and not pilabaleira(pila) then ... }
          { ir   esquerda todo canto se poida }
          while ptr <> nil do begin
               procesarnodo ( ptr ) ;
               meterpila ( pilaptr , ptr ) ;
               ptr := ptr ^ . fillo_esq ;
          end ; { while }
          { se existe algo na pila, sacar e mover   dereita }
          if not pilabaleira ( pila ) then begin
               sacar ( pilaptr , ptr ) ;
               ptr := ptr ^ . fillo_der ;
          end ; { if }
     until ( ptr = nil ) and pilabaleira ( pilaptr ) ;
end ; { procedure }
{-------------------------------------------}
Para o procedemento iterativo para a postorde son necesarias d£as pilas.
Proc‚sase o nodo gardado tras acceder ¢ lado dereito. Recup‚rase e non
se procesa sen¢n que se vai   dereita e a segunda vez que se recupera 
proc‚sase. As partes esquerdas son directamente procesables; 
as dereitas, non.

          A                       PILA a            PILA b
        /   \                   
      /       \                    -D                 S
     B         H                    F                 N
   /   \     /   \                 -C                 S
  C     E   I     K                 E                 N
 / \       /        \              -B                 S
D   F     J          Y              H                 N
   /                               -A                 S
  G               

se raiz <> nil 
     repetir
          mentres raiz <> nil
               meterpila ( raiz , true )
               se raiz ^ . fillo_der <> nil
                    meterpila ( raiz ^ . fillo_der , false )
               finse
               raiz := raiz ^ . fillo_esq 
          finmentres
          bPila := false

          mentres non bPila
               se pilabaleira ( raiz )
                    bPila := true
               senon
                    se sacarpila ( raiz )
                         procesar ( raiz )
                    senon
                         bPila := true
                    finse
               finse
          finmentres
     ata pilabaleira ( raiz )

PERCORRIDO POR ANCHURA: Os nodos da  rbore perc¢rrense por nivel.
Empr‚gase unha cola.

          A                       
        /   \                  A , 
      /       \                 
     B         H               B , H , 
   /   \     /   \              
  C     E   I     K            C , E , I , K , 
 / \       /        \           
D   F     J          Y         D , F , J , Y , 
   /                            
  G                            G .

procedure anchura ( raiz : tipoarbore ) ;
begin
     limparcola ( cola ) ;
     if raiz <> nil 
     then insertarcola ( raiz , cola ) ;
     while not colabaleira ( cola ) do begin
          sacarcola ( raiz ) ;
          procesarcola ( raiz ) ;
          if raiz ^ . fillo_esq <> nil 
          then insertarcola ( raiz ^ . fillo_esq , cola ) ;
          if raiz ^ . fillo_der <> nil 
          then insertarcola ( raiz ^ . fillo_der , cola ) ;
     end ; { while }

{---------------------------------------------------------------------------}
Exercicio: crear un procedemento que permita crear unha  rbore en memoria a 
~~~~~~~~~~ partir dunha  rbore baleira. 
A secuencia a seguir ser  a seguinte:
-primeiro preg£ntase a informaci¢n que se gardar  no nodo.
-a continuacion preg£ntase se vai a existir outro nodo con parte esquerda e
se ‚ as¡ introd£cese o seu valor.
-sobre ese novo nodo rep¡tese a consulta. En caso de non ter parte 
esquerda preg£ntase se t‚n parte dereita.

Dese¤alo recursivamente.

Sup¢¤ense dous casos:
-nodo raiz (par metro por valor) xa existe (non cont‚n ningunha informaci¢n).
-nodo raiz non existe (par metro por referencia porque hai que apuntar ¢
nodo raiz que se cree)

{-------------------------------------}
procedure crear ( raiz : tipoarbore ) ;
var
   op : char ;
begin
     writeln ( 'Dato? ' ) ;
     readln ( raiz ^ . info ) ;
     writeln ( 'T‚n fillo esquerdo? ' ) ;
     readln ( op ) ;
     if op = 's' then begin
          new ( raiz ^ . esq ) ;
          crear ( raiz ^ . esq ) ;
     end
     else raiz ^ . esq := nil ;
     { end if-then-else }
     writeln ( 'T‚n fillo dereito? ' ) ;
     readln ( op ) ;
     if op = 's' then begin
          new ( raiz ^ . der ) ;
          crear ( raiz ^ . der ) ;
     end
     else raiz ^ . der := nil ;
     { end if-then-else }      
end ; { procedure }
{-----------------------------------------}
procedure crear ( var raiz : tipoarbore ) ;
var
   op : char ;
begin
     new ( raiz ) ;
     writeln ( 'Dato? ' ) ;
     readln ( raiz ^ . info ) ;
     writeln ( 'T‚n fillo esquerdo? ' ) ;
     readln ( op ) ;
     if op = 's' 
     then crear ( raiz ^ . esq ) ;
     else raiz ^ . esq := nil ;
     writeln ( 'T‚n fillo dereito? ' ) ;
     readln ( op ) ;
     if op = 's' 
     then crear ( raiz ^ . der ) ;
     else raiz ^ . der := nil ;
end ; { procedure }

{---------------------------------------------------------------------------}
Exercicio: crear unha funci¢n que pas ndolle unha  rbore binaria e un certo 
~~~~~~~~~~ dato tipo info indique se ese dato est  almacenado nalg£n nodo da
 rbore. A' funci¢n p saselle a  rbore, o dato e devolve un valor booleano.

function esta_en_arbore ( a : arbore ; d : tipoinfo ) : boolean ;
begin
     if a = nil
     then esta_en_arbore := false
     else esta_en_arbore := ( a ^ . info = d ) 
                        or esta_en_arbore ( a ^ . esq , d ) 
                        or esta_en_arbore ( a ^ . der , d ) ;
end ; { function }

{---------------------------------------------------------------------------}
Exercicio: funci¢n recursiva que permite facer un duplicado dunha  rbore.
~~~~~~~~~~ P saselle a  rbore e devolve o punteiro   raiz da copia.

function copiar ( raiz : tipoarbore ) : tipoarbore ;
var
   novo : tipoarbore ;
begin
     if raiz = nil 
     then copiar := nil 
     else begin
          new ( novo ) ;
          novo ^ . info := raiz ^ . info ;
          novo ^ . esq := copiar ( raiz ^ . esq ) ;
          novo ^ . der := copiar ( raiz ^ . der ) ;
          copiar := novo ;
     end ; { else }
end ; { function }

{---------------------------------------------------------------------------}
Exercicio: funci¢n recursiva que permite facer un duplicado dunha  rbore
~~~~~~~~~~ pero de modo que sexa como a imaxe reflexada nun espello.
           P saselle a  rbore e devolve o punteiro   raiz da  rbore
           "reflexado" (problema da imaxe especular).

function espello ( raiz : tipoarbore ) : tipoarbore ;
var
   novo : tipoarbore ;
begin
     if raiz = nil
     then copiar := nil
     else begin
          new ( novo ) ;
          novo ^ . info := raiz ^ . info ;
          novo ^ . esq := espello ( raiz ^ . dta ) ;
          novo ^ . dta := espello ( raiz ^ . esq ) ;
          espello := novo ;
     end ; { else }
end ; { function }

NOTA: advertir que ‚ practicamente igual ¢ anterior.

{---------------------------------------------------------------------------}
Exercicio: funci¢n recursiva que devolve o n£mero de nodos dunha  rbore.
~~~~~~~~~~ 
function contanodos ( arbore : tarbore ) : integer ;
begin
     if arbore <> nil
     then contanodos := 1 + contanodos ( arbore ^ . esq )
                           + contanodos ( arbore ^ . dta )
     else contanodos := 0 ;
end ;

{---------------------------------------------------------------------------}
Exercicio: funci¢n recursiva que devolve a altura dunha  rbore de grao 3.
~~~~~~~~~~ 
function altura3 ( raiz : tipoarbore ) : integer ;
begin
     if raiz = nil
     then altura := 0
     else
         altura := 1 + maximo ( altura ( raiz ^ . esq ) ,
                                altura ( raiz ^ . ctr ) ,
                                altura ( raiz ^ . dta ) ) ;
end ; { function }

(queda por facer a funci¢n m ximo de tres n£meros)

ARBORES ESPECIAIS
~~~~~~~~~~~~~~~~~
Arbores de expresi¢ns aritm‚ticas: nodos con fillos de 0 ou 2 fillos.
Os nodos con (2) fillos corresponden a operadores e os nodos sen fillos
a operandos.

exemplo:
    *
   / \
  -   C
 / \
A   B        A representaci¢n ‚ directa e en infixa non require par‚nteses.

-funci¢n que devolva a avaliaci¢n dunha expresi¢n nunha  rbore
-¨qu‚ dous percorridos necesito para establecer a estructura dunha  rbore 
binaria?
 prefixa e infixa, ver (*)
-funci¢n que pas ndolle unha  rbore binaria devolve o nivel da  rbore que 
m is nodos cont‚n e o n£mero de nodos dese nivel.

ARBORES ESPECIFICAS
~~~~~~~~~~~~~~~~~~~
Arbores binarias de b£squeda: Estructura non lineal na cal cada elemento
t‚n 0, 1 ou 2 sucesores establec‚ndose unha relaci¢n de orde entre un 
sucesor, o elemento e o outro sucesor.

Def.- Para todo nodo dun certo tipo dunha  rbore de b£squeda:
-d‚bese establecer entre os nodos da  rbore alg£n tipo de relaci¢n de orde.
-en base   relaci¢n t¢dolos nodos   esquerda dun dado deben ser
menores ou iguais ca este e os da dereita maiores ou iguais ca este.

A estructura dunha  rbore binaria de b£squeda depende da implementaci¢n
e da secuencia de entrada dos datos.

(*) exemplo:

se temos dous percorridos seguintes dunha  rbore binaria de b£squeda:
Inorde: C B E D A G H F 
Preorde: A B C D E F G H      (nota: a orde alfab‚tica non interv‚n)

A preorde indica que a raiz da  rbore ‚ A, daquela na inorde 
"tiramos" de A cara arriba:
                 A
                / \
Inorde: C B E D   G H F
Rep¡tese o proceso recursivamente cos sub rbores esquerdo e dereito
A preorde indica que a seguinte raiz ‚ B, repetimos o proceso:
                 A
                / \
              B     
             / \
Inorde:    C   D   G H F 
               /
              E
Qu‚danos por resolver a sub rbore dereita de A:
Inorde:  G H F 
Preorde: F G H
Tiramos de F que ‚ a raiz e qu‚danos (segundo indica a inorde) a sub rbore
esquerda por resolver):
Inorde:  G H ( esquerda - raiz - dereita )
Preorde: G H ( raiz - esquerda - dereita )     H queda   dereita de G
O resultado ‚:
       A
    /     \
   B        F
 /   \    /
C     D  G
     /     \ 
    E        H

E' necesario ter a preorde.

Exercicio: atopar un nodo nunha  rbore binaria de b£squeda.

{----------------------------------------------------------------}
procedure buscar {iterativamente}
( raiz : tipoarbore ; valor : tipoinfo ; var atopado : boolean ) ;

var
   ptr : tipoarbore ;
begin
     ptr := raiz ;
     atopado := false ;
     while ( ptr <> nil ) and ( not atopado ) do 
          if ( ptr ^ . info = valor ) 
          then atopado := true
          else
               if ( ptr ^ . info > valor )
               then ptr := ptr ^ . esq 
               else ptr := ptr ^ . dta ;
end ; { procedure }
{----------------------------------------------------------------}
procedure buscar {recursivamente}
( raiz : tipoarbore ; valor : tipoinfo ; var atopado : boolean ) ;

var
   ptr : tipoarbore ;
begin
     if raiz = nil
     then atopado := false
     else
          if ( raiz ^ . info = valor )
          then atopado := true
          else
               if ( raiz ^ . info > valor )
               then buscar ( raiz ^ . esq , valor , atopado )
               else buscar ( raiz ^ . dta , valor , atopado ) ;
end ; { procedure }
{----------------------------------------------------------------}

Inserci¢n de nodos en  rbores binarias de b£squeda
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) comparar a clave a insertar ca raiz da  rbore. Se ‚ maior d‚bese 
avanzar cara a sub rbore dereita. Se ‚ menor d‚bese mover   sub rbore
esquerda. 
2) repetir sucesivamente o paso anterior ata que se cumpra algunha das
seguintes condici¢ns:
        -A sub rbore dereita ‚ igual   baleira; ou a sub rbore esquerda ‚
         igual ¢ baleira. Ins‚rtase no lugar axeitado.
        -A clave que se quere insertar ‚ igual   raiz da  rbore.
         Non se realiza inserci¢n.

{---------------------------------------------------------------}
procedure insertar ( var raiz : tipoarbore ; valor : tipoinfo ) ;
{ implementaci¢n recursiva }
begin
     if ( raiz = nil ) then begin
        new ( raiz ) ;
        raiz ^ . info := valor ;
        raiz ^ . esq := nil ;
        raiz ^ . dta := nil ;
     end 
     else 
        if ( raiz ^ . info > valor ) 
        then insertar ( raiz ^ . esq , valor ) 
        else insertar ( raiz ^ . dta , valor ) 
        { recursi¢n de cola } 
end ; { procedure }
{--------------------------------------------------------------}
{ implementaci¢n iterativa }
var
   novo , ptr , anterior : tipopunteiro ;
   clavenova : tipoclave ;
begin
     new ( novo ) ;
     novo ^ . esq := nil ;
     novo ^ . dta := nil ;
     novo ^ . info := info ;
     clavenova := info ;
     
     ptr := raiz ;
     anterior := nil ;
     while ptr <> nil do begin
        anterior := ptr ;
        if ptr ^ . info > clavenova 
        then ptr := ptr ^ . esq 
        else ptr := ptr ^ . dta
     end ; { while }                          

        if anterior = nil 
        then raiz := novonodo
        else
            if anterior ^ . info . clave > clavenova
            then anterior ^ . esq := novonodo
            else anterior ^ . dta := novonodo
end ; { insertar iterativo }

Supresi¢n de nodos en  rbores binarias de b£squeda
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
primeiro hai que encontrar o nodo que queremos eliminar. Despois
consiste en eliminar un nodo da  rbore binaria de b£squeda sen violar os
principios que precisamente o definen. Hai os seguintes casos, en funci¢n
de se o n£mero de fillos ‚ 0, 1 ou 2:
-se o elemento a borrar ‚ terminal ou folla, simplemente supr¡mese.
-se o elemento a borrar t‚n un so descendente, sutit£ese por ese
descendente.
-se o elemento a borrar t‚n dous descendentes, sutit£ese polo nodo
que se atopa m is   dereita da sub rbore esquerda.

exemplo:
                                   9
                                 /   \
                               /       \
              suprimir ----> 5           10
                           /   \
                         /       \
                       1           7
                     /   \       /   \
                  -1       2    6     8
                 /   \       \
               -2      0       4 <--- substituir por este
                             /
                           3

Do que se trata ‚ de localizar o elemento maior da sub rbore esquerda
do que vamos a borrar. Tam‚n poder¡amos localizar o elemento menor da
sub rbore dereita. 
E' dicir facemos o movemento 1   esquerda, todo   dereita
(ou na outra opci¢n far¡amos 1   dereita, todo   esquerda)
e logo "pont‚ase" do pai ¢ fillo do elemento que vimos de borrar.

Ca primeira soluci¢n quedar¡a:

                                   9
                                 /   \
                               /       \
                             4           10
                           /   \
                         /       \
                       1           7
                     /   \       /   \
                  -1       2    6     8
                 /   \       \
               -2      0       3
                              
Ca segunda soluci¢n quedar¡a:                             

                                   9
                                 /   \
                               /       \
                             6           10
                           /   \
                         /       \
                       1           7
                     /   \           \
                  -1       2          8
                 /   \       \
               -2      0       4 
                             /
                           3

procedure suprimir ( var raizarbore : tipoarbore ; valorclave : tipoclave ) ;
var
   ptr , anterior : tipopunteiro ;
begin
     ptr := raizarbore ; anterior := nil ;
     while ptr ^ . info . clave > valorclave do begin
          anterior := ptr ;
          if ptr ^ . info . clave > valorclave 
          then ptr := ptr ^ . esquerdo
          else ptr := ptr ^ . dereito ;
     end ; { while }
     { suprimir nodo apuntado por ptr ; anterior apunta ¢ pai dese nodo }
     suprimirnodo ( raizarbore , ptr , anterior ) ;
end ;

procedure suprimirnodo ( var raiz : tipopunteiro ; ptr , anterior : tipopunteiro ) ;
{
Suprime o nodo apuntado por ptr; anterior ‚ un punteiro para o nodo pai, ou
‚ nil se o nodo a suprimir ‚ a raiz
}
var
   temp : tipopunteiro ;
begin
     { caso de supresi¢n dunha folla }
     if ( ptr ^ . dereito = nil ) and ( ptr ^ . esquerdo = nil )
     then 
          if anterior = nil
          then raiz := nil
          else 
              if anterior ^ . dereito = ptr
              then anterior ^ . dereito := nil
              else anterior ^ . esquerdo := nil
     else
          { caso de supresi¢n de nodo con dous fillos }
          if ( ptr ^ . dereito <> nil ) and ( ptr ^ . esquerdo <> nil ) then begin
             { 
             Buscar o valor a reemprazar. Atopar o nodo que cont‚n o
             valor m is pr¢ximo ¢ que se vai a suprimir 
             }
             anterior := ptr ;
             temp := anterior ^ . esquerdo ;
             while temp ^ . dereito <> nil do begin
                  anterior := temp ;
                  temp := temp ^ . dereito ;
             end ;
             { copiar a informaci¢n }
             ptr ^ . info := temp ^ . info ;
             if anterior = ptr 
             then anterior ^ . esquerdo := temp ^ . esquerdo 
             else anterior ^ . dereito := temp ^ . esquerdo ;
             .
             .
             .
             if ptr ^ . dereito <> nil 
             then
                 if anterior = nil
                 then raizarbore := ptr ^ . dereito 
                 else
                     if anterior ^ . dereito = ptr
                     then anterior ^ . dereito := ptr ^ . dereito
                     else anterior ^ . esquerdo := ptr ^ . dereito
             else
                 if anterior = nil
                 then raizarbore := ptr ^ . esquerdo
                 else
                     if anterior ^ . dereito = ptr 
                     then anterior ^ . dereito := ptr ^ . esquerdo
                     else anterior ^ . esquerdo := ptr ^ . esquerdo ;
             dispose ( ptr )
          end ; { if }
end ; { suprimirnodo }

Unha soluci¢n alternativa para a supresi¢n dun nodo nunha  rbore binaria
de b£squeda:

                                   11
                                 /   
                               /       
                             9          
                           /   \
                         /       \
         suprimir ---> 5           10
                     /   \  
                   /       \
                 -1         7 
                /   \     /   \
             -2      2   6     8 
                    /
                   0

                                   11
                                 /   
                               /       
                             9          
                           /   \
                         /       \
                       /           10
                     /       
                   -1     
                  /   \  
               -2      2 
                      /  \
                     0     7 
                         /   \
                        6     8 

{ implementaci¢n iterativa }

{ implementaci¢n recursiva }
procedure eliminar ( var raiz : tiponodo ; valor : info ) ;
var
   aux : tiponodo ;

          procedure delete ( var r : tiponodo ) ;
          begin
               if ( r ^ . dereita <> nil )
               then delete ( r ^ . dereita )
               else begin
                    aux ^ . info := r ^ . info ;
                    aux := r ;
                    r := r ^ . esq ;
               end ; { else }
          end ; { delete }

begin { eliminar }
     if raiz <> nil
     then 
         if ( valor < raiz ^ . info ) 
         then eliminar ( raiz ^ . esquerda , valor )
         else
             if ( valor > raiz ^ . info )
             then eliminar ( raiz ^ . dereita , valor )
             else begin
                 aux := raiz ;
                 if ( raiz ^ . dereita = nil )
                 then raiz := aux ^ . esquerda
                 else
                     if ( raiz ^ . esquerda = nil )
                     then raiz := aux ^ . dereita 
                     else delete ( aux ^ . esquerda ) ;
             end ; { else }
             dispose ( aux ) ;
end ; { eliminar }

OUTRAS ESTRUCTURAS DE TIPO ARBORE
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Arbores entrelazadas: melloran os percorridos.
Arbores balanceadas: melloran o rendemento en operaci¢ns de b£squeda.
Tries: empr‚ganse para a implementaci¢n de diccionarios.
Arbores multicami¤o: empr‚ganse para tomas de decisi¢n.
Mont¡culos: empr‚ganse para operaci¢ns de ordenaci¢n.
     Complexidade nùlg 2 (n), melloran a ordenaci¢n por mistura.
     Empr‚ganse  s veces para implementar colas de prioridade.

ARBORES BINARIAS ENTRELAZADAS
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Melloran as operaci¢ns de percorrido sobre todo a de percorrido en 
profundidade. A idea consiste en eliminar a pila.

Os nodos comp¢¤ense de cinco campos:
-info
-2 punteiros: dereita, esquerda
-2 valores booleanos. Se o campo booleano ‚ true, o punteiro dereita ou
esquerda segundo sexa o caso apunta a un antecesor e non a un descendente,
neste caso apunta ¢ seu antecesor seguinte no percorrido inorde.

                                    50
                                  /  ^ \
                                /    |   \
                              /      |     \
                            30       |      57
                          /  ^ \     |         \ 
                        /    |   \   |           \
                      /      |     \ |             \
                     10      |      40               60
                   / ^  \    |     / ^              / ^ \
                 5 ---   15  |   35  |            /   |   \
                           \ |     \ |           58 ---    80
                             20     38
                                                             [inorde]

esta ‚ unha  rbore entrelazada pola dereita: ¢ non ser necesarias as                           
chamadas recursivas af¢rrase tempo e memoria.

en xeral o tipo nodo ‚:
      ÚÄÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄÄ¿
      ³ L th ³ Esq ³ Info ³ Der ³ R th ³
      ÀÄÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÄÙ        

Implementaci¢n:

type
     tipo_nodo = ^ nodo ;
     nodo = record
                  info : tipoinfo ;
                  esq , der : tiponodo ;
                  rth : boolean ;
            end ;

segundo esta implementaci¢n (coincide ca do exemplo) o nodo ‚ as¡:
      ÚÄÄÄÄÄÂÄÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄÄ¿
      ³ Esq ³ Info ³ Der ³ R th ³
      ÀÄÄÄÄÄÁÄÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÄÙ        

{ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ}
function arbore ( x : tipoinfo ) : tiponodo ;
var
   ptr : tiponodo ;
begin
     new ( ptr ) ;
     ptr ^ . info := x ;
     ptr ^ . esq := nil ;
     ptr ^ . der := nil ;
     ptr ^ . rth := false ;
end ;
{ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ}
{ percorrido en inorde para  rbores entrelazadas pola dereita }
procedure inorde ( a : entrelazada_der ) ;
begin
     if a <> nil then begin
       while a ^ . dereita <> nil do begin
          while a ^ . esq <> nil do 
               a := a ^ . esq ;
          procesa ( a ) ;
          a := a ^ . der ;
       end ;
       procesa ( a ) ;
     end ;
end ;
{ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ}
procedure insertaresquerda ( p : tiponodo ; x : tipoinfo ) ;
var
   q : tiponodo ;
begin
     if ( p <> nil ) then begin
       if ( p ^ . esq <> nil ) then begin
          q := arbore ( x ) ;
          p ^ . esquerda := q ;
          q ^ . dereita := p ;
          q ^ . rth := true ;
       end ;
     end ;
end ;
{ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ}
procedure insertardereita ( p : tiponodo ; x : integer ) ;
var
   q , r : tiponodo ;
begin
     if p <> nil then begin
       if ( p ^ . dereita <> nil ) then
         if p ^ . rth { non t‚n fillos   dereita } then begin
           q := arbore ( x ) ;
           r := p ^ . dereita ;
           p ^ . rth := false ;
           p ^ . dereita := q ;
           q ^ . dereita := r ;
           q ^ . rth := true ;
         end ; { non t‚n fillos   dereita }
         if ( p ^ . dereita = nil ) then begin
           q := arbore ( x ) ;
           p ^ . dereita := q ;
         end ; { derradeiro nodo }
     end ; { if p <> nil }
end ; { insertadereita }

{ procesamento de  rbore enlazada en inorde }
{ ev¡tanse a recursividade e as pilas }

procedure inorde ( tree : tiponodo ) ;
var
   p , q : tiponodo ;
begin
     p := tree ;
     repeat
           q := nil ;
           while ( p <> nil ) do begin
                q := p ;
                p := p ^ . esquerda ;
           end ; { while }
           if ( q <> nil ) then begin
             write ( q ^ . info ) ;
             p := q ^ . dereita ;
             while ( q ^ . rth ) do begin
                  write ( p ^ . info ) ;
                  q := p ;
                  p := p ^ . dereita ;
             end ; { while }
           end ; { if }
     until ( q = nil ) ;
end ; { inorde }

ARBORES BALANCEADAS ( AVL )
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Nas  rbores binarias de b£squeda p¢dense realizar eficientemente as
operaci¢ns de b£squeda, inserci¢n e eliminaci¢n de nodos. Sen embargo, se
a  rbore medra ou decrece descontroladamente o rendemento pode disminuir
considerablemente.

Con obxecto de mellorar o rendemento na b£squeda xorden as  rbores
balanceadas (AVL). A idea ‚ a de realizar reacomodos ou balanceos
despois de inserci¢ns ou eliminaci¢ns de elementos.

Def.- Def¡nese unha  rbore balanceada como unha  rbore binaria de b£squeda na
cal se debe de cumprir a seguinte condici¢n:
     "para cada nodo T da  rbore, a altura das sub rbores esquerdo e
      dereito non debe diferir en m is dunha unidade"

A complexidade deste tipo de  rbore en canto ¢ tempo ‚ moi superior  s
anteriores  rbores.

As  rbores balanceadas te¤en unha certa similitude, en canto ¢ seu mecanismo 
de formaci¢n, ¢s n£meros de Fibonacci. A  rbore de altura 0 ‚ baleira, a
 rbore de altura 1 t‚n un £nico elemento e en xeral o n£mero de nodos
dunha  rbore con altura h > 1 calc£lase mediante a seguinte f¢rmula:

          k  = k    + 1 + k
           h    h-1        h-2

onde k ‚ o n£mero de nodos e h a altura da  rbore.

Para poder determinar se unha  rbore est  balanceada ou non, debe manexarse
informaci¢n relativa ¢ equilibrio de cada nodo da  rbore (factor de 
equilibrio dun nodo, FE).

O FE def¡nese como a altura da sub rbore dereita menos a altura da
sub rbore esquerda.

     FE = H   - H
           rd    re

onde r* ‚ a rama * e H   ‚ a altura da rama *
                      r*
Os valores que pode tomar FE son -1, 0, ou 1 e -2 ou 2 na situaci¢n previa
a reestructurar a  rbore.

Inserci¢n en AVL
~~~~~~~~~~~~~~~~
     1.- Localizar o lugar onde hai que insertar o elemento.
     2.- Calcular o seu FE, que ser  0 e regresar polo cami¤o de b£squeda
         calculando o FE dos distintos nodos.
     3.- Se alg£n de dichos nodos viola o criterio de equilibrio, d‚bese
         reestructurar a  rbore.
     4.- O proceso remata ¢ chegar   raiz da  rbore ou cando se realiza
         a reestructuraci¢n do mesmo, neste caso non ‚ necesario determinar
         o FE dos restantes nodos.

Caso 1.- As ramas esquerda re e dereita rd te¤en a mesma altura ...
          1.1.- ... e ins‚rtase en re : Hre > Hrd ( rbore balanceada)
          1.2.- ... e ins‚rtase en rd : Hrd > Hre ( rbore balanceada)

Caso 2.- As ramas esquerda re e dereita rd te¤en distinta altura ...
          2.1.- ... e Hre < Hrd ...
               2.1.1.- ... e ins‚rtase en re : Hrd = Hre ( rbore balanceada)
               2.1.2.- ... e ins‚rtase en rd : REEQUILIBRAR 
          2.2.- ... e Hre > Hrd ...
               2.2.1.- ... e ins‚rtase en re : REEQUILIBRAR 
               2.2.2.- ... e ins‚rtase en rd : Hrd = Hre ( rbore balanceada)

REEQUILIBRAR consiste en rotar os nodos da  rbore.

                           DD fillo dereito da raiz pasa a ser a raiz
        Simple ( 2 nodos )
                           EE fillo esquerdo da raiz pasa a ser a raiz
Rotaci¢n
                              DE
        Composta ( 3 nodos ) 
                              ED

=============================================================================
Rotaci¢n simple: dous nodos cambian de posici¢n:
-----------------------------------------------------------------------------
Rotaci¢n EE :
   
        (k2)                            (k1)
       /    \                          /    \
    (k1)     /3\         ------->    /1\    (k2)
    /  \                                    /  \
  /1\  /2\                                /2\  /3\
                             
                             /i\ son sub rbores dos que a forma non importa  
-----------------------------------------------------------------------------
Rotaci¢n DD :
   
        (k1)                            (k2)
       /    \                          /    \
     /1\    (k2)         ------->    (k1)   /3\ 
            /  \                     /  \
          /2\  /3\                 /1\  /2\
                             
                             /i\ son sub rbores dos que a forma non importa
=============================================================================
Rotaci¢n composta: tres nodos cambian de posici¢n:
-----------------------------------------------------------------------------
a rotaci¢n DE (dereita->esquerda) ‚ en xeral as¡:

         (k1)                             (k2)
        /   \                            /    \
      /1\   (k3)                      (k1)    (k3)
            /   \         ÍÍÍ>        /  \     /  \
          (k2)  /4\                 /1\  /2\ /3\  /4\
          / \                   
        /2\ /3\                    
       
                             /i\ son sub rbores dos que a forma non importa
-----------------------------------------------------------------------------
a rotaci¢n ED (esquerda->dereita) ‚ en xeral as¡:

         (k1)                             (k2)
        /   \                            /    \
     (k3)   /4\                       (k1)    (k3)
     /  \                ÍÍÍ>        /  \     /  \
   /1\   (k2)                      /1\  /2\ /3\  /4\
          / \                      
        /2\ /3\                    

                             /i\ son sub rbores dos que a forma non importa
-----------------------------------------------------------------------------

outro exemplo:

          B
        /   \
      A       D                 insertar E ( ir¡a en * )
            /   \
          C       K
                /
              *

o resultado ‚:

              D                 rotaci¢n DD
            /   \
          B       K
        /  \     /
       A    C   E

          B
        /   \
      A       D                 insertar E ( ir¡a en * )
            /   \
          C       K
                /
              *

-----------------------------------------------------------------------------
Insertar o 13 no seguinte  rbore AVL:          Ir¡a en *

entre par‚nteses vai o FE
                                  10 (1)
                                /     \
                              /         \
                            5 (0)        20 (0)
                          /   \         /   \
                         2 (0) 7 (0)  15 (0)  25 (1)
                                     /  \       \
                                (0) 12  17 (0)   30 (0)
                                      \
                                       *

a situaci¢n antes da rotaci¢n ser¡a:

                                  10 (2) <ÄÄÄ hai que reequilibrar
                                /     \
                              /         \
                            5 (0)        20 (-1)
                          /   \         /   \
                         2 (0) 7 (0)  15(-1)  25 (1)
                                     /  \       \
                                (1) 12  17 (0)   30 (0)
                                      \
                                       13 (0)

daquela o resultado ‚:
                                   15
                                 /    \ 
                               /        \
                             10          20     
                            /  \        /   \
                          5     12    17      25    
                         / \      \             \
                        2   7      13            30    
                                       
e cos FE's:                                          
                                   15(0)
                                 /    \ 
                               /        \
                          (0)10          20(1)  
                            /  \        /   \
                      (0) 5  (1)12    17(0)   25 (1)
                         / \      \             \
                        2   7      13(0)         30 (0)
                       (0)  (0)

Dada a  rbore inicial

   58
  /  \        (FE=0 nos tres nodos)
43    75

insertar 86, 65, 70, 67, 73, 93, 69, 25, 66, 68, 47, 62, 10, 60

   58 (1)                            58 (1)
  /  \                             /    \
43    75 (1)                     43      75 (0)
(0)     \                       (0)     /  \
         86 (0)                       65    86
                                      (0)  (0)

            58 (2)  
          /    \                                           65 (0)
        43      75 (-1)                                  /    \
       (0)     /  \          engade interior           58      75 (0)
          (1)65    86(0)     da dereita -> r.DE       / (-1)  /  \
               \                                    43       70   86
                70                                 (0)       (0)  (0)
                (0)

(sen acabar)

{ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ}
procedure inserta_balanceada 
( var nodo : tiponodo ; var bo : boolean ; info : tipoinfo ) ;
{
     nodo ‚ a  rbore AVL , info ‚ a informaci¢n a insertar

     Inicialmente bo ‚ FALSE
}
var
   outro , nodo1 , nodo2 : tiponodo ;
begin
     if ( nodo <> nil ) then begin 
       if ( info < nodo ^ . info ) then begin
         insertar_balanceada ( nodo ^ . esquerda , bo , info ) ;
         if ( bo ) then begin
           case nodo ^ . fe of
           1 : begin 
                    nodo ^ . fe := 0 ; 
                    { 
                    se FE se fai cero bo ‚ false porque nos nodos
                    anteriores non se incrementan niveis:
                            o
                          /   \         x ‚ o nodo insertado
                         o     o
                        / \   / \       o FE do pai de x pasa de 1 a 0
                       x   o o   o 
                    }
                    bo := false ; 
               end ; { o factor de equilibrio ‚ 1 }
           0 : nodo ^ . fe := -1 ; { estaba equilibrado e se engade   esquerda }
           -1 : begin { hai que reestructurar a  rbore }
                     nodo1 := nodo ^ . esquerda ;
                     if ( nodo1 ^ . FE = -1 ) then begin
                       {---------- rotaci¢n EE ----------}
                       nodo ^ . esquerda := nodo1 ^ . dereita ;
                       nodo1 ^ . dereita := nodo ;
                       nodo ^ . fe := 0 ;
                       nodo := nodo1 ;
                     end { o fillo esquerdo do nodo t‚n FE = -1 }
                     else begin { o fillo esquerdo do nodo NON t‚n FE -1 }
                         {---------- rotaci¢n ED ----------}
                         nodo2 := nodo1 ^ . dereita ;
                         nodo ^ . esquerda := nodo2 ^ . dereita ;
                         nodo2 ^ . dereita := nodo ;
                         nodo1 ^ . dereita := nodo2 ^ . esquerda ;
                         nodo2 ^ . esquerda := nodo1 ;
                         if ( nodo2 ^ . fe = -1 ) 
                         then nodo ^ . fe := 1 
                         else nodo ^ . fe := 0 ;
                         if ( nodo2 ^ . fe = 1 ) 
                         then nodo1 ^ . fe := -1
                         else nodo1 ^ . fe := 0 ;
                         nodo := nodo2 ;
                     end ; { o fillo esquerdo do nodo NON t‚n FE -1 }
                end ; { fin de : o factor de equilibrio ‚ -1 }
           end ; { case }
           nodo ^ . fe := 0 ; 
           bo := false 
         end ; { bo ‚ TRUE }
       end { fin de : a informaci¢n a insertar ‚ menor que a da raiz }
       else 
           if ( info > nodo ^ . info ) then begin 
             inserta_balanceada ( nodo ^ . dereita , bo , info ) ;
               if ( bo ) then begin { bo ‚ TRUE }
                 case nodo ^ . fe of
                 -1 : begin
                           nodo ^ . fe := 0 ;
                           bo := false ;
                      end ; { nodo ^ . fe = -1 }
                 0 : nodo ^ . fe := 1 ;
                 1 : begin { hai que reestructurar a  rbore }
                          nodo1 := nodo ^ . dereita ;
                          if ( nodo1 ^ . fe = 1 ) then begin 
                            {---------- rotaci¢n DD ----------}
                            nodo ^ . dereita := nodo ^ . esquerda ;
                            nodo1 ^ . esquerda  := nodo ;
                            nodo ^ . fe := 0 ;
                            nodo := nodo1 ;
                          end ; { nodo1 ^ . fe = 1 }
                     end { nodo ^ . fe = -1 }
                     else begin { nodo ^ . fe <> -1 }
                         {---------- rotaci¢n DE ----------}
                         nodo2 := nodo1 ^ . esquerda ;
                         nodo ^ . dereita := nodo2 ^ . esquerda ;
                         nodo2 ^ . esquerda := nodo ;
                         nodo1 ^ . esquerda := nodo2 ^ . dereita ;
                         nodo2 ^ . dereita := nodo1 ;
                         if ( nodo2 ^. fe = 1 ) 
                         then nodo ^. fe := -1 
                         else nodo ^. fe := 0 ;
                         if ( nodo2 ^ . fe = -1 ) 
                         then nodo1 ^ . fe := 1 
                         else nodo1 ^ . fe := 0 ;
                         nodo := nodo2 ;
                     end ; { nodo ^ . fe <> -1 }
               end ; { bo ‚ TRUE }
             end ; { case }
             nodo ^ . fe := 0 ;
             bo := false ;
           end ; { a informaci¢n a insertar ‚ maior que a da raiz }
     end { fin de : se a  rbore NON est  inicialmente baleira }
     else begin { a  rbore est  inicialmente baleira }
         new ( outro ) ;
         outro ^ . info := info ;
         outro ^ . esquerdo := nil ;
         outro ^ . dereito := nil ;
         outro ^ . fe := 0 ;
         bo := true ;
         nodo := outro ;
     end ; { fin de se a  rbore SE est  inicialmente baleira }
end ; { inserta_balanceada }
{ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ}

Supresi¢n en AVL
~~~~~~~~~~~~~~~~
Consiste en quitar un nodo da  rbore sen violar os principios que definen
unha  rbore equilibrada.

PRIMEIRO PASO:

Casos:
-se o elemento a suprimir ‚ unha folla se suprime e iso ‚ todo.
-se o elemento a suprimir t‚n un so descendente t‚n que substituirse
 por ese descendente
-se o elemento a suprimir t‚n dous descendentes, t‚n que substituirse
 polo nodo que se atopa m is   esquerda na sub rbore dereita, ou
 polo nodo que se atopa m is   dereita na sub rbore esquerda.

SEGUNDO PASO:

Reequilibrar se ‚ necesario.

Hai un caso que nunca se daba engadindo nodos (‚ un "quinto caso de 
rotaci¢n"):
  
   1                                    3
 /   \                                /   \
X     3                              1     4
     / \            -------->         \   /s4\
    /   \                              2
   2     4                            /s2\
 /s2\   /s4\

-buscar o Cair¢ a errata que hai no algoritmo de supresi¢n.

EXERCICIOS RESOLTOS.-

exercicio: secuencia de creaci¢n A, B, M, J, C, K, L, S, D, F, I, P, R, G

A  A     A(2)              B       B        B                    B
    \     \       DD      / \     / \     /   \       EE       /   \
     B     B     ---->   A   M   A   M   A     M(-2) ---->    A     J
            \                       /         /                    / \
             M                     J         J                    C   M
                                            /
                                           C

   B(2)                   J             J            J
 /   \       DD        /    \        /    \       /    \
A     J     ---->     B      M      B      M     B      M
     / \             / \    /      / \    /     / \    / \
    C   M           A   C  K      A   C  K     A   C  K   S
       /                                  \            \
      K                                    L            L

      J                J                          J
   /    \          /      \                   /      \
  B      M        B        M       DD        B        M
 / \    / \      / \      / \     ---->     / \      / \
A   C  K   S    A   C(2) K   S             A   D    K   S
     \  \            \    \                   / \    \
      D  L            D    L                 C   F    L
                       \
                        F

      J                        J                     J
   /    \                  /      \               /     \
  B(2)   M                D        M             D        M
 / \    / \     DD      /   \     / \          /   \    /   \      DD
A   D  K   S   ---->   B     F   K   S        B     F  K(2)  S    ---->
   / \  \             / \     \   \          / \     \  \
  C   F  L           A   C     I   L        A   C     I  L
       \                                                  \
        I                                                  P

         J                    J                      J
      /     \              /     \                /     \
    D         M          D          M           D          M
   / \       / \        / \       /   \        / \       /   \     DE
  B   F     L   S      B   F     L     S      B   F(2)  L     S   ---->
 / \   \   / \        / \   \   / \   /      / \   \   / \   /
A   C   I K   P      A   C   I K   P R      A   C   I K   P R
                                                   /
                                                  G

           J
      /         \
     D            M
   /   \        /   \
  B     G      L     S
 / \   / \    / \   / 
A   C F   I  K   P R
      

exercicio: secuencia de supresi¢n E, I, G, L, F, B, K, D

        F
     /     \
    D       I
   / \     / \
  C   E   H   K
 /       /   / \
B       G   J   L

        F                        F                      F
     /     \                  /     \                /     \
    D       I       EE       C       I              C       H
   /       / \     ---->    / \     / \            / \     / \
  C       H   K            B   D   H   K          B   D   G   K
 /       /   / \                  /   / \                    / \
B       G   J   L                G   J   L                  J   L

        F                        F               F                    F
     /     \                  /     \         /     \               /   \
    C       H      DD        C       K       C       K      ED     C     J
   / \       \    ---->     / \     / \     / \     /      ---->  / \   / \
  B   D       K            B   D   H   L   B   D   H             B   D H   K
             / \                    \               \
            J   L                    J               J

      D               D            D        C
   /     \           / \          / \        \     DE      H
  C       J         C   J        C   J        J   ---->   / \ 
 /       / \           / \          /        /           C   J
B       H   K         H   K        H        H


exercicio: + entran; - saen;   +15, +47, +70, +10, +9, +17, -9, +31, +28, 
+33, +60, +73, -10, -47, +55, +65, +75, +62, -33.

15    15     15                  47          47           47
        \      \       DD       /  \        /  \         /  \       EE
         47     47    ---->   15    70    15    70     15    70    ---->
                  \                       /            /
                   70                   10            10
                                                      /
                                                     9

    47            47                                             15
   /  \          /  \              15          15               /  \
  10  70       10    70   ED      /  \        /  \             10   47
 /  \         /  \       ---->  10    47     10   47                / \
9    15      9    15            /    /  \        /  \             17   70
                    \          9    17  70     17   70             \
                     17                                             31

           17            17            17             17
  DE      /  \          /  \          /  \           /    \
 ---->  15    47      15    47      15    47       15       47
        /     / \     /     / \     /     / \      /     /     \    
       10    31  70  10    31  70  10    31  70   10    31      70
                           /            /  \           /  \     /
                          28           28   33        28   33  60

      17                        47
    /    \                     /   \            33              33
  15       47        DD      17     70        /    \          /    \
         /    \     ---->   /  \   /  \      17     70       17     70
       31      70          15  31 60  33    /  \   /  \     /  \   /  \
      /  \    /  \            /  \         15  31 60  73   15  31 60  73
     28  33  60  73          28  33            /               /  /
                                              28              28 55

      33                33                   33
    /    \            /    \              /     \
  17       70        17     70           17      70
 /  \     /  \      /  \   /  \         /  \    /  \
15  31   60   73   15  31 60  73       15  31  60  73
    /   / \            /  / \   \          /  / \    \
   28  55  65         28 55 65  75        28 55 65   75
                                                /
                                               62

       31 (2)                    60
    /     \                    /    \
  17       70                 31     70
 /  \     /  \         DE    /  \   /  \
15  28   60   73      ----> 17  55 65  73
        /  \    \          /  \    /     \
       55  65    75       15  28  62     75
           /
          62


EXERCICIOS PROPOSTOS.-

exercicio: secuencia de supresi¢n: 25, 75, 66, 65, 62, 10, 43, 47
na  rbore seguinte

                          65
                         /  \
                       /      \
                     /          \
                   /              \
                 43                70
                /  \              /   \
              /      \          /       \
            25        58      60         75
           /         /  \    / \        /  \
          10       47    62 60  69    73    86
                        /       /             \
                      60      68               93

exercicio: secuencia de construcci¢n: 50, 35, 75, 1, 7, 15, 40, 9, 80, 36, 20, 
30, 45, 8, 42, 38, 65, 48, 41

exercicio: secuencia de supresi¢n: 55, 35, 50, 33, 40, 60, 65, 6, 5
na  rbore seguinte:
                                20
                               /  \
                             /      \
                           /          \
                         5               50
                       /   \           /    \
                     1        10      35       65
                      \      / \     /  \     /  \
                       3    6   15  30   40  55    70
                               /     \        \    / \
                              11      33      60  68 77

                                 
                              
                               ÛßßßßßßßßßßßßÛ
                               Û MONTICULOS Û
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßÜÜÜÜÜÜÜÜÜÜÜÜÜÜßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

Un mont¡culo ‚ unha  rbore binaria que satisfai d£as propiedades: unha 
concerninte   s£a figura e outra   orde dos seus elementos:

-‚ unha _ rbore binaria_ que est  _completa_ ou _case completa_, cas follas
do derradeiro nivel tan   esquerda como sexa posible

       /\
     /    \
   /        \
 /     ÚÄÄÄÄÄÄ
ÄÄÄÄÄÄÄÙ

-para todo nodo, c¢mprese que o seu valor ‚ maior ou igual que o valor de
calquera dos seus fillos.

Empr‚ganse para: 
-operaci¢ns de ordenaci¢n -melloran a ordenaci¢n por mistura, complexidade
n log 2 (n)-.
- s veces para o manexo de colas de prioridade.

Representaci¢n dun mont¡culo nun vector lineal.
-----------------------------------------------

Hai que lembrar que:
-o nodo k almac‚nase na posici¢n k correspondente do arreglo
-o fillo esquerdo do nodo k almac‚nase na posici¢n 2ùk
-o fillo dereito do nodo k almac‚nase na posici¢n 2ùk+1

exemplo: dado o mont¡culo...

                         90
                       /    \
                     /        \
                  19            36
                /    \         /  \
              17      3      25    1
             /  \
            2    7

...a representaci¢n nun vector lineal ‚:

90 19 36 17 3 25 1 2 7 

(‚ un percorrido de anchura do mont¡culo)

anchura ( a ) 
     limpacola ( cola )
     if a <> nil 
     then metecola ( a , cola )
     while not colabaleira ( cola ) do begin
          sacacola ( a ) 
          procesar ( a ) 
          if a ^ . esq <> nil 
          then metecola ( a ^ . esq , cola ) 
          if a ^ . der <> nil 
          then metecola ( a ^ . der , cola ) ;

Inserci¢n en mont¡culo.
-----------------------

A operaci¢n de inserci¢n consta de dous pasos:
-ins‚rtase o elemento na primeira posici¢n dispo¤ible no vector.
-verif¡case se o seu valor ‚ maior que o do seu pai. Se ‚ as¡ 
interc mbianse entre s¡ estes dous valores. Se non ‚ as¡, o algoritmo 
chegou   s£a fin. Este paso apl¡case de forma recursiva de abaixo cara
arriba.

exemplo: crear un mont¡culo dada a secuencia    25 17 36 23 90 1 19 2

25.   25       17.        25     36.           25    ->   36
                        17                   17  36     17  25
[25]           [25,17]           [25,17,36]                    [36,17,25]

23.                36    ->     36
                 17  25       23  25
[36,17,25,23]  23           17        [36,23,25,17]

90.                       36     ->      36     ->     90
                        /    \         /    \         /  \
                      23      25     90      25     36    25
[36,23,25,17,90]    17  90         17  23         17  23      [90,36,25,17,23]

1.     90           19.    90                 2.     90
     /    \              /    \                    /    \
   36      25          36      25                36      25
 17  23   1          17  23   1  19            17  23   1  19
                                              2
[90,36,25,17,23,1]   [90,36,25,17,23,1,19]    [90,36,25,17,23,1,19,2]

Ordenaci¢n por mont¡culos ou heapsort.
--------------------------------------

E' o m is eficiente dos m‚todos de ordenaci¢n que usan  rbores.
Consta de dous pasos: construir un mont¡culo; e sacar os elementos do mesmo,
pola raiz e segundo un algoritmo que veremos.

Algoritmo de transformaci¢n dun array desordeado nun mont¡culo.
---------------------------------------------------------------

Supo¤emos un arreglo con elementos de 1 a n, datos desordenados de tipo 
enteiro. Pas ndolle o arreglo, o procedemento troca os valores 
de sitio de modo que o array resultante represente un mont¡culo.

monticulo ( a : vector ; n : enteiros )
variables
         i , k , aux : enteiros
         b : booleana
comezo
          i inicial¡zase a 1, o comezo do vector
          mentres i <= n facer 
               k <- i
               b <- certo
               mentres k > 1 e b = certo facer
                    b <- falso
                    se a [ k ] > a [ enteiro k/2 ] ent¢n
                         trocar ( a [ k ] , a [ enteiro k/2 ] )
                         k <- enteiro k/2
                         b <- certo
                    finse
               finmentres

               i <- i+1

          finmentres
fin

Implementaci¢n din mica.
------------------------
Para engadir un elemento faise un percorrido en anchura e ins‚rtase no
primeiro nodo que te¤a un fillo a nil.
Poder se engadir un campo punteiro ¢ pai do nodo e poder se usar 
recursividade.

Eliminaci¢n dun mont¡culo.
--------------------------
O proceso para obtener os elementos ordenados efectuar se da seguinte
maneira:

1§) reempr zase a raiz co elemento que ocupa a derradeira posici¢n do
mont¡culo.

2§) verif¡case se o valor da raiz ‚ maior c¢s seus dous fillos (maior
c¢ maior dos seus fillos). Se ‚ as¡, remata o algoritmo. Se non ‚ as¡, 
tr¢case a raiz co maior. Apl¡case de forma recursiva dende 
arriba cara abajo.

exemplo:                [90,19,36,17,3,25,1,2,7]

        90           
      /    \         
    19      36       
   / \     /  \
  17  3   25   1      
 /  \
2   7                
        7                     sae o 90
      /    \         
    19      36       
   / \     /  \
  17  3   25   1      
 /  
2 
        36                    recursividade
      /    \         
    19      7       
   / \     /  \
  17  3   25   1      
 /  
2 
        36                    recursividade
      /    \         
    19      25     
   / \     /  \
  17  3   7    1      
 /  
2 
         2                    sae o 2
      /    \         
    19      25     
   / \     /  \
  17  3   7    1      
         
        25                    recursividade
      /    \         
    19      2      
   / \     /  \
  17  3   7    1      
    
...etc

Os mont¡culos son estructuras que serven para representar colas de prioridade.

eliminar ( a : vector ; n : enteiro ) ;
variables
          i , aux , z , d , k , ad , maior : enteiros
comezo
          i <- n
          mentres i > 1 facer
               aux <- a[i]
               a[i] <- a[1]
               z <- 2
               d <- 3 
               k <- 1 
               mentres z < i facer
                    maior <- a[z]
                    ad <- z
                    se maior < a[d] e d <> i ent¢n
                         maior <- a[d]  
                         ad <- d
                    se aux < maior ent¢n
                         a[k] <- a[ad]
                    k <- ad
                    z <- kù2
                    d <- z+1
               finmentres
               a[k] <- aux
               i <- i-1
          finmentres
fin
  
EXERCICIOS RESOLTOS.-

exercicio: crea mont¡culo 25, 17, 36, 2, 3, 90, 1, 19, 7

25   25   25        36      36       36        36          36
     /   /  \  ->  /  \    /  \     /  \     /    \  ->   /  \   ->
    17  17  36    17  25  17  25   17  25   17    25    17    90
                          /       /  \      / \   /     / \   /
                         2       2    3    2   3 90    2   3 25

     90         90            90              90           90
   /   \       /   \        /    \          /   \         /   \
  17   36     17    36     17    36        17    36      19    36
 / \   /     / \   /  \    / \   / \      /  \   / \    /  \   / \
2   3 25    2   3 25   1  2   3 25  1    19   3 25  1  17   3 25  1
                          /              /             /
                         19             2             2

       90
     /    \
   19      36
  /  \    /  \
 17   3  25   1
 / \
2   7


exercicio: quitar tres elementos do seguinte mont¡culo.
       
       90              7                36           36
     /    \          /    \           /    \        /  \             2
   19      36      19      36   ->   19     7  ->  19   25          / \
  /  \    /  \    /  \    /  \      /  \   / \    / \   / \        19  25 ->
 17   3  25   1  17   3  25   1    17   3 25  1  17  3  7  1      / \  / \
 / \             /                 /             /              17  3  7  1
2   7           2                 2             2

     25             25            1         19            19
    /  \           /  \          /  \      /   \         /  \
   19    2       19     7      19    7    1     7       17    7
  / \   / \      / \   / \    /  \   /   / \   /       / \   /
17   3 7   1   17   3 2   1  17   3 2   17  3 2       1   3 2


EXERCICIOS PROPOSTOS.-

pasando a raiz da seguinte estructura e aproveitando as caracter¡sticas
de  rbore enhebrada, sen recursividade nin pilas, con nodo cabeceira, facer
o percorrido preorde e inorde.


                      ÚÄÄÄ¿
                      ³   ³ <--- raiz
                      ÃÄÄÄ´
            ÚÄÄÄÄÄÄÄ> ÀÄÄÄÙ <Ä¿
            ³           ³     ³
            ³           V     ³
            ³          (  )   ³
            ³         / ^^ \  ³
            ³        /  ³³  \ ³
            ³       /   ³³   \³
            ³    (  )   ³ÀÄÄ(  )
            ³   / ^^ \  ³
            ³  /  ³³  \ ³
            ³ /   ³³   \³
           (  ) ÄÄÙÀÄ (  )