Árboles

Equipo 8 “Arboles”

Grupo 18

8.1 INTRODUCCION
Una de las principales aplicaciones las realizo Gustav Kirchhoff en 1847 y lo utilizo en la manipulación de redes eléctricas. Posteriormente fue Grace Harper en 1951 al utilizarlos en expresiones matemáticas.
El principal problema de un grafo dentro de la computación es que no guarda una estructura establecida y no respetan reglas, ya que larelación entre nodos puede ser compleja. En cambio se utilizan grafos con características que permiten un mejor tratamiento de la información y se conocen como arboles.

Árbol
Es un grafo conexo que no tiene ciclos, lazos ni lados paralelos.

6.2 Propiedades de los arboles

Propiedades básicas de los arboles

Las propiedades básicas de los arboles son las siguientes: A) Es un grafoconvexo en donde existe un camino entre cualquier par de vértices (w, x). B) Este grafo no tiene ciclos ni lados paralelos. C) Todo árbol con al menos dos vértices tiene al menos una hoja (si se considera el otro vértice la raíz).

•

Un árbol esta compuesto por: Nodos: Son los vértices Ramas: Los lados Padre: un nodo de mayor nivel que el nodo al que esta vinculado. Hojas: Elementos (vértices)que están en las puntas de las ramas, es decir no tienen hijos Descendientes: Son todos los elementos colocados debajo de un nodo. Antecesores: Son los elementos colocados en una misma línea de descendencia, antes de un nodo. Vértices internos: Son todos aquellos que no son hojas

Búsquedas
Se puede considerar que uno de los usos principales de la computadora es guardar la información paradespués recuperarla en el orden deseado y en forma rápida. Para ello es necesario guardar las datos de forma que sea posible acceder a ellos en un tiempo razonable y para ello se utilizan arboles de búsqueda binarios (ABB), arboles AVL y arboles B.

8.3 Tipos de Arboles.
Los arboles se pueden clasificar de acuerdo a su numero de nodos y en función a su altura.

8.3.1 Clasificación por numero denodos.
En este caso los arboles pueden ser binarios (cada nodo padre tiene uno dos hijos máximo, trinarios (cada nodo padre tiene máximo tres hijos) etcétera.

Árbol Binario.
• Los arboles binarios son especialmente importantes en el área de la computación ya que por su naturaleza de tener solamente dos valores(0,1), o bien falso o verdadero, son muy útiles en aplicaciones de sistemasdigitales.

8.3.2 Clasificación por altura.
De acuerdo con este criterio los arboles pueden ser balanceados (Cuando la diferencia de altura entre sus ramas es máximo 1) y des balanceados (Cuando la diferencia de altura entre las ramas es mayor de 1)

8.4 Bosques
Bosque: conjunto de arboles Árbol: es un bosque conectado De un árbol se pueden obtener varios subárbol es, mismos que conforman unbosque. A su vez un árbol puede considerarse como un bosque conectado , solo se debe tener en cuenta que el árbol mas pequeño esta integrado por cuando menos dos nodos conectados por una arista.

árbol conexo que no tiene ciclos no es árbol porque tiene ciclos

Árbol: grafo conexo que no tiene ciclos, ni lazos, ni lados paralelos, esta compuesto por niveles Y el mas alto de la jerarquía se lellama raíz.
Raíz: tiene 2 niveles 0, los verticales inmediatamente debajo de la raíz tienen un nivel 1 y sucesivamente. La altura o peso de un árbol es el valor de su nivel mas bajo. Los elementos que están en las puntas de los arboles se les llaman hojas . A todos los elementos colocados debajo de un nodo se le llama descendiente.

Los elementos colocados en una misma línea de descendenciaantes de un nodo se les llama antecesores.
Se les llama verticales internos a todos aquellos que no son hojas . Los arboles se pueden clasificar de acuerdo al numero de nodos en: binario , trinarios, cuaternario, etc. Y de acuerdo a la altura en balanceados y des balanceados.
Árbol generador: aquel que permite mantener unidos a todos los vértices y que no tiene ciclos Recorrido en arboles...