ÁRBOL

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. 

Tipos de árboles

Ø  Árboles Binarios:es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").

Ø  Árbol de búsqueda binarioauto-balanceable:Es un árbol que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente

Ø  Árboles AVL: es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

Ø  Árboles Rojo-Negro: es un tipo abstracto de datos. Concretamente, es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación.

Ø  Árbol AA: es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente.

Ø  Árbol de segmento: es una estructura de datos en forma de árbol para guardar intervalos o segmentos.

Ø  Árboles Multicamino:posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Ø  Árboles B:los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. 

Ø  Árbol-B+:es un tipo de estructura de datos de árbol, representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos.

ESTRUCTURA DE UN ARBOL

 ¿QUE ES DIAGRAMA DE ÁRBOL?

El diagrama de árbol es un grafo no dirigido conexo que no contiene circuitos, es decir que no existen dos o más paseos sobre un par de vértices.
Un conjunto de árboles disjuntos es llamado bosque. Un vértice de grado 1 en un árbol se llama hoja o un nodo terminal, y un vértice de grado mayor que 1 recibe el nombre de rama o nodo interno. Por ejemplo, son hojas: b, c, d y los vértices a, A, B, C, D son nodos rama.

RECORRIDO DEL DIAGRAMA DE ÁRBOL

Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados define el tipo de recorrido.

Estos pasos (en ningún orden particular) son: ejecución de una acción en el nodo actual (referido como “visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. Así el proceso más fácilmente descrito a través de la recursión.

Los nombres dados para un estilo particular de recorrido vienen de la posición del elemento de raíz con respecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).

Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos. Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los métodos de recorrido.

Recorrido en profundidad-primero

            Árbol binario

Ø  Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

·         Visite la raíz

·         Atraviese el sub-árbol izquierdo

·         Atraviese el sub-árbol derecho

Ø  Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

·         Atraviese el sub-árbol izquierdo

·         Visite la raíz

·         Atraviese el sub-árbol derecho

Ø  Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

·         Atraviese el sub-árbol izquierdo

·         Atraviese el sub-árbol derecho

·         Visite la raíz

En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.

ü  En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho

ü  En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho

ü  En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

            Preorden (antes), inorden (en medio), postorden (después).

            Árbol genérico

            Para recorrer un árbol no vacío en orden de profundidad-primero, hay que realizar las siguientes operaciones recursivamente en cada nodo:

·         Realice la operación pre-orden

·         Para i=1 a n-1 haga

           Visite al hijo[i], si existe

           Realice la operación in-orden

·         Visite al hijo[n], si existe

·         Realice la operación post-orden

Donde n es el número de nodos hijos. Dependiendo del problema actual, las operaciones de pre-orden, in-orden o post-orden pueden ser vacías (void), o usted puede querer visitar solamente un nodo de hijo específico, así que estas operaciones pueden ser consideradas opcionales.

También, en la práctica, más de una de las operaciones de pre-orden, in-orden y post-orden pueden ser requeridas. Por ejemplo, al insertar en un árbol ternario, una operación de pre-orden es realizada comparando elementos. Una operación de post-orden puede luego ser necesitada para rebalancear el árbol.

 Recorrido en anchura-primero

            Los árboles también pueden ser recorridos en orden por nivel (de nivel en nivel), donde visitamos cada nodo en un nivel antes de ir a un nivel inferior. Esto también es llamado recorrido en anchura-primero o recorrido en anchura.

REPRESENTACIÓN GRÁFICA DEL DIAGRAMA DE ÁRBOL

Para la construcción de un diagrama en árbol se partirá colocando una rama para cada una de las posibilidades, acompañada de su probabilidad. Cada una de estas ramas se conoce como rama de primera generación.

En el final de cada rama de primera generación se constituye a su vez, un nudo del cual parten nuevas ramas conocidas como ramas de segunda generación, según las posibilidades del siguiente paso, salvo si el nudo representa un posible final del experimento (nudo final).

Hay que tener en cuenta que la construcción de un árbol no depende de tener el mismo número de ramas de segunda generación que salen de cada rama de primera generación y que la suma de probabilidades de las ramas de cada nudo ha de dar 1.

Enlace del video: https://www.youtube.com/watch?v=Vh19NAFGTw4

FUENTES :

Árboles, tipos y sus propiedades - Documento en línea: (http://www.taringa.net/post/apuntes-y-monografias/11934388/Arboles-tipos-y-sus-propiedades-Matematicas.html)

Diagrama de árbol - Documento en línea: (https://es.wikipedia.org/wiki/ Diagrama_de_árbol)

Arboles - Documento en línea: (campus.cva.itesm.mx/nazira/Tc1003/PDF/.../0703Tc1003_Arboles.pdf)