ARBOLES

PARTE 1
CLASE N12
Leissi M. Castaeda Len
lcl@[Link]
lcl@[Link]
[Link]

Que veremos hoy?

Arboles

1.
2.
3.
4.
5.
6.

Arboles Binarios
Arboles Binarios de Bsqueda
Arboles AVL
Arboles B
Arboles B+
Arboles Roji-Negro

rboles

Introduccin

Se han estudiado estructuras de datos lineales, tanto

estticas como dinmicas: a cada elemento siempre le
sucede o le precede como mximo otro elemento.
Ahora se va a introducir el concepto de ramificacin
entre nodos para estudiar la estructura de datos rboles.
Los rboles son las estructuras de datos no lineales
(cada elemento puede tener ms de un sucesor) y
dinmicas (cambiar de forma o tamao durante la
ejecucin) de datos ms importantes.

Introduccin

Los rboles balanceados o AVL son la estructura de

datos ms eficiente para trabajar con la memoria
principal (o interna), mientras que los rboles B y B+ con
la memoria secundaria (externa).

rboles

Un rbol se puede definir como una estructura

jerrquica aplicada sobre una coleccin de elementos u
objetos llamados nodos, uno de los cuales se denomina
raiz.

Formalmente se define un rbol de tipo T como una

estructura homognea resultado de la concatenacin de
un elemento de tipo T con un nmero finito de rboles
disjuntos, llamados subrboles.
Una forma particular de rbol es el rbol vaco.

rboles

Estructuras recursivas, ya que cada subrbol es a su

vez un rbol.
Un rbol se puede representar de diferentes formas
(notaciones) y todas ellas se consideran equivalentes:






Diagramas de Venn
Anidacin de parntesis
Notacin decimal de Dewey
Notacin Indentada
Grafo (se distinguen nodos y arcos)

Ejemplo

b) (A(B(D(I),E,F,(J,K)),C(G,H(L))))

c) 1.A, 1.1.B,
1.1.1.D, [Link].I,
1.1.2.E, 1.1.3.F,
[Link].J,
[Link].K, 1.2.C,
1.2.1.G, 1.2.2.H,
[Link].L

Caractersticas y Propiedades de los

rboles

Todo rbol que no es vaco tiene un

nico nodo raz
Un nodo X es descendiente directo de
un nodo Y, si el nodo X es apuntado
por el nodo Y. En este caso decimos: X
es hijo de Y.
Un nodo X es antecesor directo de un
nodo Y, si el nodo X apunta al nodo Y.
En este caso decimos: X es padre de
Y.
Todos los nodos que son
descendientes directos hijos de un
mismo nodo padre son hermanos.

B
D

F
J

11

Caractersticas y Propiedades de los

rboles (cont.)

Todo nodo que no tiene ramificaciones

hijos-, se conoce como terminal u hoja.
Todo nodo que no es raz ni hoja, se
conoce como interior.
Grado es el nmero de descendientes
directos de un determinado nodo.
Grado del rbol es el mximo grado de D
todos los nodos del rbol.
Nivel es el nmero de arcos que deben I
ser recorridos para llegar a un
determinado nodo. Raz nivel 1.
Altura es el mximo nmero de niveles
de todos los nodos del rbol.

F
J

12

Longitud de camino interno y externo

Se define la longitud de camino del nodo X como el

nmero de arcos que se deben recorrer para llegar
desde la raz hasta el nodo X.

Por definicin la raz tiene longitud de camino 1, sus

descendientes directos longitud de camino 2 y as
sucesivamente.

13

Longitud de Camino Interno (LCI)

La LCI del rbol es la suma de las longitudes de camino

de todos los nodos del rbol.
Esta medida es importante porque permite conocer los
caminos que tiene el rbol.
Se calcula por medio de la siguiente frmula:

LCI =

n
i =1

*i

Donde i representa el nivel de rbol, h su altura y n i el

nmero de nodos en el nivel i.
La media de la longitud de camino interno: LCIM=LCI/n
14

Ejemplo
h

LCI = ni * i

B
D

i =1

LCI = 1*1 + 2*2 + 5*3 + 4*4

