Tema 5 - Arboles

1

Estructura de Datos 1 ETIS 1

TEMA 5. TEMA 5. RBOLES (I)RBOLES (I)


ndice1. Concepto de rbol2. rboles binarios

1. Especificacin informal del TAD rbol binario2. Implementacin del TAD rbol binario3. Recorrido de un rbol binario4. rboles de expresin5. rboles hilvanados o enhebrados6. rboles parcialmente ordenados (Montculos)7. rboles binarios de bsqueda

2


Estructuras de datos no lineales: Cada elemento puede tener varios anteriores y/o siguientes

Ejemplos de rbol: rboles gramaticales para analizar oraciones rboles genealgicos Estructura jerrquica de una organizacin Organizacin de ficheros en directorios/carpetas segn una

estructura en rbol Desarrollo de algoritmos Recuperacin de informacin


1. Concepto de rbol

Definicin: Estructura de datos no lineal, con una organizacin

jerrquica y elementos homogneos donde cada elemento puede tener varios elementos sucesores, pero un nico elemento antecesor

3


1. Concepto de rbol Conceptos:

Nodo Cada uno de los componentes o elementos del rbol (1.1, 1.2, , 2.1, ,

3.3) Ascendiente

Un nodo N1 es ascendiente de N2 si est en un nivel superior dentro de la estructura jerrquica del rbol. (1.3 es ascendiente de los nodos 1.4, 1.5, 1.6 y 1.7)

Descendiente: Un nodo N1 es descendiente de N2 si est en un nivel inferior dentro de la

estructura jerrquica del rbol. (3.3 es descendiente de 3.1 y 3.2)



Nodo Raz Nodo inicial del rbol. Se encuentra en el nivel superior de la estructura jerrquica

del rbol (nivel 1). Es el nico que no tiene padre. (1.1, 2.1, 3.1) Nodo Hoja

Nodo terminal del rbol. Son todos aquellos nodos que no tienen descendientes y se encuentran en los niveles ms bajos de la estructura jerrquica del rbol, aunque pueden estar en distintos niveles del mismo. (rbol 1: 1.2, 1.5, 1.6 y 1.7)

Subrbol: Subconjunto de nodos de un rbol que a su vez tienen estructura de rbol. El rbol 1

tiene varios subrboles, por ejemplo: desde el nodo 1.3 y todos sus descendientes; desde el nodo 1.4. El rbol 2 no tiene ningn subrbol.

4



Nodo padre: Es el nodo ascendiente de sus subrboles. En un rbol cada nodo slo puede tener

un padre, excepto el nodo raz, que es el nico que no tiene padre. Son nodos padre:

1.1 es padre de 1.2 y 1.3, siendo estos nodos hijos 1.3 es padre de 1.4, 1.5 y 1.6, siendo estos nodos hijos 1.4 es padre de 1.7, siendo este nodo hijo 3.1 es padre de 3.2 y este a su vez es padre de 3.3

Nodo hijo: Es el nodo descendiente de otro nodo. En un rbol cada nodo puede tener varios

hijos. Nodos hermanos:

Dos nodos son hermanos si tienen el mismo padre. (1.2 y 1.3; 1.4, 1.5 y 1.6)



Nodo interno: Es todo nodo que no es ni nodo raz ni nodo hoja. Por ejemplo, 1.3, 1.4 y 3.2

Camino: Secuencia de nodos del rbol donde se cumple que cualquier par de nodos

consecutivos son padre e hijo. (1.3 1.4; 1.1 1.3 1.4) Longitud del camino:

Es el nmero de nodos menos 1 (r-1). Si r>0, se dice que el camino es propio. longitud(1.3 1.4)=1; longitud(1.1 1.3 1.4)=2

Rama: Cualquier camino desde el nodo raz del rbol hasta un nodo hoja. (1.1 1.2;

1.1 1.3 1.6; 3.1 3.2 3.3)

5



Nivel (profundidad): De un nodo: Nmero de nodos que tiene el camino desde la raz a dicho

nodo. nivel(1.3)=2; nivel(1.7)=4; nivel(2.1)=1 Grado:

De un nodo: es el nmero de descendientes directos de dicho nodo o, lo que es lo mismo, el nmero de hijos que tiene dicho nodo. grado(1.3)=3; grado(2.1)=0; grado(3.2)=1

De un rbol: mximo grado de sus nodos. grado(rbol 1)=3; grado(rbol2)=0; grado(rbol 3)=1

Peso: Nmero de nodos terminales u hojas del rbol. peso(rbol1)=4;

peso(rbol2)=1; peso(rbol3)=1


