Concepto de rbol en inform tica

Concepto de árbol en informática:

En ciencias de la computación y en informática, 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 (enese 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 deun nodo n_r 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 n_r 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 n_r, los nodos n_1, n_2, \dots, n_k son los hijos de n_r y el conjunto de nodos hoja estáformado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles A_i 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 árbol recorrido. Existen dos recorridos típicos para listar los nodos de un árbol: en profundidad y en anchura. En el primercaso, 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:
Elrecorrido 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 A_1, luego la raíz y luego cada uno de los hijos A_2 \dots A_k en ordensimé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 árbol en teoría de grafos. Un árbol es un grafo conexo y acíclic.





Terminologías utilizadas en árboles
Raíz - El nodo superiordel árbol.
Padre - Nodo con hijos.
Hijo - Nodo descendiente de otro nodo.
Hermanos - Nodos que comparten el mismo padre.
Hojas - Nodos sin hijos.
Nivel - El nivel de un nodo está definido por 1+ el número de conexiones entre el nodo y la raíz.
Tipos de árboles

Ejemplo de árbol (binario).
Árboles Binarios
Árbol de búsqueda binario auto-balanceable
Árboles AVL
Árboles Rojo-Negro
Árbol AA
Árbol desegmento
Árboles Multicamino
Árboles B (Árboles de búsqueda multicamino autobalanceados)
Árbol-B+
Árbol-B*

En términos generales:

En ciencias de la computación, 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 diceque 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.

El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre...