Árbol (estructura de datos)
Keywords: Árbol (estructura de datos), Array, B-Árbol, Computación, Estructura de datos, Glosario en teoría de grafos, Heap, Teoría de los grafos, Árbol AVL
| Tabla de contenidos |
Concepto y definiciones
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 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.
Formalmente, podemos definir un árbol de la siguiente forma recursiva:
- 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
de raíces 
con 
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 
nodos tiene como raíz el nodo nr, los nodos 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 árbos: 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.
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íclico (ver también teoría de grafos y Glosario en teoría de grafos).
Tipos de árboles
Binary_tree.png
Operaciones de árboles. Representación
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 raiz 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.
Ventajas de unos tipos de árboles frente a otros
AVL guarda un equilibrio, la diferencia entre las alturas de los subarboles que cuelgan del nodo son como mucho 1.
Uso de los árboles
Usos comunes de los árboles son:
- Representación de datos jerarquicos.
- Como ayuda para realizar búsquedas en conjuntos de datos (ver tambien: algoritmos de busqueda en Árboles )
Implementaciones
Ejemplos
Terminos Relacionados
- Partición binaria del espacio
- Heap
- Árbol (teoría de grafos)
- Algoritmos de busqueda en árboles
- Estructura de un árbol
- Árbol exponencial
Arbol (programacion)