Operaciones Basicas Sobre Arboles Binarios

OPERACIONES BASICAS SOBRE ARBOLES BINARIOS

SUSANA VALENTIN VASQUEZ

INTRODUCCION

Intuitivamente el concepto de árbol implica una estructura donde los datos se organizan de modo que los elementos de información estén relacionados entre si a través de ramas.El árbol es una estructura fundamental en las ciencias de la computación. Se lo utiliza principalmente para representar jerarquía yser utilizado en todo lo que conlleve establecer un orden en un conjunto de valores. Los árboles tienen muchas aplicaciones. Casi todos los sistemas operativos utilizan estructuras de árbol para almacenar sus archivos. También son usados para el diseño de compiladores, procesamiento de textos y algoritmos de búsqueda. Un árbol es una colección no vacía de nodos y aristas que cumplen ciertosrequisitos. Un nodo (o vértice) es un objeto que puede llevar información asociada, una arista es una conexión entre dos nodos. Un árbol con raíz es uno en el que se designa un nodo como raíz. En general se reserva el término árbol para referirse a árboles con raíz y árboles libres para aquellas estructuras de datos que cumplen con la característica de árbol pero que no tienen especificada una raíz. Eneste apunte solo trataremos árboles con raíz.

ARBOLES BINARIOS

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 árboles binarios disjuntos, es decir, dos descendientes directos llamados subárbol izquierdo y subárbol derecho. Los árboles binarios (también llamados de grado 2) tienen una especial importancia. Lasaplicaciones 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. Arboles binarios de búsqueda Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera quela clave de cada nodo es mayor que todas las claves su subarbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este árbol es un árbol binario de búsqueda.

Ejemplo: Operaciones básicas: Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de unatarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol. Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse delproceso del siguiente elemento en el árbol, según un cierto orden subyacente.

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 la estructura 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 yatiene 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 árbol donde 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 laraí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 nodo que 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...