Árbol (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 (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.

Definición

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

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 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.

Terminologías utilizadas en árboles

Tipos de árboles

Ejemplo de árbol (binario).

Operaciones de árboles. Representación

Las rotaciones en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto) del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico.

Las operaciones comunes en árboles son:

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

Uso de los árboles

Usos comunes de los árboles son:

Véase también

Algoritmos de búsqueda en árboles

This article is issued from Wikipedia - version of the Friday, October 23, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.