1. Concepto de rbol

Conceptos: Altura:

Es el nivel ms alto del rbol (n de niveles del rbol). La altura es igual al nmero de nodos que tiene la rama ms larga del rbol. Altura(rbol 1)=4; Altura(rbol 2)=1; Altura(rbol 3)=3

6


2. rboles binarios

rbol binario: rbol donde cada nodo tiene como mximo grado 2


2. rboles binarios

rbol binario equilibrado: Cuando la diferencia de altura entre los subrboles de

cualquier nodo es como mximo una unidad. Cuando los subrboles de todos los nodos tienen todos la

misma altura se dice que est perfectamente equilibrado.

rbol binario lleno: Un rbol binario de altura h es lleno si tiene todas sus hojas a

nivel h y todos los nodos que estn en un nivel menor que htiene cada uno dos hijos.

7


2. rboles binarios rbol binario completo:

A de altura h es completo si est relleno a partir del nivel h-1, con el nivel h relleno de izquierda a derecha.

Ms formalmente: Todos los nodos de nivel h-2 y superiores tienen dos hijos cada uno. Cuando un nodo tiene un descendiente derecho de nivel h, todas las hojas

de su subrbol izquierdo estn a nivel h.

SI UN RBOL BINARIO ES LLENO, ES NECESARIAMENTE COMPLETO.

UN RBOL BINARIO COMPLETO ES EQUILIBRADO UN RBOL BINARIO LLENO ES TOTALMENTE EQUILIBRADO


2.1. Especificacin del TAD rbol Binarioabin=TAD con operaciones crea, esVacio, izq, der, info, insizq, insder, supizq, supder, modifica.

DESCRIPCIN: Los valores del TAD abin son rboles binarios donde cada nodo contiene un dato del tipo tipoelem. Los rboles son mutables: insizq, insder, supizq, supder y modifica aaden, eliminan y modifican respectivamente elementos de un rbol.

OPERACIONES:crea() devuelve (abin)

efecto: Devuelve el rbol binario vaco.

esVacio(A:abin) devuelve (booleano) efecto: Devuelve cierto si A es el rbol vaco, y falso en

caso contrario.

8


2.1. Especificacin del TAD rbol binarioizq(A:abin) devuelve (abin)

requerimientos: El rbol A es no vaco. efecto: Devuelve la posicin del nodo hijo izquierdo del subrbol A. Si

el nodo A no tiene hijo izquierdo, devuelve nulo.

der(A:abin) devuelve (abin) requerimientos: El rbol A es no vaco. efecto: Devuelve la posicin del nodo hijo derecho del nodo A. Si el

nodo A no tiene hijo derecho, devuelve nulo.

info(A:abin) devuelve (tipoelem) requerimientos: El rbol A es no vaco. efecto: Devuelve el contenido (etiqueta) del nodo A en el rbol.

insizq(A:abin; E:tipoelem) requerimientos: El rbol A es no vaco y nodonulo(izq(A))=cierto. modifica: A. efecto: Aade un nodo, con contenido E, como hijo izquierdo del

nodo A.


2.1. Especificacin del TAD rbol Binarioinsder(A:abin; E:tipoelem)

requerimientos: El rbol A es no vaco y nodonulo(der(A))=cierto modifica: A. efecto: Aade un nodo, con contenido E, como hijo derecho del nodo

A.supizq(A:abin)

requerimientos: El subrbol A es no vaco modifica: A. efecto: Suprime el hijo izquierdo del subrbol A y todos sus

descendientes.supder(A:abin)

requerimientos: El rbol A es no vaco. modifica: A. efecto: Suprime el hijo derecho del subrbol A y todos sus

descendientes.modifica(A:abin; E:tipoelem)

requerimientos: El rbol A es no vaco. modifica: A. efecto: Modifica el contenido del nodo A, cambindolo por el nuevo

contenido E.

9


2.1. Especificacin del TAD rbol binario


2.2. Implementacin del TAD rbol binario

Memoria dinmica (punteros) Memoria esttica (vectores) (simulacin de

memoria dinmica montn, como vimos en listas)

En cualquier caso, informacin a almacenar: Informacin con los datos necesarios. Enlace hacia el hijo izquierdo o raz del subrbol

izquierdo. Enlace hacia el hijo derecho o raz del subrbol

derecho.

10



Realizacin mediante memoria dinmica



11





12




2.3. Recorrido de un rbol binario Recorrido en anchura

Consiste en recorrer los distintos niveles y, dentro de cada nivel, los diferentes nodos de izquierda a derecha

