Download TAD ABB

Almacenamiento y
Recuperacion de
Información TAD_ABB
Ana Lilia Laureano Cruces
Universidad Autónoma Metroplotiana
•
•
•
•
•
•
•
•
Arboles Binarios de Búsqueda
Arboles Blanceados (AVL)
Grafos y sus aplicaciones
Estructuras de Archivos
Ordenamientos externos
Indices
Arboles B y B+
Dispersion Hashing
Estructuras Jerárquicas
• Estructuras Jerárquicas: es la
organización de datos en forma de
jerarquía o niveles. Su principal
característica es que mantienen una
relación de uno a muchos (1:n), entre
sus elementos.
Árboles Binarios
Terminología básica de las
estructuras jerárquicas
•
•
•
•
•
•
Nodo raíz
Nodo padre
Hijo derecho
Hijo izquierdo
Nodo hoja
Nodo hermano
Terminología básica de las
estructuras jerárquicas
•
•
•
•
•
Ancestros
Nodo descendiente
Subárbol izquierdo
Subárbol derecho
Nivel de un nodo
5
3
2
1
8
9
4
6
7
10
El problema de la
búsqueda
• Una forma eficiente de realizar una
búsqueda es utilizando una estructura
lineales con el algoritmo de búsqueda binaria
aplicado en una tabla de memoria estática.
• Desventajas en la inserción y eliminación de
elementos.
• Con una lista ordenada se presentaba un
mejor comportamiento
• Contar con estructuras jerárquicas
representa una opción para aprovechar
las características positivas de estas
estructuras lineales.
Arbol binario de búsqueda
(ABB)
• Es una estructura de datos que guarda
información no repetida para
administrar eficientemente la búsqueda
de los propios datos. Es una estructura
jerárquica. En este caso se restringe la
relación de 1:2 como máximo.
Árbol binario de búsqueda
(ABB)
• El ordenamiento implica que para cada
elemento del ABB, los elementos
menores están a su izquierda y los
mayores a su derecha.
Ejemplos
2
8
5
1
4
3
9
3
Ejemplos
3
1
8
6
9
5
7
Ejemplos
7
2
9
6
4
5
Contra-Ejemplos
3
4
1
1
5
9
2
Contra-Ejemplos
3
1
6
9
8
5
7
Especificación del TAD
ABB
• Elementos: los elementos se identifican como
NODOS. Cada uno de ellos contiene un dato simple
o estructurado.
• Estructura: posee una estructura jerárquica a
excepción del árbol vacío; solo hay una raíz y los
demás son árboles disjuntos. Cada nodo a
excepción del nodo raíz tiene un único padre y tiene
uno, dos o no tiene hijos. El hijo izquierdo siempre
tendrá un valor menor, siendo la raíz del subárbol
izquierdo. Lo mismo en el caso de la derecha.
Operaciones del TAD ABB
• Crear
• Utilidad: crea o inicializa un árbol
• Entradas: el espacio de memoria donde se
creará el árbol
• Salidas: el árbol inicializado
• PreCond: Ninguna
• PostCond: el árbol esta inicializado sin
elementos
Operaciones del TAD ABB
• Buscar
• Utilidad: busca un elemento dentro del árbol
ABB
• Entradas: el árbol donde va a buscar y el
elemento (valor) a buscar
• Salidas: regresa falso si el valor no se
encuentra o verdadero caso contrario con un
apuntador donde se encuentra ese valor.
• PreCond: exista el árbol ABB
• PostCond: ninguna
Operaciones del TAD ABB
• Insertar
• Utilidad: inserta un nuevo elemento dentro del árbol
ABB
• Entradas: el árbol ABB donde va a insertar y el
elemento nuevo
• Salidas: el árbol quien tiene un nuevo valor
insertado como hoja, en la posición que le
corresponde.
• PreCond: el árbol ABB existe y el elemento nuevo
no esta en él.
• PostCond: el árbol ABB tiene un elemento nuevo
insertado como hoja
Operaciones del TAD ABB
• Borrar
• Utilidad: elimina un elemento del árbol
• Entradas: el árbol ABB de donde se va a borrar el
elemento y el elemento (dato) a borrar
• Salidas: regresa falso si el dato no se encuentra y
verdadero en caso contrario y si lo pudo borrar, en
cuyo caso regresa un árbol modificado
• PreCond: el árbol ABB existe y el elemento dato se
encuentra en dicho árbol
• PostCond: el árbol ABB contiene un elemento
menos
Operaciones del TAD ABB
• Recorrer
• Utilidad: despliega los elementos almacenados en el
árbol
• Entradas: el árbol ABB a desplegar y el orden en el
que se desplegarán los elementos
• Salidas: cada nodo se procesa exactamente una
vez. El orden en que se procesan los nodos
depende del valor de orden: PreOrden, InOrden y
PostOrden
• PreCond: existe el árbol ABB
• PostCond: ninguna
Algoritmo de búsqueda
1. Coloque un apuntador auxiliar en la raíz del árbol
2. Mientras no se haya encontrado el valor que se
busca y el apuntador auxiliar no este vacío (fuera
del árbol):
–
–
2.1. Verifique si la información del nodo señalado, por el
apuntador auxiliar es mayor, menor o igual al nodo
buscado.
2.2. Si es mayor mueva el apuntador auxiliar al nodo hijo
derecho; caso contrario al izquierdo. Si son iguales ha
encontrado el nodo y el apuntador auxiliar lo señala.
12
7
4
2
21
25
9 16
8
13
19
Por qué es eficiente la
búsqueda en un ABB
• El ABB es una consecuencia directa del algoritmo de
búsqueda binaria sobre una estructura lineal y, por
tanto tiene todos sus beneficios. Si un ABB tiene
distribuidos sus elementos en forma balanceada se
obtendrá el mayor beneficio, pues se harían las
mismas comparaciones que en una búsqueda
binaria sobre un arreglo. El peor caso de una
búsqueda en un ABB esta determinado por la altura
del árbol y, por lo tanto entre menor altura (más
balanceado) se obtendrán mejores resultados.
Algoritmo de Inserción
1. Se crea un nuevo nodo utilizando un
apuntador auxiliar 1. Se llena con la
información que se va a insertar en el árbol
y se colocan sus apuntadores como nodo
hoja (Nil).
2. Se coloca un apuntador auxiliar 2 en la raíz
del árbol y un apuntador auxiliar 3 en
vacío. El apuntador auxiliar 3 siempre
señalará al nodo padre del nodo al que
señala el apuntador auxiliar 2.
Algoritmo de Inserción
3. Mientras el apuntador auxiliar 2, no sea
vacío (fuera del árbol) se realiza lo
siguiente:
. Se coloca el apuntador auxiliar 3 en el
nodo que marca el apuntador auxiliar 2.
. Mueva el apuntador auxiliar 2 al nodo hijo
izquierdo si la información que se va a
insertar es menor a la información del nodo
que señala el apuntador auxiliar 2; caso
contrario, debe moverse a la derecha (pues
la información por insertar es mayor).
Algoritmo de Inserción
– Al salir del ciclo el apuntador auxiliar 2
señalará vacío, pero el apuntador auxiliar
3 estará en el nodo que será el padre del
nuevo.
• 4. Verifique si el apuntador auxiliar 3 es
vacío, en cuyo caso, el nuevo nodo
será el primero del árbol y el apuntador
raíz tendrá que señalarlo.
Algoritmo de Inserción
• Si el apuntador auxiliar 3 no es vacío,
entonces estará señalando al padre del
nuevo nodo. Se debe verificar si la
información del nuevo nodo es menor a
la del marcado por el apuntador auxiliar
3. Si la información no es menor,
entonces será mayor y tendrá que
encadenarse como hijo derecho.
12
Se busca el 15
7
4
2
21
25
9 16
8
13
19
15
Puesto que no existe se
Detecta el padre del 15
Eliminación
• La acción de borrar un nodo puede
enfrentarse con alguna de los
siguientes casos:
1. El nodo que se va a borrar es una hoja
puesto que no tiene hijos su nodo padre
apuntará ahora a vacío.
Eliminación
12
Se busca el elemento
8
7
4
2
21
25
9 16
8
13
19
Eliminación
12
7
4
2
21
25
9 16
13
19
El padre del nodo borrado
Cambia su liga a NULL
Eliminación
• 2. El nodo por borrar tiene sólo un hijo.
En este caso, el padre del que se va a
borrar puede apuntar directamente al
nodo hijo del que se eliminará.
Eliminación
12
Se busca el elemento
7
4
2
21
9 16
8
13
19
Eliminación
12
7
4
2
16
9
8
El padre del nodo
Borrado cambia su
Apuntador al hijo del
Nodo borrado
13
19
Eliminación
• El nodo por borrar tiene dos hijos. Puesto que el
padre del que se va a eliminar no puede heredar dos
apuntadores, se busca un valor substituto del valor
por borrar y el nodo no se borra físicamente. Se
puede escoger como substituto al predecesor del
que se eliminará (el valor mayor de todos los valores
menores, en otras palabras, de los nodos del
subarbol izq. El de más a la derecha), y se elimina
físicamente el nodo donde se encuentre. La baja
física del nodo substituto cae en alguno de los dos
primeros casos. También es posible considerar al
sucesor como valor substituto.
Eliminación
12
Se busca el elemento
12
7
4
2
21
25
9 16
8
13
19
Eliminación
12
7
4
2
21
25
9 16
8
Predecesor
13
19
Sucesor
Eliminación
Baja utilizando el predecesor
9
7
4
2
21
25
8 16
13
19
Eliminación
• El algoritmo de esta operación esta
compuesto por dos partes. La primera
localiza el nodo por borrar y la segunda
borra el nodo encontrado.
Primera parte
• 1. Se coloca un apuntador auxiliar 1 en
la raíz del árbol y un apuntador auxiliar
2 a vacío. El apuntador auxiliar siempre
señalará al nodo del padre del que
señala el apuntador auxiliar 1.
Primera parte
• 2. Mientras no se haya encontrado el nodo por
borrar
– Se verifica si la información del nodo señalado por el
apuntador auxiliar 1 es la que se desea borrar, en caso de
que no sea:
• Se coloca el apuntador auxiliar 2 en el nodo que señala el
apuntador auxiliar 1.
• Se mueve el apuntador auxiliar 1 al nodo al nodo hijo izq. Si la
información que se va a borrar es menor a la información del
nodo que señala el apuntador auxiliar 1; caso contrario, se
debe mover a la derecha.
• Al salir del ciclo, el ap. 1 estará señalando al nodo
por borrar y el ap. 2 al nodo padre.
Segunda parte
• Se coloca un apuntador temporal en el nodo
que debe borrar.
• Se verifica si el nodo por borrar es hoja o
tiene solo un hijo, en cuyo caso se eliminará
del árbol para darlo de baja.
– Nodo hoja: si el nodo apuntado por el auxiliar 1
no tiene hijo izq., ni der. Debe modificarse el
apuntador que lo conecta con su nodo padre (a
través del auxiliar 2) de tal forma que apunte
hacia vacío.
nodo con un hijo derecho: si el nodo apuntado por el auxiliar 1,
no tiene hijo izq. Pero si der. Se modifica el apuntador que lo
conecta con su padre (a través del auxiliar 2) de tal forma que
señale al hijo der.
nodo con un hijo izquierdo: si el nodo apuntado por el auxiliar 1
no tiene hijo der., pero si hijo izq., debe modificarse el
apuntador que lo conecta con su padre (a través de del auxiliar
2) de tal forma que señale al nodo hijo izq.
• Nodo con dos hijos: si el nodo tiene dos hijos se
procederá a localizar su substituto de la siguiente
forma:
– Se coloca el apuntador temporal en el hijo izq. Del nodo
señalado por el apuntador auxiliar 1.
– Se mueve el apuntador temporal hacia la derecha lo más
posible, es decir, justo en el nodo antes de que el
movimiento a la derecha lo saque del árbol. El nodo al que
se llege será el nodo subsituto y se puede asegurar que es
nodo hoja o que tiene sólo un hijo izq.
• Se copia la información del nodo subsituto, en el
marcado por el apuntador auxiliar 1.
• Se desencadena el nodo señalado por elpauntador
temporal de la misma forma en que se hace para un
nodo hoja o uno con hijo izq. En este caso para el
movimiento de apuntadores se tendrá que evaluar si
el nodo marcado por el apuntador temporal es la
raíz del subárbol izq. Del nodo señalado por el
apuntador auxiliarn1 o es de un nivel inferior.
• 3. Se libera el nodo señalado por el
apuntador temporal.
Ventajas y desventajas de
ABB sobre un ABB
• Representación en memoria dinámica (V)
• La forma en que se relaizan las inserciones y
eliminaciones de elementos. El orden de los
elementos, es el que balancea el arbol y
puede repercutir en posteriores búsquedas.
(D)
Aplicaciones
• Útil en la que se requiera administrar un
grupo de datos ordenados en memoria
principal. Con el objetivo básico de buscar
de manera eficiente cualquier dato.se
recomienda que la apliación tenga al grupo
de datos bien definido desde un principio. Y
qu no requiera muchas altas y bajas de
forma que mantener al árbol balnceado.