Download Estructura de Datos

Estructura de Datos
ABB Arboles de Búsqueda Binaria
Árboles Binarios
Hasta ahora nos hemos dedicado a estudiar TAD que de una u otra forma
eran de naturaleza lineal, o unidimensional. En los tipos abstractos de
datos lineales existen exactamente un elemento previo y otro siguiente
(excepto para el primero y el último, si los hay); en las estructuras no
lineales, como conjuntos o árboles, este tipo de secuencialidad no existe,
aunque en los árboles existe una estructura jerárquica, de manera que un
elemento tiene un solo predecesor, pero varios sucesores.
Se define un árbol binario como un conjunto finito de elementos (nodos) que
bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos,
es decir, dos descendientes directos llamados subarbol izquierdo y subarbol
derecho.
Los árboles binarios (también llamados de grado 2) tienen una especial
importancia.
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.
Árboles de Búsqueda Binaria
La búsqueda en árboles binarios es un método de búsqueda simple,
dinámico y eficiente considerado como uno de los fundamentales en Ciencia
de la Computación. De toda la terminología sobre árboles, tan sólo recordar
que la propiedad que define un árbol binario es que cada nodo tiene a lo más
un hijo a la izquierda y uno a la derecha. Para construir los algoritmos
consideraremos que cada nodo contiene un registro con un valor clave a
través del cual efectuaremos las búsquedas.
En las implementaciones que presentaremos sólo se considerará en cada
nodo del árbol un valor del tipo tElemento aunque en un caso general ese
tipo estará compuesto por dos: una clave indicando el campo por el cual se
realiza la ordenación y una información asociada a dicha clave o visto de
otra forma, una información que puede ser compuesta en la cual existe
definido un orden.
Un árbol binario de búsqueda(ABB) es un árbol binario con la propiedad
de que todos los elementos almacenados en el subárbol izquierdo de
cualquier nodo x son menores que el elemento almacenado en x, y todos
los elementos almacenados en el subárbol derecho de x son mayores que el
elemento almacenado en x.
Definición
Todo árbol vacío es un árbol binario de búsqueda.
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor
máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo
sea un árbol binario de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor
mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea
un árbol binario de búsqueda.
50
90
40
26
8
45
34
42
110
85
68
88
100
110
105
95
102
Ejemplo de Inserción en un ABB
Por ejemplo supongamos que queremos construir un ABB a partir del
conjunto de enteros
{10,5,14,7,12}
Eliminación en un ABB
El procedimiento para eliminar un nodo z de un árbol de búsqueda binaria
tiene tres casos:
Caso 1:
Si z no tiene hijos, se modifica su padre p[z] para reemplazar z con nil como
su hijo.
Ejemplo:
Caso 2:
Si z tiene un solo hijo, simplemente se separa z del árbol.
Ejemplo:
Caso 3:
Si z tiene dos hijos, se separa su sucesor y, el cual tiene como máximo un
hijo, y luego se reemplaza el contenido de z con el contenido de y.
Se tienen que sustituir por el nodo que se encuentra mas a la izquierda en el
subárbol derecho, o por el nodo que se encuentra mas a la derecha en el
subárbol izquierdo
Ejemplo:
Ejemplo
(A* B) + C * D + E
+
+
*
A
B
E
*
C
D
Recorridos
Preorden
Inorden
Postorden
Recorrido en preorden (prefijo)
Visita la raíz.
Recorre el subárbol izquierdo.
Recorre el subárbol derecho.
C
B
E
D
G
Preorden = A B D G C E H I F
RID
A
H
F
I
Recorrido en inorden (infijo)
Recorre el subárbol izquierdo.
Visita la raíz
Recorre el subárbol derecho.
IRD
A
C
B
E
D
F
Inorden: D G B A H E I C F
G
H
I
Recorrido en postorden (postfijo)
Recorre el subárbol izquierdo.
Recorre el subárbol derecho.
Visita la raíz.
IDR
A
C
B
E
D
F
Postorden : G D B H I E F C A
G
H
I
Ejemplo RID
IRD
IDR
120 –87 – 43 – 65 – 140 – 99 – 130 – 22 – 56
Preorden (RID)= 120 87 43 22 65 56 99 140 130
Inorden (IRD): 22 43 56 65 87 99 120 130 140
Postorden (IDR): 22 56 65 43 99 87 130 140 120
Ejercicio 1
PREORDEN
INORDEN
A BDGEHICFJK
G D B H E IA C J K F
POTS ORDEN
G D H I E B K J F CA