Upload
wylemvelasquezz
View
221
Download
0
Embed Size (px)
Citation preview
7/23/2019 FPII04 Estructuras No Lineales de Datos
1/65
Lus Rodrguez Baena ([email protected])
Universidad Pontificia de Salamanca (campus Madrid)Escuela Superior de Ingeniera y Arquitectura
Fundamentos de Programacin II
Tema 4. Estructuras no linealesde datos: rboles
7/23/2019 FPII04 Estructuras No Lineales de Datos
2/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
2
Estructuras de datos no lineales
En una estructura lineal, cada elemento slo puede ir
enlazado al siguiente o al anterior.A las estructuras de datos no lineales se les llama
tambin estructuras de datos multienlazadas. Cada elemento puede estar enlazado a cualquier otro
componentes. Se trata de estructuras de datos en las que cada
elemento puede tener varios sucesores y/o varios
predecesores. rboles. Grafos.
7/23/2019 FPII04 Estructuras No Lineales de Datos
3/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
3
Estructuras de datos no lineales (II)
rboles.
Cada elemento slo puede estar enlazado con su predecesor ysus sucesores. Puede tener varios sucesores.
Grafos.
Cada elemento puede estar enlazado a cualquier otro.A
B C D
E F
JI K
G H
A
B
C
D
E
7/23/2019 FPII04 Estructuras No Lineales de Datos
4/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
4
rboles
Estructura no lineal jerrquica en la que cadaelemento tiene un nico antecesor y puede tenervarios sucesores.
Existe un nico camino entre el primer nodo de laestructura y cualquier otro nodo.
Se utilizan para representar todo tipo dejerarquas: rbol genealgico, taxonomas,diagramas de organizacin, etc.
En informtica se utilizan para aplicaciones
algortmicas (ordenacin, bsqueda), compilacin(rboles sintcticos, rboles de expresiones), etc. Formalmente, un rbol A es un conjunto finito de
elementos con 0 o ms nodos de forma que: Se trata de una estructura vaca. Si tiene componentes, los nodos restantes se
dividen en uno o ms conjuntos disjuntos cada unode los cuales es a su vez un rbol. A estos nodos seles llama subrboles del raz.
Se trata de una estructura recursiva.
7/23/2019 FPII04 Estructuras No Lineales de Datos
5/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
5
Terminologa
Nodo: los vrtices o elementos de un rbol. Enlace/arco/arista: Conexin entre dos nodos
consecutivos. Los nodos pueden ser:
Nodo raz: nodo superior de la jerarqua. Nodo terminal u hoja: nodo que no contienen ningn subrbol. Nodos interiores: nodos con uno o ms subrboles; nodos que no
son hojas. Descendientes o hijos: cada uno de los subrboles de un nodo. Ascendiente, antecesor o padre: nodo de jerarqua superior a
uno dado. Nodos hermanos: nodos del mismo padre.
Bosque: coleccin de rboles.
7/23/2019 FPII04 Estructuras No Lineales de Datos
6/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
6
Terminologa (II)
Camino: enlace entre dos nodos. No existe un camino entre todos los
nodos. Rama: camino que termina en unahoja.
Grado de un nodo: nmero desubrboles que tiene.
Nivel de un nodo o longitud delcamino: nmero de arcos o enlacesque hay desde el nodo raz hasta unnodo dado.
Altura o profundidad de un rbol:nmero mximo de nodos de una
rama; el nivel ms alto de un rbolms uno. Peso de un rbol: nmero de nodos
terminales.
A
B C D
E F
JI K
G H
Nivel 0
Nivel 1
Nivel 2
Nivel 3
Altura del rbol = 4Peso del rbol = 7
7/23/2019 FPII04 Estructuras No Lineales de Datos
7/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
7
rboles binarios
Un rbol general sera un rbol en el que cada nodo puede tener unnmero ilimitado de subrboles.
Un rbol binario sera un conjunto de 0 o ms nodos en el cual existeun nodo raz y cada uno de los nodos, incluido el raz podrn tener 0, 1o dos subrboles: Subrbol izquierdo y subrbol derecho. Cada nodo es como mximo de grado 2.
Terminologa: rboles similares: rboles con la misma estructura. rboles equivalentes: rboles con la misma estructura y contienen la
misma informacin. rboles completos o rboles perfectos: todos los nodos, excepto las
hojas, tienen grado 2. Un rbol binario de nivel n tiene 2n-1 nodos.
rbol equilibrado: un rbol en el que las alturas de los dos subrboles decada uno de los nodos tiene como mximo una diferencia de una unidad.
rbol degenerado: todos sus nodos slo tienen un subrbol.
7/23/2019 FPII04 Estructuras No Lineales de Datos
8/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
8
rboles binarios (II)
7/23/2019 FPII04 Estructuras No Lineales de Datos
9/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
9
Implementaciones de rboles generales
Cada nodo debera tener un nmero indeterminado de
enlaces que apunten a cada uno de sus hijos. Problema cuntos enlaces reservamos? Se pueden implementar como un array con indicaciones
al padre de cada nodo.
7/23/2019 FPII04 Estructuras No Lineales de Datos
10/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
10
Implementaciones de rboles generales (II)
Implementacin mediante una lista de hijos.
En un ndice aparecen todos los nodos. Por cada nodo existe una lista de hijos.
7/23/2019 FPII04 Estructuras No Lineales de Datos
11/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
11
Implementaciones de rboles generales (III)
Implementacin mediante una lista listas.
Cada nodo apunta a una lista enlazada. En esa lista, cada nodo apunta a un nodo hijo.
7/23/2019 FPII04 Estructuras No Lineales de Datos
12/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
12
Conversin de rboles generales en
binarios Los rboles generales son ms difciles de implementar
que los rboles binarios. En este curso se implementarn rboles binarios. De cualquier forma, un rbol general se puede convertir
a binario. La raz del rbol binario ser la raz del rbol general. Se enlaza el hijo situado ms a la izquierda del nodo raz del
rbol general como hijo izquierdo del nodo raz en el rbolbinario.
Se enlazan todos los hermanos como hijos derechos en el rbolbinario.
El proceso se repite con cada nodo.
7/23/2019 FPII04 Estructuras No Lineales de Datos
13/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
13
Conversin de rboles generales en
binarios (II)
A
B
D
E
FI
J
K
G
H
C
7/23/2019 FPII04 Estructuras No Lineales de Datos
14/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
14
Implementacin de rboles binarios
Se pueden implementar como un array de elementos del tipo basedel rbol.
El primer elemento se corresponde al nivel 0 del rbol. Los dos siguientes elemento se corresponden al nivel 1 del rbol. Los cuatro siguientes elementos se corresponden al nivel 2 del rbol. Los ocho siguientes elementos se corresponden al nivel 3 del rbol. Los diecisis siguientes elementos se corresponden al nivel 4 del rbol.
A
B
FD
HG I J
E
C
FEDCBA JIHG
Nivel 0 Nivel 1 Nivel 2 Nivel 3
7/23/2019 FPII04 Estructuras No Lineales de Datos
15/65
7/23/2019 FPII04 Estructuras No Lineales de Datos
16/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
16
Implementacin de rboles binarios (III)
El almacenamiento ser un array de nodos. El tipo rbol ser un ndice de array.
Cada nodo tendr los campos raz de tipo TipoElemento, hizq de tiporbol y hder de tipo rbol.
Los punteros hizq e hder seran ndices del array. Un valor -1 en el hijo derecho podra corresponder a un elemento que no contiene un nodo
vlido.
constMaxArbol =
tipos
= TipoElemento
entero = rbol
registro = nodo
TipoElemento = raz
rbol = hizq, hderfin_registro
array[1..MaxArbol] de nodo = almacenamiento
var
almacenamiento : alm
rbol : a
7/23/2019 FPII04 Estructuras No Lineales de Datos
17/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
17
Implementacin de rboles binarios (IV)
Mediante estructuras dinmicas.
El rbol estara compuesto por una serie de nodos. Cada nodo contendra: El campo raz con la informacin del tipo base del rbol. Los punteros hizq e hder que seran punteros a nodo, es decir,
seran tambin rboles. Si alguno se esos hijos es un rbol vaco contendran un valor nulo.
El tipo de dato rbol sera un puntero a nodo. Un puntero a nodo indicara el nodo de inicio de la estructura, es
decir, la raz del rbol.
7/23/2019 FPII04 Estructuras No Lineales de Datos
18/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
18
Implementacin de rboles binarios (V)
tipos
= TipoElemento
puntero_a nodo = rbolregistro = nodo
TipoElemento = raz
rbol = hizq, hder
fin_registro
var
rbol : a
C
/ /
B
A
D E
/ /
F
/ /
G
/ /
rbolA
raz
hizq hder
nodo
7/23/2019 FPII04 Estructuras No Lineales de Datos
19/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
19
Recorridos en rboles binarios
En una estructura de datos lineal slo es posible un tipo derecorrido en dos sentidos distintos:
Del primero al ltimo o del ltimo al primero. Una estructura de datos no lineal se puede recorrer de
distintas maneras: Se realiza un recorrido por niveles, accediendo a los nodos
hermanos de cada nivel?
Una vez situados en un nodo, a qu hijo se accede primero? En que momento se accede a la informacin del nodo, antes o
despus de los hijos? En general existen dos grandes grupos de recorridos:
Recorridos en profundidad. Se recorren las ramas de un nodo dado. Recorridos en anchura.
Se accede a los nodos hermanos en cada uno de los niveles del rbol.
7/23/2019 FPII04 Estructuras No Lineales de Datos
20/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
20
Recorridos en rboles binariosRecorridos en profundidad
Tres tipos de recorridos dependiendo del orden en que
se acceda al subrbol izquierdo, al subrbol derecho o alnodo raz. En los tres recorridos se accede antes al hijo izquierdo que al
hijo derecho.
La variacin reside en el momento en que se recorrer lainformacin del nodo. Recorrido preorden u orden previo (RID, raz-hijo izquierdo-hijo
derecho). Recorrido inorden u orden simtrico (IRD, hijo izquierdo-raz-hijo
derecho). Recorrido postorden u orden posterior (IDR, hijo izquierdo- hijo
derecho-raz).
7/23/2019 FPII04 Estructuras No Lineales de Datos
21/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
21
Recorridos en rboles binariosRecorridos en profundidad (II)
Recorrido preorden. Por cada elemento no vaco:
Se accede primero al nodo raz. Se accede al hijo izquierdo en preorden. Se accede al hijo derecho en preorden. Para el siguiente rbol:
o M,F,C,A,E,H,P,R,Q,Z
Recorrido inorden. Por cada elemento no vaco:
Se accede al hijo izquierdo en inorden. Se accede primero al nodo raz. Se accede al hijo derecho en inorden. Para el siguiente rbol:
o A,C,E,F,H,M,P,Q,R,Z
Recorrido postorden.
Por cada elemento no vaco: Se accede al hijo izquierdo en postorden. Se accede al hijo derecho en postorden. Se accede primero al nodo raz. Para el siguiente rbol:
o A,E,C,H,F,Q,Z,R,P,M
7/23/2019 FPII04 Estructuras No Lineales de Datos
22/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
22
Recorridos en rboles binariosRecorrido preorden
Los tres recorridos tienen una definicin recursiva. En la definicin del recorrido, interviene el objeto definido.
Se procesa el nodo raz y se recorre el subrbol izquierdo en preorden, y despus el
subrbol derecho tambin en preorden.
procedimiento PreOrden(valor arbol: a)
inicio
si a nulo entonces
//Procesar elemento raz
escribir(a.raz)PreOrden(a.hizq)
PreOrden(a.hder)
fin_si
fin_procedimiento
Recorrido preorden: M F C A E H P R Q Z
P/
F
M
C H
/ /
A
/ /
E
/ /
rbol
R
Q
/ /
Z
/ /
7/23/2019 FPII04 Estructuras No Lineales de Datos
23/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
23
Recorridos en rboles binariosRecorrido inorden
Se recorre el subrbol izquierdo en inorden, se procesa el raz ydespus el subrbol derecho tambin en inorden.
procedimiento InOrden(valor arbol: a)
inicio
si a nulo entonces
InOrden(a.hizq)//Procesar elemento raz
escribir(a.raz)
InOrden(a.hder)
fin_si
fin_procedimiento
Recorrido inorden: A C E F H M P Q R Z
P
/
F
M
C H
/ /
A
/ /
E
/ /
rbol
R
Q
/ /
Z
/ /
7/23/2019 FPII04 Estructuras No Lineales de Datos
24/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
24
Recorridos en rboles binariosRecorrido postorden
Se procesa se recorre el subrbol izquierdo en postorden, despus elsubrbol derecho tambin en postorden y por ltimo se procesa el nodo
riz.procedimiento PostOrden(valor arbol: a)
inicio
si a nulo entonces
PostOrden(a.hizq)
PostOrden(a.hder)
//Procesar elemento raz
escribir(a.raz)
fin_si
fin_procedimiento
Recorrido postorden: A E C H F Q Z R P M
P
/
F
M
C H
/ /
A
/ /
E
/ /
rbol
R
Q
/ /
Z
/ /
7/23/2019 FPII04 Estructuras No Lineales de Datos
25/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
25
Recorrido en anchura
El recorrido se hace por niveles a partir del nivel 0. Por cada nivel se recorren los nodos hermanos de izquierda a derecha.
Recorrido en anchura: M F P C H R A E Q Z
P
/
F
M
C H
/ /
A
/ /
E
/ /
rbol
R
Q
/ /
Z
/ /
7/23/2019 FPII04 Estructuras No Lineales de Datos
26/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
26
Recorrido en anchura (II)
Para su implementacin hay que procesar el nodo raz yrecordar las direcciones de sus hijos izquierdo y derecho para
acceder a ellos en el mismo orden en que se encuentran. Hay que repetir el proceso por cada nodo, recordando las
direcciones de sus hijos izquierdo y derecho y recuperarlas enel mismo orden en que han entrado.
Existe una estructura de datos que extrae los elementos en elmismo orden en que entran: la cola. Se utiliza una cola que almacene rboles (punteros a nodos). Se introduce la direccin del nodo raz en la cola.
Se extraen elementos de la cola y por cada elemento que se extraeque no sea un rbol vaco (un puntero nulo), se introducen lasdirecciones de sus hijos izquierdo y derecho.
El proceso termina cuando la cola est vaca.
7/23/2019 FPII04 Estructuras No Lineales de Datos
27/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
27
Recorrido en anchura (II)
procedimiento Anchura(valor rbol : a)
tipos
TipoElementoCola : rbol //La cola contiene punteros a nodo
var
cola : niveles
rbol : aux
inicio
ColaNueva(niveles)
CInsertar(niveles,a)repetir
Primero(niveles, aux)
CBorrar(niveles)
si aux nulo entonces
//Procesar riz
escribir(a.raz)
CInsertar(niveles, a.hizq)
CInsertar(niveles, a.hder)
fin_si
hasta_que EsColaVaca(niveles)
fin_procedimiento
7/23/2019 FPII04 Estructuras No Lineales de Datos
28/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
28
Aplicaciones de rboles
En una lista enlazada slo hay una forma de insertar o deeliminar un elemento:
Para insertar un elemento hay que colocarlo entre al anterior y elsiguiente.
Para eliminar un elemento, hay que hacer que el anterior apunte alsiguiente.
En un rbol, dependiendo de la aplicacin que se haga delrbol esas operaciones pueden cambiar: Si se inserta un elemento se inserta como hijo izquierdo o como
hijo derecho? qu se hace con los hijos del nodo anterior? Si se elimina un elemento, qu se hace con los hijos de ese nodo?
Algunas aplicaciones de rboles binarios: rbol de expresiones. rbol binario de bsqueda.
7/23/2019 FPII04 Estructuras No Lineales de Datos
29/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
29
rboles de expresiones
Representacin de una expresin. Los nodos internos son los operadores y las hojas los operandos.
Si hay varias operaciones, las de menos prioridad ocupan los niveles msaltos. Sea la expresin: (a+b) * (c/(d+f))
Expresin infija (recorrido inorden): a+b*c/d+fExpresin prefija (recorrido preorden):
*+ab/c+dfExpresin postfija (recorrido postorden): ab+cdf+/*
/+
*
a/ /
b/ /
rbol
+
d
/ /
f
/ /
c/ /
7/23/2019 FPII04 Estructuras No Lineales de Datos
30/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
30
rbol binario de bsqueda
Una de las aplicaciones ms importantes de rboles sebasa en su capacidad para ordenar y buscar elementos.
Los rboles binarios de bsqueda se utilizan para esasaplicaciones.
Se trata de un rbol en el que se colocan los elementos
de una lista segn un determinado criterio: El primer elemento de la lista es el raz. Los siguientes elementos se colocan de forma que los elementos
menores queden en el subrbol izquierdo y los mayores en elderecho.
7/23/2019 FPII04 Estructuras No Lineales de Datos
31/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
31
rbol binario de bsqueda (II)
Dada la siguiente lista: M D P V C A F R Y N S, el rbol de bsquedaresultante sera:
M
D P
C F V
R YA
N
S
Obsrvese que: El recorrido inorden del rbol
devolvera los elementos en ordenascendente. Para buscar un elemento, habra
que comparar el elemento con elraz y, dependiendo de que el
elemento sea mayor o menor, ir alsubrbol derecho o izquierdorespectivamente.
B d b l bi i d
7/23/2019 FPII04 Estructuras No Lineales de Datos
32/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
32
Bsqueda en rboles binarios debsqueda
Para buscar un elemento hay que compararlo con el que ocupa la razdel rbol. Si es igual, ya se ha encontrado. Si es menor, se busca en el subrbol izquierdo. Si es mayor, se busca en el subrbol derecho.
Admite una definicin recursiva: Casos base:
Si el rbol es nulo, el elemento no est.
Si se trata del elemento raz, el elemento ya se ha encontrado. Casos generales. Si el elemento es menor que el raz hay que hacer la bsqueda en el subrbol izquierdo
(llamada recursiva). Si el elemento es mayor, hay que hacer la bsqueda en el subrbol derecho (llamada
recursiva).
La funcin de bsqueda devolver un rbol, es decir un puntero anodo. Si el elemento est en el rbol, ser la direccin del nodo dnde se encuentra el
elemento buscado. Si el elemento no est en el rbol, devolver un puntero nulo.
7/23/2019 FPII04 Estructuras No Lineales de Datos
33/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
33
Bsqueda iterativa
rbol : funcin Buscar(valor rbol : a; valor TipoElemento : e)
var
lgico : encontrado
inicio
encontrado falsomientras no encontrado y (a nulo) hacer
si a.raz = e entonces
encontrado verdad
si_no
si a.raz > e entonces
a a.hizqsi_no
a a.hder
fin_si
fin_si
fin_mientras
siencontrado
entoncesdevolver(a)
si_no
devolver(nulo)
fin_si
fin_funcin
7/23/2019 FPII04 Estructuras No Lineales de Datos
34/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
34
Bsqueda recursiva
Funciona de forma similar a la bsqueda binaria recursiva. Si el rbol el nulo, no se encuentra y devuelve nulo. Si el elemento raz coincide, devuelve el valor de a. Si el elemento raz es mayor, se busca en el subrbol izquierdo. Si el elemento raz es menor, se busca en el subrbol derecho.
rbol : funcin Buscar(valor rbol : a; valor TipoElemento : e)
inicio
si a = nulo entonces
devolver(nulo)si_no
si a.raz = e entonces
devolver(a)
si_no
si a.raz > e entonces
Buscar(a.hizq,e)
si_noBuscar(a.hder,e)
fin_si
fin_si
fin_si
fin_funcin
7/23/2019 FPII04 Estructuras No Lineales de Datos
35/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
35
Insercin en un rbol de bsqueda
En un rbol binario de bsqueda, todos los elementos seinsertan como hojas.
Para insertar un elemento, hay que desplazarse por lossbrboles izquierdo o derecho, dependiendo del valordel nodo, hasta encontrar un rbol nulo.
Segn el valor del ltimo elemento raz, insertar comoraz del rbol, como hijo derecho del anterior o comohijo izquierdo del anterior.
7/23/2019 FPII04 Estructuras No Lineales de Datos
36/65
7/23/2019 FPII04 Estructuras No Lineales de Datos
37/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
37
Insercin en un rbol de bsqueda (III)
procedimiento Insertar(ref rbol :a ; valor TipoElemento : e)
var
rbol : act, ant, aux
inicio
//Inicializar punterosact a
ant nulo
//Reservar espacio para un nuevo nodo
//Siempre se inserta el elemento
reservar(aux)
aux.raz eaux.hizq nulo
aux.hder nulo
//Buscar la posicin del nuevo elemento
mientras act nulo hacer
ant act
si act.raz > e thenact act.hizq
si_no
act act.hder
fin_si
fin_mientras
//Si es el primer nodosi ant = nulo entonces
a aux
si_no
//Es hijo izq del anterior
si ant.raz > e entonces
ant.hizq auxsi_no
ant.hder aux
fin_si
fin_si
fin_procedimiento
Insercin en un rbol de bsqueda
7/23/2019 FPII04 Estructuras No Lineales de Datos
38/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
38
Insercin en un rbol de bsquedaVersin recursiva
Es posible hacer una definicin recursiva de la insercinen un rbol binario de bsqueda. Caso base.
Si el rbol es nulo.o Se inserta un nuevo nodo colgando del rbol.
Caso general. Si el rbol no est vaco.
o Si el elemento a insertar es menor que el elemento raz, se inserta en elsubrbol izquierdo.
o Si el elemento a insertar es mayor que el elemento raz, se inserta en el
subrbol derecho.
Insercin en un rbol de bsqueda
7/23/2019 FPII04 Estructuras No Lineales de Datos
39/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
39
Insercin en un rbol de bsquedaVersin recursiva (II)
Versin recursiva.
procedimiento Insertar(ref rbol :a ; valor TipoElemento : e)inicio
si a = nulo
//Hemos llegado a una hoja. Insertamos
reservar(a)
a.raz e
a.hizq nulo
a.hder nulo
si_no
si a.raz > e then
Insertar(a.hizq,e)
si_no
Insertar(a.hder,e)
fin_si
fin_si
fin_mientras
Insercin en un rbol de bsqueda
7/23/2019 FPII04 Estructuras No Lineales de Datos
40/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
40
Insercin en un rbol de bsquedaVersin recursiva (III)
7/23/2019 FPII04 Estructuras No Lineales de Datos
41/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
41
Borrado de un nodo
Al algoritmo de borrado de un nodo debemos suministrarle ladireccin del nodo a borrar (act) y la direccin del nodo anterior
(ant). Si queremos borrar el elemento raz, ant ser nulo. Dependiendo del valor del nodo anterior habr que tomar distintas
decisiones.
Caso 1: Borrar una hoja. Caso 1a: borrar el ltimo nodo de un rbol de un nico elemento.
El rbol toma un valor nulo.
M
/ /
a
actant
M
/ /
a
actant
a nulo
7/23/2019 FPII04 Estructuras No Lineales de Datos
42/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
42
Borrado de un nodo (II)
Caso 1: Borrar una hoja. Caso 1b: El nodo a borrar es hijo izquierdo del anterior.
El hijo izquierdo del anterior ser nulo.
D
M
C
/ /
F
/ /
a
act
ant
D
/
M
C
/ /
F
/ /
a
act
ant
ant.hizq nulo
B d d d (III)
7/23/2019 FPII04 Estructuras No Lineales de Datos
43/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
43
Borrado de un nodo (III)
Caso 1: Borrar una hoja. Caso 1c: El nodo a borrar es hijo derecho del anterior.
El hijo derecho del anterior ser nulo.
ant.hder nulo
D
M
C
/ /
F
/ /
a
act
ant D
/
M
C
/ /
F
/ /
a
act
ant
B d d d (IV)
7/23/2019 FPII04 Estructuras No Lineales de Datos
44/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
44
Borrado de un nodo (IV)
Caso 2: Borrar un nodo con un solo hijo. Caso 2.1: Slo tiene hijo derecho
Caso 2.1.a: es el nodo raz.o El nodo raz apuntar al hijo derecho del anterior.
a a.hder
P
M
/
Q
/ /
a
R
/ /
act
ant
P
M
/
Q
/ /
a
R
/ /
act
ant
B d d d (V)
7/23/2019 FPII04 Estructuras No Lineales de Datos
45/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
45
Borrado de un nodo (V)
Caso 2: Borrar un nodo con un solo hijo. Caso 2.1: Slo tiene hijo derecho
Caso 2.1.b: es el hijo derecho del anterior.o El hijo derecho del anterior apuntar al hijo derecho del nodo a borrar.
ant.hder act.hder
P
M
V
/ /
a
/
Ract
Q
/ /
ant
P
M
R
/ /
a
/
Ract
Q
/ /
ant
B d d d (VI)
7/23/2019 FPII04 Estructuras No Lineales de Datos
46/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
46
Borrado de un nodo (VI)
Caso 2: Borrar un nodo con un solo hijo. Caso 2.1: Slo tiene hijo derecho
Caso 2.1.c: es el hijo izquierdo del anterior.o El hijo izquierdo del anterior apuntar al hijo derecho del nodo a borrar.
ant.hizq act.hder
D
/
M
E
/ /
F
a
G
/ /
act
ant
D
/
M
E
/ /
F
a
G
/ /
ant
Borrado de un nodo (VI)
7/23/2019 FPII04 Estructuras No Lineales de Datos
47/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
47
Borrado de un nodo (VI)
Caso 2: Borrar un nodo con un solo hijo. Caso 2.2: Slo tiene hijo izquierdo.
Igual que el caso 2.1, pero se apuntar al hijo izquierdo del actual. Caso 2.2.a: Es el nodo raz.
o a a.hizq
Caso 2.2.b: Es hijo derecho del anterioro ant.hder act.hizq
Caso 2.2.c: Es hijo izquierdo del anterioro ant.hizq act.hizq
Borrar un nodo (VII)
7/23/2019 FPII04 Estructuras No Lineales de Datos
48/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
48
Borrar un nodo (VII)
Caso 3: Borrar un nodo con dos hijos. En este caso no se borra el nodo act, sino que se sustituye su
valor por el mayor valor entre los situados a la izquierda (o elmenor entre los situados a la derecha). De esta forma se mantienen los elementos y la estructura del rbol
binario de bsqueda.
Lo que se borra es el nodo que contena el valor que se hasubido. Si el nodo situado inmediatamente a la izquierda es el mayor de
los menores, se modifica el hijo izquierdo del actual.
7/23/2019 FPII04 Estructuras No Lineales de Datos
49/65
Borrar un nodo (IX)
7/23/2019 FPII04 Estructuras No Lineales de Datos
50/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
50
Borrar un nodo (IX)
procedimiento Borrar(ref arbol : a; valor arbol : act,ant)
var
arbol : aux
inicio
// si borramos una hoja. Caso 1.si (act.hder = nulo) y (act .hizq = nulo) entonces
si ant = nulo entonces // es el ltimo nodo de un arbol
a nulo
si_no
si ant .hder = actentonces // es el subarbol derecho
ant .hder nulo
si_no
ant .hizq nulo
fin_si
fin_si
si_no
// si el nodo a borrar tiene dos hijos. Caso 3.
si (act .hder nulo) y (act .hizq nulo) entonces
// inicializa los puntero para buscar
// el valor a reemplazar
ant act
aux act .hizq
Borrar un nodo (X)
7/23/2019 FPII04 Estructuras No Lineales de Datos
51/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
51
Borrar un nodo (X)
// localiza el nodo que contiene el valor
// ms proximo al que se va a suprimir
mientras aux .hder nulo hacer
ant aux
aux aux.hderfin_mientras
// pone el valor reemplazado en el nodo
// cuyo valor se va a suprimir
act .raiz aux .raiz
// se suprime el nodo del que se ha tomado el valor *)
si ant = actentonces
ant.hizq aux.hizq
si_no
ant .hder aux.hizq
fin_si
act aux // para poder disponer del nodo
si_no
// Solo tiene un hijo. Caso 2.
// Se actualizan los punteros del nodo a borrar
// segn tenga un hijo izquierdo o un hijo derecho
si act.hder nulo entonces // act tiene un hijo derecho
si ant = nulo entonces // se trata del nodo raiz
Borrar un nodo (XI)
7/23/2019 FPII04 Estructuras No Lineales de Datos
52/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
52
Borrar un nodo (XI)
a act .hder
si_no // se trata de un nodo no raz
si ant .hder = actentonces // se trata del hijo derecho
ant.hder act .hder
si_no // se trata del hijo izquierdo
ant .hizq act .hderfin_si
fin_si
si_no // act tiene un hijo izquierdo
si ant = nulo entonces // se trata de un nodo raz
a act .hizq
si_no // se trata de un nodo no razsi ant.hder = actentonces // se trata del hijo derecho
ant.hder act .hizq
si_no // se trata del hijo izquierdo
ant.hizq act .hizq
fin_si
fin_sifin_si
fin_si
fin_si
liberar(act)
fin_procedimiento
Borrado recursivo
7/23/2019 FPII04 Estructuras No Lineales de Datos
53/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
53
Borrado recursivo
Se puede simplificar el borrado iterativo utilizando unasolucin recursiva.
El procedimiento, en este caso buscara el nodo y si loencuentra, lo elimina. Caso base.
Existen dos casos base: Si el rbol es nulo, el elemento no existe.
Si el elemento a borrar no es menor ni mayor que el elemento raz (sise encuentra), se borra el nodo. Caso general.
Dos llamadas recursivas: Si el elemento a borrar es menor que el raz, hay que borrar en el
subrbol izquierdo. Si el elemento a borrar es mayor que el raz, hay que borrar en el
subrbol derecho.
Borrado recursivo
7/23/2019 FPII04 Estructuras No Lineales de Datos
54/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
54
Borrado recursivo
El borrado del nodo slo presentara tres casos: Si es una hoja: el predecesor sera nulo (figura A de la
dispositiva siguiente). Si tiene un nico subrbol, el predecesor tendr que apuntar al
nico hijo de dicho rbol (figura B de la dispositiva siguiente). Si tiene dos hijos, se redistribuyen los nodos para que los nodos
restantes mantengan la estructura de rbol binario se bsqueda: Se sube a la posicin del nodo a borrar, el contenido del nodo del
elemento mayor del subrbol izquierdo. Se elimina el nodo situado ms a la derecha del subrbol izquierdo
(el que se ha subido). Para este proceso se realizar una llamada a otro procedimiento
recursivo que sustituir el valor del nodo a borrar.
Borrado recursivo (II)
7/23/2019 FPII04 Estructuras No Lineales de Datos
55/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
55
Borrado recursivo (II)
Borrado recursivo (III)
7/23/2019 FPII04 Estructuras No Lineales de Datos
56/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
56
Borrado recursivo (III)
procedimiento BorrarElemento(ref rbol : a; valor TipoElemento : e)
var
rbol : aux
inicio
si a = nulo entonces //El elemento no existesi_no
si e < a.razentonces
BorrarElemento(a.hizq,e)
si_no
si e > a.razentonces
BorrarElemento(a.hder,e)si_no //Borra el elemento a
aux a //aux guarda la direccin del nodo a borrar
si a.hder = nulo entonces //Si no tiene hijo derecho
a aux.hizq
si_no
si a.hizq = nulo entonces //Si no tiene hijo izquierdo
a aux.hder
si_no //Tiene dos hijos
SubirNodo(aux.hizq, aux)
fin_si
fin_si
Borrado recursivo (IV)
7/23/2019 FPII04 Estructuras No Lineales de Datos
57/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
57
Borrado recursivo (IV)
liberar(aux)
fin_si
fin_si
fin_si
fin_procedimiento
procedimiento SubirNodo(ref rbol : a, aux)
inicio
si a.hder nulo entonces //Moverse al mayor de los menoresSubirNodo(a.hder,aux)
si_no
aux.raz a.raz
aux a
a aux.hizq
fin_si
fin_procedimiento
Ejemplos
7/23/2019 FPII04 Estructuras No Lineales de Datos
58/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
58
Ejemplos
Disee una funcin que devuelva la altura de un rbol.
entero : funcin Altura(valor rbol : a)
iniciosi a nulo entonces
devolver(1 + MayorAltura(Altura(a.hizq),Altura(a.hder))
si_no
devolver(0)
fin_si
fin_funcin
entero funcin MayorAltura(E entero : a,b)
inicio
si a > b entonces
devolver(a)
si_nodevolver(b)
fin_si
fin_funcin
Ejemplos (II)
7/23/2019 FPII04 Estructuras No Lineales de Datos
59/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
59
j p ( )
Disee un procedimiento que copie un rbol
procedimiento Copiar(valor rbol : a; ref rbol : c)
iniciosi a nulo entonces
reservar(c)
c.raz a.raz
Copiar(a.hizq, c.hizq)
Copiar(a.hder, c.hder)
si_noc nulo
fin_si
fin_procedimiento
Ejemplos (III)
7/23/2019 FPII04 Estructuras No Lineales de Datos
60/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
60
j p ( )
Una funcin que compruebe si dos rboles son similares. Si los dos no son nulos, son similares si al subrbol derecho y el izquierdo son
similares.
Si los dos son nulos, son similares. Si uno es nulo y el otro no, no son similares.
lgico:funcin SonSimilares(valor arbol: a1,a2)
inicio
si (a1 nulo)y (a2 nulo)entoncesdevolver(SonSimilares(a1.hizq,a2.hizq)y SonSimilare(a1.hder,a2.hder))
si_no
devolver((a1 =nulo)y (a2 =nulo))
fin_si
fin_funcin
Ejemplos (IV)
7/23/2019 FPII04 Estructuras No Lineales de Datos
61/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
61
j p ( )
Una funcin que comprueba si dos rboles son equivalentes. Si los dos no son nulos y la informacin es la misma, son equivalentes si al subrbol derecho
y el izquierdo son equivalentes.
Si la raz es distinta no son equivalentes Si los dos son nulos, son equivalentes. Si uno es nulo y el otro no, no son equivalentes.
lgico:funcin SonEquivalentes(valor arbol: a1,a2)
inicio
si (a1 nulo)y (a2 nulo)entoncessi a1.raz = a2.razentonces
devolver(SonEquivalentes (a1.hizq,a2.hizq)y
SonEquivalentes (a1.hder,a2.hder))
si_no
devolver(falso)
si_nodevolver((a1 =nulo)y (a2 =nulo))
fin_si
fin_funcin
Ejemplos (V)
7/23/2019 FPII04 Estructuras No Lineales de Datos
62/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
62
j p ( )
Disee un algoritmo que calcule el nmero de nodos de un rbol. Si el rbol est vaco, el nmero de nodos es 0, Si no est vaco, al menos tiene un nodo y, adems puede tener ms
nodos a la izquierda o a la derecha.
entero funcin NmeroDeNodos(valor arbol: a)
inicio
si a =nulo entonces
devolver(0)
si_no
devolver(1 + NmeroDeNodos(a.hizq) + NmeroDeNodos(a.der))
fin_si
fin_funcin
Ejemplos (VI)
7/23/2019 FPII04 Estructuras No Lineales de Datos
63/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
63
Disee un algoritmo que devuelva el peso de un rbol. Si el rbol est vaco, el peso es 0.
Si el hijo izquierdo y el hijo derecho del rbol son nulos, el peso es 1. Si no, el peso ser la suma de los pesos de sus dos hijos.
entero funcin Peso(valor arbol: a)
inicio
si a =nulo entoncesdevolver(0)
si_no
si (a.hizq =nulo)y (a.der =nulo)entonces
devolver(1)
si_no
devolver(Peso(a.hizq) + Peso(a.der))
fin_si
fin_si
fin_funcin
Ejercicios (VII)
7/23/2019 FPII04 Estructuras No Lineales de Datos
64/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
64
1. Se tiene almacenado en un rbol binario de bsquedauna serie de nmeros ordenados de menor a mayor.
Disee un procedimiento que devuelva los nmerospero ordenados de mayor a menor.2. Se tiene almacenada una frase en un archivo de texto.
Disee un algoritmo que almacene las palabras de la
frase en un rbol binario de bsqueda. Las palabras delrbol no se podrn repetir y en cada nodo sealmacenar la palabra y el nmero de veces queaparece en la frase. El algoritmo deber mostrar por
pantalla las palabras ordenadas por la frecuencia deaparicin.
Ejercicios (VIII)
7/23/2019 FPII04 Estructuras No Lineales de Datos
65/65
Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodrguez Baena, Escuela Superior de Ingeniera y Arquitectura, 2012
65
3. En un archivo directo se tiene almacenada informacin sobre unaserie de automviles. Por cada registro del archivo aparece lamatrcula (campo clave), la marca y el modelo y el DNI delpropietario. Los registros estn distribuidos de forma aleatoria porel archivo que tiene una capacidad para 1000 vehculos. Disee unalgoritmo que cree un ndice del archivo en un rbol binario debsqueda. Cada nodo del rbol deber almacenar la matrcula y elnmero de registro relativo del archivo donde est almacenado elvehcuclo.
A partir de este ndice disee los procedimientos para: Realizar un listado con todos los datos de los vehculos del archivo. Sacar por pantalla los datos de un vehculo cuya matrcula se introduce por
teclado. Realizar la insercin de un nuevo vehculo en el archivo, insertandotambin la informacin necesaria en el ndice.
Realizar la eliminacin de un vehculo en el archivo.