= 36

Longitud de camino externo (LCE)

Para definir la longitud de camino externo de un rbol es

necesario primero explicar los conceptos de rbol
extendido y nodo especial.

rbol extendido: aquel en el que el nmero de hijos de

cada nodo es igual al grado del rbol. Si algn nodo no
cumple con esta condicin, entonces deben
incorporarse los nodos especiales requeridos.

Nodos especiales: tienen como objetivo reemplazar las

ramas vacas o nulas, no puede tener descendientes. Se
representa en forma de cuadrado.
16

Longitud de camino externo (LCE)

Podemos definir entonces la LCE de un rbol como la

suma de las longitudes de camino de todos los nodos
especiales del rbol. Se calcula por medio de la
siguiente frmula:
h +1

LCE =

n
i=2

ei

*i

Donde i representa el nivel del rbol, h su altura y nei el

nmero de nodos especiales en el nivel i. Observe que i
comienza desde 2, puesto que la raz se encuentra en el
nivel i y no puede ser nodo especial.
La media: LCEM=LCE/ne
17

Ejemplo
A

h +1

LCE = nei * i

i=2

LCE = 1*2 + 1*3 + 11*4 + 12*5 = 109

Ejercicio

Hallar el camino interno, media del camino interno y el

camino externo de:

rboles Binarios

20

rboles Binarios

Un rbol ordenado es aquel en el cual la distribucin de

las ramas sigue un cierto orden.

Los rboles ordenados de grado 2 son conocidos como:

rboles binarios.

En un rbol binario cada nodo puede tener como

mximo dos subrboles y stos se distinguen entre s
como subrbol izquierdo y subrbol derecho, segn su
ubicacin con respecto a la raz.

21

rboles Binarios: aplicaciones

Las aplicaciones de los arboles binarios son muy

variadas ya que se les puede utilizar para representar
una estructura en la cual es posible tomar decisiones
con dos opciones en distintos puntos.

Ejemplo:


rboles Binarios de Bsqueda

27
14

47

7
59

32
11

50
77
22

 Representacin de una expresin algebraica.

+
*

^
3.5

23

 rbol Genealgico.
Osvaldo Cario
Battistuti

Jose Cario
Scandallo

Antonio Cario
Godoy

Maria Scandallo
Miscoria

Maria Battistuti
Valiente

Roberto Battistuti
Mazzotti

Maria Valiente
Martin

24

rboles binarios distintos, similares y

equivalentes

Distintos: cuando sus estructuras, la distribucin de

nodos y arcos son diferentes.
A

A)

B)
B

C
D

B
C

rboles binarios distintos, similares y

equivalentes

Similares: cuando sus estructuras son idnticas pero la

informacin que contienen sus nodos difiere entre s
A

A)

F
A

B)
C
B

R
D

rboles binarios distintos, similares y

equivalentes

Equivalentes: aquellos que son similares y adems la

informacin de sus nodos contienen la misma
informacin
A
A
A)
B
B
A

B)

A
C
C

B
D
D

Qu relacin encuentra en los siguientes

rboles binarios?
A

A)

B)

N
D

C)

D)

A
C

B
D

A)

B)

N
D
A

C)

D)

A
C

B
D

El rbol de la figura C es distinto de los rboles de la figura A,B

Los rboles de la figura A, B y D son similares.

Los rboles de la figura A y D son equivalentes.

rboles binarios completos

Se define un rbol binario completo como un rbol en el

que todos sus nodos, excepto los del ltimo nivel, tienen
dos hijos; el subrbol izquierdo y el subrbol derecho.
Ejemplo:
A
A) DE ALTURA 3:

A
B

B) DE ALTURA 4:

G
M

Se puede calcular el nmero de nodos de un rbol binario

completo de altura h aplicando la siguiente frmula:
NMERO DE NODOSABC = (2^h) - 1
Donde ABC significa rbol binario completo, y h la altura del rbol.
As, por ejemplo, un rbol binario completo de altura 5 tendr 31
nodos, de altura 9 tendr 511 nodos y un rbol de 17 tendr 131071
nodos.

Cabe aclarar que existen algunos autores que definen un rbol

