Arboles-informatica
Páginas: 19 (4706 palabras)
Publicado: 10 de marzo de 2011
5. Árboles
5.1 Conceptos básicos
Los árboles son una de las estructuras de datos no lineales más utilizada. Sirve para representar estructuras de información jerárquicas y direcciones o etiquetas de una manera organizada.
Dentro de la ciencia de la computación, los árboles tienen muchas aplicaciones como por ejemplo:
• organizar tablas de símbolos en compiladores
•representar tablas de decisión
• asignar bloques de memoria de tamaño variable
• ordenar
• buscar
• solucionar juegos
• probar teoremas
Como objetos matemáticos los árboles también han sido estudiados ampliamente.
Los árboles permiten representar situaciones de la vida diaria como son:
• organización de una empresa
• árbol genealógico de una persona
•organización de torneos deportivos
Definición: Un árbol es un conjunto finito T de uno o más nodos tal que:
a) Existe un nodo especial llamado la raíz de árbol
b) Los nodos restantes están particionados en m > 0 conjuntos disjuntos T1,...,Tm y cada uno de estos conjuntos es a su vez un árbol. Los árboles T1,...,Tm son llamados subárboles de la raíz
Cualquier nodo es la raíz de unsubárbol que consiste de él y los nodos debajo de él. Esto se deriva de la definición recursiva de árbol presentada.
Un árbol puede representarse gráficamente de muchas formas. Algunas de ellas son por medio de:
• conjuntos anidados:
[pic]
• paréntesis anidados.
(1(2(4(9,10,11),5),3(6(12),7,8)))
• indentación
[pic]
• grafos
[pic]
La forma más común de representar a losárboles es por medio de un grafo con la raíz hacia arriba:
[pic]
Cada vértice o nodo del árbol puede tener un nombre y puede tener una información asociada; un arco es una conexión entre dos vértices.
Un camino en un árbol es una lista de vértices diferentes en los que vértices sucesivos están conectados por arcos en el árbol. Una propiedad que define a los árboles es que existe exactamenteun camino entre la raíz y cada uno de los otros nodos en el árbol.
La longitud de un camino es el número de nodos del camino menos uno. Por tanto, hay un camino de longitud cero de cualquier nodo a si mismo.
Se dice que un nodo Y está abajo de un nodo X, si X está en el camino de Y a la raíz. Además, cada nodo, excepto la raíz, tiene exactamente un nodo arriba de él, que es llamado su padre;los nodos que están exactamente abajo de él son llamados sus hijos.
El número de hijos que cuelgan de un nodo es llamado el grado del nodo. El grado de un árbol es el grado máximo de los nodos del árbol. Un nodo de grado cero es llamado hoja, es decir, no tiene hijos.
Ejemplo:
Considere el siguiente árbol:
[pic]
Figura 1
El camino del nodo A al nodo P es (A, B, D, J, P), cuyalongitud de camino es 4. E es el padre de K y L.
Los hijos de G son M, N y O.
Los nodos de grado 0 son: I, P, K, L, F, M, N, O, P y H es decir son las hojas del árbol.
El único nodo de grado 1 es J.
Los nodos de grado 2 son A, B, D y E.
Los nodos de grado 3 son C y G.
No existen nodos de mayor grado, por tanto, el grado del árbol es 3.
Los nodos de un árbol pueden dividirse enniveles; el nivel de un nodo es el número de nodos en el camino de él a la raíz. La altura de un árbol es el nivel máximo de todos los nodos en el árbol, es decir, la distancia máxima de la raíz a cualquier nodo.
Ejemplo:
A continuación se muestra el nivel de cada nodo del árbol de la figura 1:
[pic]
De lo anterior, se ve que el árbol es de altura 4.
A veces la forma en la cual los hijosde cada nodo están ordenados es importante. Un árbol ordenado es aquel en el cual el orden de los hijos de cada nodo está especificado.
Un conjunto de árboles es llamado un bosque. Existe una pequeña diferencia entre un árbol y un bosque; si se elimina la raíz de un árbol se obtiene un bosque, y, recíprocamente, si se añade un nodo a un bosque se obtiene un árbol.
¿Qué es un árbol de...
5.1 Conceptos básicos
Los árboles son una de las estructuras de datos no lineales más utilizada. Sirve para representar estructuras de información jerárquicas y direcciones o etiquetas de una manera organizada.
Dentro de la ciencia de la computación, los árboles tienen muchas aplicaciones como por ejemplo:
• organizar tablas de símbolos en compiladores
•representar tablas de decisión
• asignar bloques de memoria de tamaño variable
• ordenar
• buscar
• solucionar juegos
• probar teoremas
Como objetos matemáticos los árboles también han sido estudiados ampliamente.
Los árboles permiten representar situaciones de la vida diaria como son:
• organización de una empresa
• árbol genealógico de una persona
•organización de torneos deportivos
Definición: Un árbol es un conjunto finito T de uno o más nodos tal que:
a) Existe un nodo especial llamado la raíz de árbol
b) Los nodos restantes están particionados en m > 0 conjuntos disjuntos T1,...,Tm y cada uno de estos conjuntos es a su vez un árbol. Los árboles T1,...,Tm son llamados subárboles de la raíz
Cualquier nodo es la raíz de unsubárbol que consiste de él y los nodos debajo de él. Esto se deriva de la definición recursiva de árbol presentada.
Un árbol puede representarse gráficamente de muchas formas. Algunas de ellas son por medio de:
• conjuntos anidados:
[pic]
• paréntesis anidados.
(1(2(4(9,10,11),5),3(6(12),7,8)))
• indentación
[pic]
• grafos
[pic]
La forma más común de representar a losárboles es por medio de un grafo con la raíz hacia arriba:
[pic]
Cada vértice o nodo del árbol puede tener un nombre y puede tener una información asociada; un arco es una conexión entre dos vértices.
Un camino en un árbol es una lista de vértices diferentes en los que vértices sucesivos están conectados por arcos en el árbol. Una propiedad que define a los árboles es que existe exactamenteun camino entre la raíz y cada uno de los otros nodos en el árbol.
La longitud de un camino es el número de nodos del camino menos uno. Por tanto, hay un camino de longitud cero de cualquier nodo a si mismo.
Se dice que un nodo Y está abajo de un nodo X, si X está en el camino de Y a la raíz. Además, cada nodo, excepto la raíz, tiene exactamente un nodo arriba de él, que es llamado su padre;los nodos que están exactamente abajo de él son llamados sus hijos.
El número de hijos que cuelgan de un nodo es llamado el grado del nodo. El grado de un árbol es el grado máximo de los nodos del árbol. Un nodo de grado cero es llamado hoja, es decir, no tiene hijos.
Ejemplo:
Considere el siguiente árbol:
[pic]
Figura 1
El camino del nodo A al nodo P es (A, B, D, J, P), cuyalongitud de camino es 4. E es el padre de K y L.
Los hijos de G son M, N y O.
Los nodos de grado 0 son: I, P, K, L, F, M, N, O, P y H es decir son las hojas del árbol.
El único nodo de grado 1 es J.
Los nodos de grado 2 son A, B, D y E.
Los nodos de grado 3 son C y G.
No existen nodos de mayor grado, por tanto, el grado del árbol es 3.
Los nodos de un árbol pueden dividirse enniveles; el nivel de un nodo es el número de nodos en el camino de él a la raíz. La altura de un árbol es el nivel máximo de todos los nodos en el árbol, es decir, la distancia máxima de la raíz a cualquier nodo.
Ejemplo:
A continuación se muestra el nivel de cada nodo del árbol de la figura 1:
[pic]
De lo anterior, se ve que el árbol es de altura 4.
A veces la forma en la cual los hijosde cada nodo están ordenados es importante. Un árbol ordenado es aquel en el cual el orden de los hijos de cada nodo está especificado.
Un conjunto de árboles es llamado un bosque. Existe una pequeña diferencia entre un árbol y un bosque; si se elimina la raíz de un árbol se obtiene un bosque, y, recíprocamente, si se añade un nodo a un bosque se obtiene un árbol.
¿Qué es un árbol de...
Leer documento completo
Regístrate para leer el documento completo.