Diferencia entre revisiones de «Árbol (informática)»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 22:38 24 sep 2009

En ciencias de la 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:

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 $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 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 $A_{1}$ , 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 á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

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

Uso de los árboles

Usos comunes de los árboles son:

Representación de datos jerárquicos.
Como ayuda para realizar búsquedas en conjuntos de datos (ver también: algoritmos de búsqueda en Árboles )

Véase también

Algoritmos de búsqueda en árboles

@@ Línea 20: / Línea 20: @@
 == Tipos de árboles ==
-[[Image:binary_tree_(oriented digraph).png|right|192|thumb|Eje==Definición==
+[[Image:binary_tree_(oriented digraph).png|right|192|thumb|Ejemplo de árbol (binario).]]
-Formalmente, podemos definir un árbol de la siguiente forma:
-:
+* [[Árbol_binario|Árboles Binarios]]
-* Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
+* [[Árbol de búsqueda binario auto-balanceable]]
+** [[Árbol_rojo-negro|Árboles Rojo-Negro]]
-* Un nuevo árbol a partir de un nodo <math>n_r</math> y <math>k</math> árboles <math>A_1, A_2 \dots A_k</math> de raíces <math>n_1, n_2, \dots, n_k</math> con <math>N_1, N_2, \dots ,N_k</math> elementos cada uno, puede construirse estableciendo una relación padre-hijo entre <math>n_r</math> y cada una de las raíces de los <math>k</math> árboles. El árbol resultante de <math>N = 1 + N_1 + \dots + N_k</math> nodos tiene como raíz el nodo <math>n_r</math>, los nodos <math>n_1, n_2, \dots, n_k</math> son los hijos de <math>n_r</math> y el conjunto de nodos hoja está formado por la unión de los <math>k</math> conjuntos hojas iniciales. A cada uno de los árboles <math>A_i</math> se les denota ahora '''subárboles''' de la raíz.
+** [[Árbol AVL|Árboles AVL]]
+* [[Árbol-B|Árboles B]]
-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 <math>n+1</math> (a distancia <math>n+1</math> aristas de la raíz), se deben haber listado  todos los de nivel <math>n</math>. Otros recorridos típicos del árbol son '''preorden''', '''postorden''' e '''inorden''':
+** [[Árbol-B+]]
-* 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 <math>A_1, A_2 \dots A_k</math> en orden previo.
+** [[Árbol-B*]]
-* 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 <math>A_1</math>, luego la raíz y luego cada uno de los hijos <math>A_2 \dots A_k</math> en orden simétrico.
+* [[Árbol multicamino|Árboles Multicamino]]
-* El recorrido en '''postorden''', también llamado '''orden posterior''' consiste en recorrer en primer lugar cada uno de los hijos <math>A_1, A_2 \dots A_k</math> 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 los grafos|teoría de grafos]]. Un árbol es un grafo '''conexo''' y '''acíclico''' (ver también [[teoría de los grafos|teoría de grafos]] y [[Glosario en teoría de grafos]]).
-mplo de árbol (binario).]]
-*
 == Operaciones de árboles. Representación ==