Minientrada

Arboles y Arboles Binarios

 Un árbol es una estructura de datos, ampliamente usada que imita 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. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

 

Formalmente, podemos definir un árbol de la siguiente forma:

  • Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

  • Un nuevo árbol a partir de un nodo nr y k árboles A_1, A_2 \dots A_k de raíces n_1, n_2, \dots, n_k con N_1, N_2, \dots ,N_k elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los k árboles. El árbol resultante de N = 1 + N_1 + \dots + N_k nodos tiene como raíz el nodo nr, los nodos n_1, n_2, \dots, n_k son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

  • El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos A_1, A_2 \dots A_k en orden previo.

  • El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos A_2 \dots A_k en orden simétrico.

  • El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos A_1, A_2 \dots A_k en orden posterior y por último la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de arbol en teoria de grafos. Un árbol es un grafo conexo y aciclico.

Las operaciones comunes en árboles son:

  • Enumerar todos los elementos.

  • Buscar un elemento.

  • Dado un nodo, listar los hijos (si los hay).

  • Borrar un elemento.

  • Eliminar un subárbol (algunas veces llamada podar).

  • Añadir un subárbol (algunas veces llamada injertar).

  • Encontrar la raíz de cualquier nodo.

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

  • Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.

  • Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

Usos comunes de los árboles son:

  • Representación de datos jerarquicos.

  • Como ayuda para realizar búsquedas en conjuntos de datos

Arboles 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 arboles binarios de busqueda, los monticulos binarios y Codificacion de Huffman.

 En Teoria de Grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.

Tipos de Arboles Binarios.

  • Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

  • Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

  • Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

  • A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Recorridos en profundidad

El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos:

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.

En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

void preorden(tArbol *a) { if (a != NULL) { tratar(a); //Realiza una operación en nodo preorden(a->hIzquierdo); preorden(a->hDerecho); } }

Implementación en pseudocódigo de forma iterativa:

push(s,NULL); //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía push(s,raíz); //insertamos el nodo raíz MIENTRAS (s <> NULL) HACER p = pop(s); //sacamos un elemento de la pila tratar(p); //realizamos operaciones sobre el nodo p SI (D(p) <> NULL) //preguntamos si p tiene árbol derecho ENTONCES push(s,D(p)); FIN-SI SI (I(p) <> NULL) //preguntamos si p tiene árbol izquierdo ENTONCES push(s,I(p)); FIN-SI FIN-MIENTRAS

Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

void postorden(tArbol *a) { if (a != NULL) { postorden(a->hIzquiedo); postorden(a->hDerecho); tratar(a); //Realiza una operación en nodo } }

Recorrido en inorden

En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 9, 4.

Esquema de implementación:

void inorden(tArbol *a) { if (a != NULL) { inorden(a->hIzquierdo); tratar(a); //Realiza una operación en nodo inorden(a->hDerecho); } }

Recorridos en amplitud (o por niveles)

En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.

Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.

El esquema algoritmo para implementar un recorrido por niveles es exactamente el mismo que el utilizado en la versión iterativa del recorrido en preorden pero cambiando la estructura de datos que almacena los nodos por una cola.

Métodos para almacenar árboles binarios

Los árboles binarios pueden ser construidos a partir de Lenguaje de Programacion de varias formas. En un lenguaje con registro y Referencia, los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, también contiene un puntero a un único nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo. En la figura adjunta se puede observar la estructura de dicha implementación.

Los árboles binarios también pueden ser almacenados como una estructura de datos implicita en vectores, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos como notación la siguiente: si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índice \left \lfloor \frac{i-1}{2} \right \rfloor (partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.

Arboles y Arboles Binarios

Deja un comentario o(‧'.'‧)o

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s