Arboles Y Tabla Hash

Instituto Universitario de Mercadotecnia
Materia: Estructura de Datos
Carrera: informática

Arboles y tablas de hash



INDICE

* Definición de Arboles

* Operaciones Básicas con arboles

* Búsqueda
* Inserción
* Borrado

*Ejemplos de cada Operación

* Definición de la tabla de Hash

* Operación Básica de la tabla de Hash

* Búsqueda
* Inserción

* Ejemplos década operación

* Tabla comparativa entre los Arboles y las tablas Hash


DESARROLLO

* Definición de Árbol

Representan las estructuras lineales y no lineales dinámicas más importantes en computación. Dinámicas, porquela estructura árbol puede cambiar durante la ejecución de un programa, No lineales porque a cada elemento de árbol puede seguirte varios elementos. Un árbol General. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, unos de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre,hijo, hermano, antecesor, sucesor, ancestro etc.

* Operaciones Básicas con arboles

* Búsqueda : Implica la localización de un registro caracterizado por una determinada clave o también el acceso a todos los registros que cumpla con una o mas condiciones

. Los árboles de búsqueda son muy eficientes. El algoritmo compara el elemento a buscar con la raíz, si es menor continua la búsquedapor la rama izquierda, si es mayor continua por la izquierda. Este procedimiento se realiza recursivamente hasta que se encuentra el nodo o hasta que se llega al final del árbol.
Otra operación importante en el árbol es el recorrido el mismo. El recorrido se puede realizar de tres formas diferentes:
· Pre orden: Primero el nodo raíz, luego el subárbol izquierdo y a continuación el subárbolderecho.
· Inorden: Primero el subárbol izquierdo, luego la raíz y a continuación el subárbol derecho.
· Postorden: Primero el subárbol izquierdo, luego el subárbol derecho y a continuación la raíz.
El siguiente árbol es un ejemplo de árbol de búsqueda:

* Inserción

El procedimiento de inserción en un árbol binario de búsqueda es muy sencillo, únicamente hay que tener cuidado de no romper laestructura ni el orden del árbol.
Cuando se inserta un nuevo nodo en el árbol hay que tener en cuenta que cada nodo no puede tener más de dos hijos, por esta razón si un nodo ya tiene 2 hijos, el nuevo nodo nunca se podrá insertar como su hijo. Con esta restricción nos aseguramos mantener la estructura del árbol, pero aún nos falta mantener el orden.
Para localizar el lugar adecuado del árboldonde insertar el nuevo nodo se realizan comparaciones entre los nodos del árbol y el elemento a insertar. El primer nodo que se compara es la raíz, si el nuevo nodo es menor que la raíz, la búsqueda prosigue por el nodo izquierdo de éste. Si el nuevo nodo fuese mayor, la búsqueda seguiría por el hijo derecho de la raíz.
Este procedimiento es recursivo, y su condición de parada es llegar a un nodoque no tenga hijo en la rama por la que la búsqueda debería seguir. En este caso el nuevo nodo se inserta en ese hueco, como su nuevo hijo.
Vamos a verlo con un ejemplo sobre el siguiente árbol:
Se quiere insertar el elemento 6.
Lo primero es comparar el nuevo elemento con la raíz. Como 6 > 4, entonces la búsqueda prosigue por el lado derecho. Ahora el nuevo nodo se compara con el elemento8. En este caso 6 <>

* Borrado
El borrado en árboles binarios de búsqueda es otra operación bastante sencilla excepto en un caso. Tras realizar la búsqueda del nodo a eliminar observamos que el nodo no tiene hijos. Este es el caso más sencillo, únicamente habrá que borrar el elemento y ya habremos concluido la operación. Si tras realizar la búsqueda nos encontramos con que tiene un...