Conceptos básicos de Árboles

Árbol

En informática, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.

Altura de un nodo

La altura de un nodo es el número de aristas en el camino más largo entre ese nodo y una hoja.

Altura de un árbol

Es la longitud del camino más largo que puede encontrarse en un árbol.

Nivel

El nivel de un nodo se define por 1 + (el número de conexiones entre el nodo y la raíz).

Grado

Número de subárboles de un nodo.

Tipos de arboles: Binarios y Heap

Árboles Binarios

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre “binario”). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Los Montículos binarios

Un caso particular y sencillo de la estructura de datos Montículo, y está basada en un árbol binario balanceado, que puede verse como un árbol binario con dos restricciones adicionales:

·         Propiedad de montículo

Cada nodo contiene un valor superior al de sus hijos (para un montículo por máximos) o más pequeño que el de sus hijos (para un montículo por mínimos).

·         Árbol semi completo

El árbol está balanceado y en un mismo nivel las inserciones se realizan de izquierda a derecha.

Los montículos por mínimos se utilizan frecuentemente para representar colas de prioridad. A continuación se muestran dos montículos: el primero por mínimos y el segundo por máximos, que representan el mismo conjunto de valores y además son semi completos.

Algoritmos: Insertar y Heapify.

Insertar

En el caso de tener un arreglo (array) ordenado en el algoritmo no se debe especificar ninguna posición, los elementos ocupan las posiciones que se les son asignadas según su valorDentro de este tipo de algoritmo pueden presentarse dos situaciones: Los elementos no pueden encontrarse repetidos en la lista. Los elementos pueden repetirse.

• Los elementos no pueden encontrarse repetidos en la lista: Al darse este caso dentro de la lista, nos arroga un mensaje o un código de error indicándonos que el elemento no se puede insertar. Si esto no sucede, se tendrá que buscar la posición que le corresponde en el arreglo y haga la inserción en la línea que le corresponde, que es de forma similar a la que se utiliza en el caso de arreglo no ordenados.

• Los elementos pueden repetirse: En este caso nos da igual que el elemento este o no en el arreglo. Simplemente utilizamos el método binario para que determine la posición donde se encuentra alojado el elemento o donde este debería estar, y en esta posición se debe insertar el nuevo número.

Algoritmo Heap Sort 

Una de las aplicaciones de los Heaps o Montículos es el algoritmo HeapSort, el cual es uno de tantos que permite ordenar un conjunto "S" de datos en tiempo “linearítmico“ O(n logn). No es un algoritmo estable, es decir, no garantiza que los elementos tengan el mismo orden relativo después de la ordenación, pero a diferencia de otros algoritmos comoQuicksort siempre garantiza O(n logn) como mejor, promedio o peor caso.

Una vez que se entiende la estructura de datos Heap el algoritmo es bastante sencillo y se basa en los siguientes pasos:

1.   Construir un MaxHeap o MinHeap a partir de un arreglo.

2.   Inicializar un ciclo desde I=heap.Length – 1 hasta I > 1 e Ir eliminando el tope (intercambiándolo con el último elemento I). Luego se verifica desde el primer nodo que se mantenga la propiedad del montículo (El mayor o menor elemento esté en el tope) esta operación generalmente se conoce como Heapify.

La explicación de eliminar del tope junto con Heapify puedes leerlas en mi post sobre Heaps o montículos, donde las explico con imágenes para que se entienda un poco mejor. Cabe destacar que para ordenar de manera creciente se utiliza un MaxHeap y para ordenar de manera decreciente un MinHeap. De igual manera, vale mencionar que la mayoría de las implementaciones de este algoritmo son en sitio, es decir, se modifica directamente el arreglo que se quiere ordenar.

Paso 1

Para construir el heap hay que recorrer el arreglo, recordemos que un montículo se basa un arreglo, desde (arreglo.Length / 2) hasta > 1. Se hace desde abajo hacia arriba porque a partir de (arreglo.Length) / 2 + 1 todos los nodos son hijos y en Heapify se deben verificar los nodos padres contra los hijos e ir intercambiando según sea el caso (con el mayor o el menor de los hijos) para mantener la propiedad del montículo. En Pseudocódigo sería algo como:

void BuildHeap(int[] array)

{

    for (int i = array.Length / 2; i <= 0; i--)

    {

        //Hacer cumplir la propiedad del heap dependiendo

        //si es un MaxHeap o un MinHeap

        Heapify(array, i, array.Length);

    }

}

Paso 2

Dentro de un ciclo vamos intercambiando el primer con el último elemento no ordenado y luego llamamos a Heapify para mantener la propiedad del Heap en la parte no ordenada del arreglo.

Teoremas binarios.

Teorema I

Un grafo no dirigido es un árbol, sí y solo sí hay un único camino entre cada pareja de vértices.

Raíces de un árbol

Un árbol con raíz es un árbol en que uno de sus vértices  ha sido designado como la raíz y todas las aristas están orientadas de modo que se alejan de la raíz.

Teorema II

Un árbol de n vértices tiene n-1 aristas.