Operaciones Basicas Sobre Arboles Binarios

Centro Universitario de Valladolid

Licenciatura en Sistemas Computacionales

Nombre: Ángel Gabriel Martínez Alegría

Asignatura: Estructura de Datos

Trabajo: Investigación “Operaciones básicas sobre arboles binarios”

Fecha: 12/Julio/2011

Introducción
En este tema aprenderemos como se utilizan todas y cada una de las operaciones básicas en los arboles binarios, desde la creaciónde un arbol binario hasta el balanceo de un arbol binario, como también veremos como insertar, eliminar nodos y como funcionan sus recorridos en tales arboles binarios. Esto nos será útil para los diferentes y cada uno de los lenguajes que veremos para la programación ya que aprendiendo cada uno de estos entenderemos como funcionan cada uno de ellos y por ende comprenderemos como utilizarlos entales lenguajes de programación . Nos ayudara a desarrollar la capacidad de poder solucionar problemas en la creación de algoritmos aplicaciones en los lenguajes de programación y veremos como estos funcionan en las diversas estructuras de datos.

Un árbol binario de búsqueda es aquel que es: - Una estructura vacía o - Un elemento o clave de información (nodo) más un número finito -a lo sumodosde estructuras tipo árbol, disjuntos, llamados subárboles y además cumplen lo siguiente: * Todas las claves del subárbol izquierdo al nodo son menores que la clave del nodo. * Todas las claves del subárbol derecho al nodo son mayores que la clave del nodo. * Ambos subárboles son árboles binarios de búsqueda. Un ejemplo de árbol binario de búsqueda:

Figura 5

Al definir el tipo de datos querepresenta la clave de un nodo dentro de un árbol binario de búsqueda es necesario que en dicho tipo se pueda establecer una relación de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual a lo que apunte). Si se codifica el árbol en Pascal no se puede establecer una relación de orden para las claves, puesto que Pascal no admite determinar si un puntero es mayor omenor que otro. En el ejemplo de la figura las claves son números enteros. Dada la raíz 4, las claves del subárbol izquierdo son menores que 4, y las claves del subárbol derecho son mayores que 4. Esto se cumple también para todos los subárboles. Si se hace el recorrido de este árbol en orden central se obtiene una lista de los números ordenada de menor a mayor.

Una ventaja fundamental de losárboles de búsqueda es que son en general mucho más rápidos para localizar un elemento que una lista enlazada. Por tanto, son más rápidos para insertar y borrar elementos. Si el árbol está perfectamente equilibrado , es decir, la diferencia entre el número de nodos del subárbol izquierdo y el número de nodos del subárbol derecho es a lo sumo 1, para todos los nodos, entonces el número de comparacionesnecesarias para localizar una clave es aproximadamente de logN en el peor caso. Además, el algoritmo de inserción en un árbol binario de búsqueda tiene la ventaja sobre los arrays ordenados, donde se emplearía búsqueda dicotómica para localizar un elementode que no necesita hacer una reubicación de los elementos de la estructura para que esta siga ordenada después de la inserción. Dicho algoritmofunciona avanzando por el árbol escogiendo la rama izquierda o derecha en función de la clave que se inserta y la clave del nodo actual, hasta encontrar su ubicación; por ejemplo, insertar la clave 7 en el árbol de la figura 5 requiere avanzar por el árbol hasta llegar a la clave 8, e introducir la nueva clave en el subárbol izquierdo a 8. El algoritmo de borrado en árboles es algo más complejo,pero más eficiente que el de borrado en un array ordenado. Ahora bien, suponer que se tiene un árbol vacío, que admite claves de tipo entero. Suponer que se van a ir introduciendo las claves de forma ascendente. Ejemplo: 1,2,3,4,5,6 Se crea un árbol cuya raíz tiene la clave 1. Se inserta la clave 2 en el subárbol derecho de 1. A continuación se inserta la clave 3 en el subárbol derecho de 2....