binario completo de otra forma; y otros que utilizan el trmino lleno
para referirse a completos.

Representacin de rbol general a binario

1.

Deben enlazarse los hijos de cada nodo en forma

horizontal

2.

Debe enlazarse en forma vertical el nodo padre con el

hijo que se encuentra ms a la izquierda, adems debe
eliminarse el vnculo de ese padre con el resto de sus
hijos

3.

Debe rotarse el diagrama resultante aproximadamente

45 grados hacia la izquierda.

B
D

H
A

L
B

A
D
B
D
I

C
E

F
J

G
K

C
E

H
L

H
L

Representacin de rboles binarios en

memoria

Hay dos formas tradicionales de representarlos:



Por medio de datos tipo punteros tambin conocidos como

variables dinmicas o listas.
Por medio de arreglos.

Sin embargo la ms utilizada es la primera, puesto que

es la ms natural para tratar este tipo de estructuras.
Los nodos del rbol binario sern representados como
registros que contendrn como mnimo 3 campos: uno
almacenar la informacin del nodo y los dos restantes
se utilizarn apuntarn al subarbol izquierdo y derecho
del subarbol en cuestin.
34

rboles binarios

Cada nodo se representa grficamente de la siguiente

manera:
T=

Izq

Info

Der

La definicin de un rbol binario en lenguaje algortmico

es:
Enlace=^nodo
Nodo=registro
izq: tipo enlace
info: tipo de dato
der: tipo enlace
{fin de la definicion}
35

+
*
A

^
B

3.5

/
C

NIL

NIL

3.5

NIL

NIL

NIL
D

NIL

NIL NIL

NIL

NIL

Operaciones en rboles binarios

Una de las operaciones bsicas es la creacin del

mismo en memoria.
Otras operaciones:





Recorrer todos los nodos

Insertar un nuevo nodo
Eliminar alguno de los existentes
Buscar un valor determinado

A continuacin se presentar el algoritmo de creacin de

un rbol

37

Crea_arbol(NODO)
1.
Leer informacion(Hacer NODO^.INFO
INFOR)
2.
Escribir existe nodo por izquierda?: 1(Si) 0(No)
3.
Leer respuesta (RESP)
4.
Si RESP es afirmativa entonces
CREA (OTRO)
{crear un nuevo nodo}
Hacer NODO ^.IZQ
OTRO
Regresar a Crea_arbol con NODO ^.IZQ
{llamada recursiva}
si no
Hacer NODO ^.IZQ NIL
6.
{fin condicional del paso 4}
7.
Escribir existe nodo derecha? : 1(Si) 0(No)
8.
Leer respuesta (RESP)
9.
Si respuesta es afirmativa entonces
CREA (OTRO)
{crear un nuevo nodo}
Hacer NODO ^.DER
OTRO
Regresar a Crea_arbol con NODO ^.DER
{llamada recursiva}
si no
Hacer NODO ^.DER NIL
10.
{fin condicional del paso 9}

Recorrido de un rbol binario

Una de las operaciones ms importantes, que lo que

hace es visitar los nodos del rbol en forma ordenada,
de tal forma que todos los nodos sean visitados una sola
vez.
Hay tres manera de recorrer un rbol : en inorden,
preorden y postorden:


INORDEN

Recorrer el subarbol izquierdo en inorden.

Examinar la raz.

Recorrer el subarbol derecho en inorden.

39

Recorrido de un rbol binario



PREORDEN

Examinar la raz.

Recorrer el subarbol izquierdo en preorden.

recorrer el subarbol derecho en preorden.

POSTORDEN

Recorrer el subarbol izquierdo en postorden.

Recorrer el subarbol derecho en postorden.

Examinar la raz.

40

Ejemplo de recorrido
A
B
D

C
E

PREORDEN:

ABDECFG

INORDEN:

DBEAFCG

POSORDEN:

DEBFGCA

G
+
^

*
A
PREORDEN:

+*AB^/CD3.5

INORDEN:

A*B+C/D^3.5

POSORDEN:

AB*CD/3.5^+

B
C

3.5

/
D

41

