Árbol Binario

Concepto de árbol binario.

Estas estructuras se utilizan para representar datos en forma jerárquica entre los elementos. Este tipo de estructura es un tipo de dato no lineal de dos dimensiones. Los nodos de los árboles que son los elementos o vértices contienen nodos o mas enlaces, entre los cuales contiene un nodo raíz que es el primer nodo del árbol y que a su vez cada enlace se refiere aun nodo hijo tales como hijo izquierdo e hijo derecho. Los hijos de un solo nodo se conocen como hermanos. Séle llama grado de un nodo al numero de hijos que salen de el y a los nodos con grado 0 se les llama nodos terminales u hojas. Cada numero de un árbol tiene asociado un numero de nivel que se determina por un numero de antecesores que tiene desde la raíz, teniendo en cuenta que el nivel de la raíz es 1 ó 0. Un árbol tiene profundidad o altura que es el máximo de niveles del árbol, además el árbol cuenta con peso que es el número de nodos terminales. Al conjunto de dos o más árboles se le conoce como bosque.

Este tipo de árbol tiene la característica de que los valores en cualquier subárbol izquierdo son menores que el valor de su nodo padre, y los valores en cualquier subárbol derecho son mayores que el valores de su nodo padre.

Árbol binario es aquel en el que cada nodo tiene como máximo el grado 2. Este es equilibrado cuando la diferencia de altura entre sus subárboles de cualquier nodo es como máximo una unidad, cuando todos los nodos se encuentran a la misma altura se dice que el árbol esta equilibrado. Se llama árbol binario lleno cuando todas sus hojas están al mismo nivel y sus nodos interiores tienen cada uno dos hijos. Un árbol binario completo es equilibrado mientras un árbol binario lleno es totalmente equilibrado.

Árboles binarios de búsqueda.

Dentro del tipo de árbol binario de búsqueda en cualquier nodo el valor es superior a los valores de los nodos de el subárbol (izquierdo e inferior) a el subárbol derecho. Dentro de las características de estos se puede decir que no son únicos para los datos dados.

La utilidad de este tipo de árbol es la eficiencia de búsqueda en un nodo, esta es similar a la búsqueda binaria. La supresión de un nodo requiere la liberación del espacio en la memoria que es ocupada por el mismo.

Búsqueda de un elemento.

Este comienza en el nodo raíz y consta de los siguientes pasos:

· La clave búsqueda se compra con la clave del nodo raíz.

· Si las claves son iguales la búsqueda se detiene.

· La clave búsqueda es mayor que la clave raíz, la búsqueda se reanuda en el subárbol derecho, si la clave búsqueda es menor que la clave raíz la búsqueda se reanuda en el subárbol izquierdo.

Árboles binarios equilibrados.

Es aquel en el que la altura de los subárboles izquierdo y derecho de cualquier nodo no difieren en más de una unidad. Para determinar si el árbol esta equilibrado, se lleva acabo un factor de equilibrio.

El factor de equilibrio del árbol binario es la diferencia de altura entre los subárboles izquierdo y derecho, si se denota la altura del subárbol izquierdo como h_I y la altura del subárbol derecho como h_D, entonces el factor de equilibrio en un árbol se determina por la siguiente formula:

Fe = h_D - h_I.

Árbol binario equilibrado, árboles AVL.

Se dice que la eficiencia de búsqueda de un árbol binario para localizar una clave varia entre 0(n) y (Log(n)), dependiendo de la estructura. Esto es, se añaden claves a un árbol binario de búsqueda mediante el uso de algoritmos, la estructura del árbol va a depender del orden en el que estas se añaden, de manera que los elementos se insertan de manera creciente o decreciente, de manera que el árbol tendrá todas las ramas izquierda y derecha vacías y la búsqueda en el árbol será de modo secuencial. Para que una búsqueda resulte eficiente es importante que los árboles binarios estén equilibrados y estos sean de mínima altura.

Un árbol binario equilibrado es aquel en el que la altura del subárbol izquierdo y derecho de cualquier nodo no difiere en mas de una unidad, de manera que permite que árboles asimétricos se consideren equilibrados. El árbol binario de búsqueda ideal será un árbol de búsqueda equilibrada y de altura mínima. Los árboles binarios son equilibrados con los denominados árboles AVL, los AVL son árboles binarios de búsqueda equilibrada, estos no necesariamente deben de ser de altura mínima.

Bibliografía:

C++ como programar. Cuarta edición.

Guillermo Trujado Mendoza, Miguel Gutiérrez Hernández.

Pearson Educación.

Estructuras de datos en C (SCHAUM).

Luís Joyanes Aguilar, Matilde Fernández Azuela

MC Graw Hill.