Download Estructura de Datos
Document related concepts
Transcript
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