Ejemplo de recorrido
A
B

D
G

E
H

F
I

K
PREORDEN:

ABDGKCEHIFJ

INORDEN:

GKDBAHEICFJ

POSORDEN:

KGDBHIEJFCA

Recorrido Preorden
PREORDEN(NODO).
1.
Si NODO NIL entonces
visitar el NODO {escribir NODO^.INFO}
regresar a PREORDEN con NODO^.IZQ
{llamada recursiva a PREORDEN con la
rama izquierda del nodo}
regresar a PREORDEN con NODO^.DER
{llamada recursiva a PREORDEN con la
rama derecha del nodo}
2.
{Fin condicional del paso 1}

Recorrido Inorden
INORDEN(NODO).
1.
Si NODO NIL entonces

2.

regresar a INORDEN con NODO^.IZQ

{llamada recursiva a INORDEN con la rama
izquierda del nodo}
visitar el NODO {escribir NODO^.INFO}
regresar a INORDEN con NODO^.DER
{llamada recursiva a INORDEN con la rama
derecha del nodo}
{Fin condicional del paso 1}

Recorrido Postorden
POSTORDEN(NODO).
1.
Si NODO NIL entonces
regresar a POSTORDEN con NODO^.IZQ
{llamada recursiva a POSTORDEN con la rama
izquierda del nodo}
regresar a POSTORDEN con NODO^.DER
{llamada recursiva a POSTORDEN con la rama
derecha del nodo}
visitar el NODO {escribir NODO^.INFO}
2.
{Fin condicional del paso 1}

rboles Binarios de
Bsqueda

46

rbol binario de bsqueda

Este tipo de rbol permite almacenar informacin

ordenada.

Reglas a cumplir:



Cada nodo del rbol puede tener 0, 1 2 hijos.

Los descendientes izquierdos deben tener un valor menor al
padre.
Los descendientes derechos deben tener un valor mayor al
padre.

47

Ejemplos de ABB
21

30
33

13

18

25

36

32
40

15

33

21

41
43

Por qu no son ABB?

21

5
33

13

17

18
15

25

1
22

2
40

Por qu no son ABB?

21

5
33

13

17

18
15

25

1
22

2
40

Implementacin de un ABB
struct nodo
{
int llave;
struct nodo *izq;
struct nodo *der;
};
typedef struct nodo *ABBTree;

51

Insertar en un ABB
void insertar(ABBTree &arbol, int dato)
{
if (arbol==NULL)
{
arbol=(ABBTree)malloc(sizeof(struct nodo));
arbol->izq=NULL;
arbol->der=NULL;
arbol->llave=dato;
}
else
{
if (dato>arbol->llave)
{
insertar(arbol->der,dato);
}
else
{
insertar(arbol->izq,dato);

52

else
{
insertar(arbol->izq,dato);
}
}
}

Reportar

void reportar(ABBTree abb, int h)

{
if(abb!=NULL)
{
printf("%i h=%i \n",abb->llave, h);
reportar(abb->izq,h+1);
reportar(abb->der,h+1);
}
}
53

Recorridos
void recorrerEnOrden(ABBTree abb)
{
if(abb!=NULL)
{
recorrerEnOrden(abb->izq);
printf("%i \n",abb->llave);
recorrerEnOrden(abb->der);
}
}

54

Recorridos
void recorrerPreOrden(ABBTree abb)
{
if(abb!=NULL)
{
printf("%i \n",abb->llave);
recorrerEnOrden(abb->izq);
recorrerEnOrden(abb->der);
}
}

55

Recorridos
void recorrerPostOrden(ABBTree abb)
{
if(abb!=NULL)
{
recorrerEnOrden(abb->izq);
recorrerEnOrden(abb->der);
printf("%i \n",abb->llave);
}
}

56

Buscar
int buscar(ABBTree abb, int dato)
{
int resp=0;
if (abb==NULL)
{
resp=0;
}
else
{
if(abb->llave==dato)
{
resp=1;
}

else if (abb->llave<dato)
{
resp=buscar(abb->der,dato);
}
else
{
resp=buscar(abb->izq,dato);
}
}
return resp;
}

57