Arboles y Redes

6.
1 Árboles
• Desde el punto de vista conceptual, un árbol es un objeto que comienza con una
raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las
cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja.
•Los árboles representan las estructuras no-lineales y dinámicas de datos más
importantes en computación. Dinámicas, puesto que la estructura árbol puede
cambiar durante la ejecución de un programa. No lineales, puesto que a cada
elemento del árbol pueden seguirle varios elementos.
6.1.1 Componentes y propiedades

 En la ciencia de la computación definimos un árbol como un conjunto de nodos y
líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es
un par de nodos ordenados, y a la secuencia de líneas se le denomina ruta (path).
 Además, los árboles tienen las siguientes propiedades:
1) Tienen un nodo al que se le llama raíz del árbol.
2) Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no
tiene ninguna).
3) Existe una ruta única del nodo raíz a todos los demás nodos del árbol.
4) Si hay una ruta <a, b>, entonces a “b” se le denomina ‘hijo’ de “a” y es el nodo raíz
de un subárbol.
Gráficamente puede representarse una estructura árbol de diferentes maneras y todas ellas
equivalentes:
 Arboles por diagrama de Venn:
• Arboles mediante un grafo:

Representación gráfica, características y propiedades de los árboles
 Nodos: Se le llama Nodo a cada elemento que contiene un Árbol.
 Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz.
 Nodo Padre: Se utiliza este término para llamar a todos aquellos nodos que tiene al menos
un hijo.
 Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.
 Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre
en común dentro de la estructura.
 Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran
en los extremos de la estructura.
 Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que además tiene al menos
un hijo.
EJEMPLOS
Los árboles además de los nodos tienen otras propiedades importantes que son utilizadas en
diferentes ámbitos los cuales son:
 Nivel:
Nos referimos como nivel a cada generación dentro del árbol. Por ejemplo, cuando a un
nodo hoja le agregamos un hijo, el nodo hoja pasa a ser un nodo rama, pero además el árbol
crece una generación por lo que el Árbol tiene un nivel más. Cada generación tiene un
número de Nivel distinto que las demás generaciones.
1. Un árbol vacío tiene 0 niveles

2. El nivel de la Raíz es 1
3. El nivel de cada nodo se calculado contando cuantos nodos existen sobre el, hasta
llegar a la raíz + 1, y de forma inversa también se podría, contar cuantos nodos
existes desde la raíz hasta el nodo buscado + 1.
 Orden:
El Orden de un árbol es el número máximo de hijos que puede tener un Nodo.
Notemos que un Árbol con Orden = 1 no tendría sentido ya que sería una estructura lineal.
ya que cada nodo solo podría tener un Hijo.
Este valor no lo calculamos, si no que ya lo debemos conocer cuando diseñamos nuestra

estructura, ya que si queremos calcular esto lo que obtendremos es el grado.
 Grado:
El grado se refiere al número mayor de hijos que tiene alguno de los nodos del Árbol y esta
limitado por el Orden, ya que este indica el número máximo de hijos que puede tener un
nodo.
El grado se calcula contando de forma recursiva el número de hijos de cada sub-árbol hijo y
el número de hijos del nodo actual para tomar el mayor, esta operación se hace de forma
recursiva para recorrer todo el árbol.
grado = max(contarHijos(hijo1), contarHijos(hijo2), contarHijos(hijoN), contarHijos(this))

 Sub-Árbol:
Conocemos como Sub-Árbol a todo Árbol generado a partir de una sección determinada del
Árbol, Por lo que podemos decir que un Árbol es un nodo Raíz con N Sub-Árboles.
Existen escenarios donde podemos sacar un Sub-Árboles del Árbol para procesarlo de forma
separada, de esta forma el Sub-Árboles pasa a ser un Árbol independiente, También
podemos eliminar Sub-Árboles completos, Agregarlos, entre otras operaciones.
6.1.2 Clasificación árbol (Altura, número de nodos)
• Altura:
Le llamamos Altura al número máximo de niveles de un Árbol.
La altura es calculada mediante recursividad tomando el nivel más grande de los dos sub-árboles de
forma recursiva de la siguiente manera:
altura = max(altura(hijo1), altura(hijo2), altura(hijoN)) + 1
•Número De Nodos
Un árbol estrictamente binario con n hojas siempre contiene 2n - 1 nodos. El nivel de un nodo en
árbol binario se define del modo siguiente: la raíz del árbol tiene el nivel 0, el nivel de cualquier
otro nodo en el árbol es uno más que el nivel de su padre.
Si un árbol binario contiene m nodos en el nivel I, contiene cuando mucho 2m nodos en el nivel I
+ 1. Dado que un árbol binario solo contiene un nodo en el nivel 0 (raíz), puede contener un
máximo de 2I nodos en el nivel I. Un árbol binario completo de profundidad d es el árbol que
contiene 2I nodos en el nivel I entre 0 y d. La cantidad total de nodos en un árbol binario
completo de profundidad d, tn es igual a la suma de la cantidad de nodos en cada nivel entre 0
yd.
Un árbol binario de profundidad d es un árbol binario casi completo si:

Cualquier nodo nd a un nivel menor que d - 1tiene 2 hijos.
Para cualquier nodo nd en el árbol con un descendiente derecho en el nivel d, nd debe tener 1
hijo izquierdo y cada descendiente izquierdo de nd es una hoja en el nivel d o tiene 2 hijos.
Los nodos de un árbol binario casi completo se enumeran para que se asigne a la raíz el No.1,
se asigne a un hijo izquierdo 2 veces el número asignado a su padre y se asigne a un hijo
derecho 1 más el doble del No. asignado a su padre. Un árbol estrictamente binario casi
completo con n hojas tiene 2n - 1nodos, como cualquier otro árbol estrictamente binario con n
hojas. Un árbol binario casi completo con n hojas que no es estrictamente binario tiene 2n
nodos.
Solo hay un árbol binario casi completo con n nodos. Este árbol es estrictamente binario si y
solo si n es impar.

Arboles y Redes

Cargado por

Copyright:

Formatos disponibles

Arboles y Redes

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Arboles y Redes

Cargado por

Copyright:

Formatos disponibles

6.

6.1.1 Componentes y propiedades

 Arboles por diagrama de Venn:

• Arboles mediante un grafo:

1. Un árbol vacío tiene 0 niveles

Este valor no lo calculamos, si no que ya lo debemos conocer cuando diseñamos nuestra

grado = max(contarHijos(hijo1), contarHijos(hijo2), contarHijos(hijoN), contarHijos(this))

Le llamamos Altura al número máximo de niveles de un Árbol.

altura = max(altura(hijo1), altura(hijo2), altura(hijoN)) + 1

Un árbol binario de profundidad d es un árbol binario casi completo si:

También podría gustarte