Recorrido en profundidad Recorrido inorden:

IRD, normal de expresiones, orden simtrico u orden central Recorro subrbol izquierdo Visito nodo raz Recorro subrbol derecho

Recorrido preorden: RID, notacin prefija o notacin polaca

Visito nodo raz Recorro subrbol izquierdo Recorro subrbol derecho

Recorrido postorden: IDR o notacin postfija de expresiones o notacin polaca inversa

Recorro subrbol izquierdo Recorro subrbol derecho Visito nodo raz

13


2.3. Recorrido de un rbol binario

Simulacin recorrido en profundidad:http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BTree.html



DD-B

D-B-GD-B-G-E

D-B-G-E-A

D-B-G-E-A-F

D-B-G-E-A-F-C

Recorrido en profundidad recursivo:

14




A

A-B

A-B-D

A-B-D-E

A-B-D-E-G

A-B-D-E-G-C

A-B-D-E-G-C-F




D

D-GD-G-ED-G-E-B

D-G-E-B-F

D-G-E-B-F-C

D-G-E-B-F-C-A

15



Recorrido no recursivo: Uso de estructuras auxiliares para almacenar

punteros a los diversos nodos del rbol. Recorrido en profundidad

Pila donde almacenar punteros a los distintos nodos del rbol

Recorrido en anchura Se visitan los nodos por niveles Toma puntero raz y lo pone en la cola. A continuacin se repite: quitar primer elemento de la cola,

mostrar el contenido de dicho nodo y almacenar los punteros correspondientes a sus hijos izquierdo y derecho.

As, al recorrer los nodos de un nivel, mientras mostramos su contenido, almacenamos en la cola los punteros a todos los nodos del nivel siguiente.



Recorrido en profundidad no recursivoSe van colocando en la pila punteros a la razy los sucesivos hijos izquierdos de cada nodo

Recupera de la pila y escribe 1

Como (1) no tiene hijo derecho,recupera de la pila y escribe 4

El hijo derecho de (4) es (6).Pone en la pila el puntero al 6.

INORDEN

16



Recorrido en profundidad no recursivo

Recupera de la pila y escribe 6

Como (6) no tiene hijo derecho,recupera de la pila y escribe 8

El hijo derecho de (8) es (12).Pone en la pila el puntero al 12.

Se coloca en la pila el hijo izquierdo de (12)que ser el que se recupere a continuacin

. . .



Recorrido en profundidad no recursivo

17



Saco primer elemento (17) e imprimo

Inserto en cola posiciones de nodoizquierdo (8) y derecho (25) del elementoextrado

Creo la cola

Inserto posicin nodo raz (17) en cola

Recorrido en anchura







. . .


18





2.4. rboles de expresin

Los rboles binarios se utilizan para representar expresiones en memoria; esencialmente en compiladores de lenguajes de programacin.

Si suponemos operadores binarios: Los parntesis no se almacenan pero estn implicados en la

forma del rbol Todos los operandos letras estn almacenados en hojas. La raz de cada subrbol es un operador

Expresin (A + B) * C

Inorden (IRD): A + B * C

Preorden (RID): * + A B C (notacin prefija o polaca)

Postorden (IDR): A B + C * (notacin postfija o polaca inversa)

19


2.4. rboles de expresin

Ejemplos:

Expresin X * (Y / - Z)

Inorden (IRD): X * Y / - Z

Preorden (RID): * X / Y - Z

Postorden (IDR): X Y Z - / *

Expresin A + [B * -(C+D)]

Inorden (IRD): A + B * - C + D

Preorden (RID): + A * B - + C D

Postorden (IDR): A B C D + - * +

Expresin [A * (X + Y)] * C

Inorden (IRD): A * X + Y * C

Preorden (RID): * * A + X Y C

Postorden (IDR): A X Y + * C *


2.4. rboles de expresin Construccin a partir de una expresin en notacin

convencional (infija): Estructuras de datos auxiliares:

Pila para almacenar punteros a los nodos de un rbol Pila para retener los operadores temporalmente hasta que llegue

el momento de incorporarlos al rbol. Pasos a seguir:

Cuando se lee un operando se crea un rbol de un nodo y se mete el puntero a l en la pila de punteros.

Cuando se lee un operador se retiene en la pila de operadores. Los operadores se van poniendo en esta pila sucesivamente hasta encontrar uno con prioridad, en cuyo caso se sacan los operadores con menor prioridad y se coloca en ella este ltimo. Aunque el parntesis tiene la mayor prioridad slo se saca cuando aparece un parntesis derecho. Cuando se acaba la entrada tambin se saca lo que hubiera en la pila.

Al sacar un operador de su pila, hay que extraer dos punteros dela pila de punteros. Con estos tres elementos se forma un nuevo rbol. El puntero a este nuevo rbol se coloca en la pila de punteros.

El proceso termina cuando se acaba la entrada y la pila de operadores queda vaca.

20


2.4. rboles de expresin Construccin a partir de una expresin en notacin convencional (infija):

4 + 5 ^( 2 * 3 ) + 8

2: El ) saca los operadoresde la pila hasta el (

1 3: El + saca de la pila todos losoperadores con mayor o igual prioridadque l y a continuacin se coloca l

4 5


2.5. rbol hilvanado o enhebrado Los nodos hojas y los nodos con un solo hijo tienen

enlaces vacos Memoria esttica (arrays): muchas componentes del vector

tendrn valor -1 (Nulo) Memoria dinmica: muchos punteros a NULL

Si un rbol tiene n nodos, existen 2n enlaces, donde n+1 son enlaces vacos

Perlis y Thorton: uso de estos enlaces para direccionarotros nodos dentro del propio rbol (recorridositerativos ms eficientes).

Estos enlaces que cumplen una funcin nueva y especial se llaman HILVANES.

21


2.5. rbol hilvanado o enhebrado

Estos enlaces que cumplen una funcin nueva y especial se llaman HILVANES. Cuando un nodo tiene un hijo derecho vaco, este enlace ser

un hilvn que apuntar al nodo siguiente segn el recorrido que se est realizando sobre el rbol, por ejemplo inorden.

Cuando un nodo tiene un hijo izquierdo vaco, este ser un hilvn que apuntar al nodo anterior, tambin dentro del recorrido que se est realizando, por ejemplo inorden.


2.5. rbol hilvanado o enhebrado Diferenciar entre un enlace normal y un hilvn:

Operacin esHijoIzq() devuelve TRUE si el hijo izquierdo del rbol A es no vaco, y FALSE si se trata de un hilvn.

Operacin esHijoDer() Cambio en la definicin del tipo de nodo, aadiendo dos

campos para indicar si los hijos son subrboles o hilvanes

De esta forma las operaciones aadidas slo son una consulta a dichos campos del nodo.

22


2.5. rbol hilvanado o enhebrado Creacin de un rbol hilvanado:

Modificar procedimientos insizq() e insder() Hay que modificar ms procedimientos: suprimir

insizq(P,D)

insder(P,E)


2.5. rbol hilvanado o enhebrado

Ventaja principal rboles hilvanados: Permitir el recorrido de los rboles de forma iterativa sin

utilizar pilas. Determinacin del nodo siguiente en inorden iterativo:

Si el hijo derecho es un hilvn, entonces nos seala el nodo deseado.

Si tiene hijo derecho, entonces bajamos por todos los sucesivos hijos izquierdos hasta encontrar uno que no tenga hijo izquierdo.

23


2.5. rbol hilvanado o enhebrado Recorrido inorden iterativo:

Situarse en el nodo ms a la izquierda del rbol, bajando por los hijos izquierdos mientras se pueda.

Mientras que el rbol no sea vaco, se procesa el nodo en el que se est y se determina cul es el nodo siguiente aplicando nodoSiguiente().


2.6. Montculos

Montculo binario: Es una estructura de datos simple que da soporte eficiente a

las operaciones del TAD cola de prioridad. Aplicaciones: todas las de cola de prioridad: planificacin de

trabajos en sistema multiusuario, colas de impresin, criptografa

Hay que buscar el elemento con mayor prioridad (valor clave mnimo): Siempre ser la raz

24


2.6. Montculos Definicin:

Un montculo binario (o simplemente montculo) es un rbol binario semicompleto en el que el valor de clave almacenado en cualquier nodo es que los valores de clave de sus hijos.

rbol parcialmente ordenado: cumple la propiedad de ordenacin anterior.

rbol semicompleto: en el nivel ms bajo pueden faltar algunos nodos, pero stos han de ser los de ms a la derecha posible.


2.6. Montculos Montculo = rbol binario semicompleto

Esto hace que sea fcil representarlo en una estructura de datos con disposicin secuencial (array), donde el nmero de nodo ser el ndice del array.

A[1]: raz Hijo izquierdo de A[i]: A[2i] Hijo derecho de A[i]: A[2i+1] Padre de A[i]: A[i/2], i>1

Ventajas: se aprovecha la posibilidad de operar aritmticamente con los ndices del vector para obtener, en tiempos de ejecucin constantes, las posiciones de los padres e hijos izquierdo y derecho. Es ms eficiente en espacio que la representacin enlazada pues no hay necesidad de almacenar punteros.

Desventaja: se requiere conocer a priori el nmero mximo de elementos en el rbol

25


2.6. Montculos

Implementacin de montculo=cola de prioridad Modificamos el tipo de datos Modificamos procedimientos insertar/suprimir


2.6. Montculos

Mantenimiento de montculos: insertar Asegurar que el montculo mantiene su forma y el orden

parcial.

Se inserta nuevo nodo comohoja extremo derecho del ltimonivel del rbol, iniciando unnuevo nivel si es necesario

clave (nuevo) < clave (padre) intercambio

clave (nuevo) < clave (padre) intercambio

26


2.6. Montculos

Insertar


2.6. Montculos Mantenimiento de montculos: suprimir

Asegurar que el montculo mantiene su forma y el orden parcial.

1. Devolvemos elemento raz (valor 2)2. Muevo elemento en hoja extremo

derecha (valor 15) a raz y elimino posicin extremo derecha.

clave (nuevo) > clave (hijos) Intercambio con hijo menor

clave (nuevo) > clave (hijos) Intercambio con hijo menor

27


2.6. Montculos

Suprimir


2.7. rboles binarios de bsqueda (ABB)

Definicin ABB: Dado un nodo, todos los datos del subrbol

izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subrbol derecho son mayores que los datos del nodo.

Ventaja: El coste de buscar un dato es menor, pues los datos estn ordenados.

Recorrido inorden: Datos de menor a mayor: 4 30 41 55 75 85

28



Operaciones en ABB: Tiempo de ejecucin promedio O(logn) para un

conjunto de n elementos: inserta: inserta un elemento en el rbol suprime: elimina un elemento del rbol esMiembro: para saber si un elemento est en el rbol min/max: devuelve el elemento mnimo/mximo de un

rbol suprime_min/suprime_max: elimina el elemento

mnimo/mximo de un rbol Imponer condiciones de balanceado (rboles AVL, rboles

B, etc.) sobre los ABB para que se mantenga O(logn). Si no balanceamos, tiempo de ejecucin O(n) en el peor caso.


2.7. rboles binarios de bsqueda (ABB) Especificacin informal del ABB:

abb=TAD con operaciones crea, esVacio, inserta, suprime, esMiembro

DESCRIPCIN: Los valores del TAD abb son rboles binarios de bsqueda de

elementos del tipo tipoelem. Los ABB son mutables: inserta y suprime aaden y eliminan elementos del rbol respectivamente.

OPERACIONES: crea() devuelve (abb)

efecto: devuelve el rbol binario de bsqueda vaco

esVacio(A:abb) devuelve (booleano) efecto: devuelve cierto si A es el rbol vaco y falso en caso contrario

inserta(A:abb;E:tipoelem) modifica: A efecto: aade el elemento E al rbol binario de bsqueda A.

suprime(A:abb;E:tipoelem) modifica: A efecto: suprime el elemento E, si existe, en el rbol binario de bsqueda A.

esMiembro(A:abb;E:tipoelem) devuelve (booleano) efecto: devuelve cierto si E es un elemento del rbol binario de bsqueda A, y

falso en caso contrario.

29



Mdulo de definicin del ABB (sin tratamiento de errores)



Mdulo de implementacin del ABB

30


2.7. rboles binarios de bsqueda (ABB) Insercin:

1. Asignar memoria para un nuevo nodo2. Buscar en el rbol para encontrar la posicin de insercin del nuevo

nodo, que se colocar como nodo hoja:1. Si datoraz, insertamos por subrbol derecho

3. Enlazar el nuevo nodo al rbol.


2.7. rboles binarios de bsqueda (ABB)Eliminacin:1. Buscamos posicin nodo a eliminar2. Reajustamos los punteros:

a) Si el nodo es hoja, se suprime del rbolb) Si el nodo tiene un nico hijo, sustituimos el nodo por el hijoc) Si el nodo tiene dos hijos, buscamos el menor de los descendientes del hijo derecho*, y

sustituimos el nodo por este descendiente.

*O el mayor de los descendientes del hijo izquierdo

31


2.7. rboles binarios de bsqueda (ABB)Eliminacin

a) Nodo hoja: lo suprimo del rbol

b) Slo tiene hijo izquierdo:se sustituye por l

c) Tiene los dos hijos:suprimo el mnimo delsubrbol derecho

b) Slo tiene hijo derecho:se sustituye por l

Documents

Tema 5 - Arboles