Blog del sitio: Tecnológico

Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...121   ()
Perfil
de Carlos Andres Cogollo Melendez - miércoles, 11 de junio de 2014, 17:32
Todo el mundo

SUBCLASIFICACION DE ARBOLES:

Arboles Binarios

Un árbol binario es un árbol en donde cada nodo posee 2 referencias a subárboles. En general, dichas referencias se denominan izquierda y derecha, se define el subárbol izquierdo y subárbol derecho del árbol.

1. Terminologia:

Binario

Completo: Todos los nodos tienen dos hijos excepto las hojas.

Balanceado: Para todo los nodos, la diferencia entre las alturas del subarbol izquierdo y derecho es menor de dos.

Lleno: Todos los niveles del árbol tiene el maximo de nodos. ( 2 ^ h - 1 Cantidad total de nodos del árbol)

Degenerado: Todos los nodos tienen solo un hijo excepto las hojas. 

 

2. Implementacion:

-vectores:

vectores

 

-Nodo Arbol Binario:

nodo

 

d

 

3. Recorridos:

Recorridos

Combinación de actividades para visitar todos los nodos y hacer las respectivas operaciones.

 Actividades (Reccursivas)

1. Visitar raiz

2. Recorrer SubArbol izquierdo ( R )

3. Recorrer SubArbol derecho ( R )

 

 

 

 
Perfil
de Carlos Andres Cogollo Melendez - miércoles, 11 de junio de 2014, 17:15
Todo el mundo

Árbol

Es una estructura de datos, no lineal en la que cada nodo puede apuntar a uno o varios nodos, este empieza con una raíz y se extiende en varias ramas.


Propiedades

 

  • Tienen un nodo llamado raíz del árbol.
  • Todos los nodos, excepto la raíz, tienen una sola línea de entrada.
  • Existe una ruta única del nodo raíz a todos los demás nodos del árbol.
  • Nodo raíz de un subárbol.

 

 

Gráfica de un Árbol

 

   Arbol


*Nodo raiz: No tiene ascendentes

*Nodo interno: Tiene tanto descendentes como ascendentes

*Nodo hoja: No tiene descendentes

*Subgrupo: Nodo de sus descendientes

*Rama: Camino desde la raiz hasta una hoja

*Altura (3): Cantidad de niveles

*Peso (7): Cantidad de hojas

*Orden (10): Cantidad de nodos

 

Implementación de un Árbol

1. Arreglos:

Arreglo

 

2. Nodo:

Nodo

 

 

[ Modificado: miércoles, 11 de junio de 2014, 17:16 ]
 
Todo el mundo

Documento word

[ Modificado: miércoles, 11 de junio de 2014, 21:17 ]
 
Imagen de jeyner pinedo palacio
de jeyner pinedo palacio - miércoles, 11 de junio de 2014, 16:58
Imagen de Roger De Jesus Muñoz Villalobos
de Roger De Jesus Muñoz Villalobos - miércoles, 11 de junio de 2014, 16:44
Todo el mundo
  • ¿Que Son?

Son arboles Binarios ABB mejorados que proveen un algoritmo de auto balanceo.

  • Criterios de autobalanceo por Altura

Factor de equilibrio

FE= hsd-hsi

hsd= altura subárbol derecho

hsi= altura subárbol izquierdo

Para todos los Nodos

Si(FE > -2 y FE < 2)

Árbol balanceado

Si no

Arbol no balanceado

Fin si

 

  • Operaciones AVL

Inserccion: Primero es el proceso ABB, pero adicionalmente se calcula en cada inserccion el FE Iniciando 

en la hoja insertado siguiendo la rama hasta la raiz, se pueden presentar los sigueintes casos.

1ro Llegar a la raiz

2do El FE=0 en algun nodo diferente a la hoja

3ro El FE muestra que hay desbalance, en este caso se resstructura el arbol en un proceso lladao rotacion.

Rotaciones

- Rotacion II ( izquierda - izquierda)

 

- Rotacion DD (derecha derecha)

-Rotacion ID (izquierda derecha)

-Rotacion DI

 

Eliminacion:

se aplica inicialmente la misma regla ABB, pero adicional mente se calcula el FE en la rama de la eliminación, si se detecta desbalance, se reestructura el árbol dependiendo del caso de rotación.

 

 Reflexion:

Los arboles AVL proponen un algoritmo que reestructura el árbol para recuperar su balance perdido en operaciones de inserción y eliminación.

 

 

 

 

 

 

[ Modificado: miércoles, 11 de junio de 2014, 16:51 ]
 
Imagen de jeyner pinedo palacio
de jeyner pinedo palacio - miércoles, 11 de junio de 2014, 16:38
Imagen de jeyner pinedo palacio
de jeyner pinedo palacio - miércoles, 11 de junio de 2014, 16:27
Imagen de Jean Carlos Robles Atencia
de Jean Carlos Robles Atencia - miércoles, 11 de junio de 2014, 16:25
Todo el mundo

ARBOLES ABB: permite ordenamiento y eficiencia en el proceso de busqueda mucho mejor que la estructuras antes vistas (arreglos, listas enlazadas)

 

Operaciones: 

*insercion: para insertar, para los nodos, para claves en subarbol derecho mayores. la insercion se hace en la misma forma en que se consiguen las claves

ejemplo: 7, 3, 10, 5, 2, 9, 1, 4

 

*eliminar  

1. hoja :simplemente se suprime 

2. nodo con un subarbol: remplazando por su descendiente inmediato 

3. nodo con los subarboles: remplazado pro su descendiente mas a la izquierda del subarbol derecho por el descendiente mas a la derecha del subarbol izquierdo

 

ARBOLES AVL: arboles binarion abb mejorados, ya que proveen un algoritmo de autobalancel que evita la tendencia degenerada en las operaciondnes de insercion y eliminacion 

 

 CRITERIO DE BALANCEO POR ALTURA 

 

OPERACION DE AVAL 

INSERCION:inicialmente el mismo proceso ABB, pero adicionalmente se calcula en cada insercion el FE iniciando en la hoja insertada siguiendo la rama hasta la raiz, se puede presentar los sieguentes casos:

1. llegar a la raiz 

2. el FE= 0 en algun nodo diferente de la hoja 

3. el fe muestra que hay desbalance, en este caso se restructura el arbol en un proceso llamado notacion que puede ser de los siguientes tipos :

 

Rotacion 

II= Izquierda-Izquierda

Insertar: C,B,A

DD: Derecha-Derecha

Insertar : A,B,C

ID IZQUIERDA-DERECHA

INSERTAR: C,A,B

DI DERECHA-IZQUIERDA

INSERTAR: 3,7,1,4,8,9,12,24,33,44,25,11,10,6,2

 

 

 

REGLAS PARA ELIMINAR:

Se aplica la misma regla ABB, se calcula el factor de equilibrio en la rama donde se elimina el nodo si hay desbalance se aplica en tipo de rotacion.

[ Modificado: miércoles, 11 de junio de 2014, 17:46 ]
 
Imagen de JHONATAN LEANDRO CORREA MEJIA
de JHONATAN LEANDRO CORREA MEJIA - miércoles, 11 de junio de 2014, 16:11
Todo el mundo

ARBOL DE EXPRESIONES

 

 

arboles binarios que se usan para evaluar expresiones aritmeticas en estos arboles las hojas son los operandos y el resto de nodos los operadores 

 

 

NOTA: el recorrido  en preorden de un arbol de expresion produce la  prefija de la expresion 

ARBOLES ABB

permiten ordenamiento y eficiencia en el proceso de busqueda mucho mejor que las estructuras antes vistas ( arreglos, listas enlazadas) mientras mas crece la estructura de arboles de busqueda hace la busqueda mas eficiente tambien al hacer un recorrido en inorden

 

 

OPERACIONES

 

INSERCCION: para insertar par alos nodos las claves en el subarbol izquierdo deben ser menores y las del subarbol derecho mayores la inserccion se hace en la misma forma en que se consiguen las claves

 EJEMPLO

 

ELIMINAR 

  • 1 HOJA:  simplemente se suprime
  • NODO CON UN SUBARBOL: es reemplazado por su descendiente inmediato
  • NODO CON DOS SUBARBOL:  es reemplazado por e descendienre mas a la izquierda del subarbol derecho o por el descendiente as ala derecha del subarbol izquierdo

 

ARBOLES AVL 

arboles abb mejorados ya uqe proveen un algoritmo de auto balanceo que evita la tendencia degenrada enlas operaciones de inserccion y eliminacion

FACTOR DE EQUILIBRIO

FE=hsd-hsi

si( FE>-2 & FE<2)

arbol balanceado

sino 

arbol no balanceadp

fin si

 

OPERACIONES EN AVL 

INSERCCION: inicialmente el mismo proceso de abb pero adicionalmente se calcula en cada inserccion al fe inicial en la hoja insertada siquiendo  la rama hasta la raiz se puden presentar los siquientes casos 

  • llega a al raiz
  • el fe = 0 en algun nodo diferente a la hoja 
  • el fe muestra que hay desbalance en este caso se reestructura el arbol en un proceso llamado rotacion que puede se de los siquientes tipos

 

 

 

 

 

 

 

 

 

 
Imagen de JHONATAN LEANDRO CORREA MEJIA
de JHONATAN LEANDRO CORREA MEJIA - miércoles, 11 de junio de 2014, 16:11
Todo el mundo

ARBOL DE EXPRESIONES

 

 

arboles binarios que se usan para evaluar expresiones aritmeticas en estos arboles las hojas son los operandos y el resto de nodos los operadores 

 

 

NOTA: el recorrido  en preorden de un arbol de expresion produce la  prefija de la expresion 

ARBOLES ABB

permiten ordenamiento y eficiencia en el proceso de busqueda mucho mejor que las estructuras antes vistas ( arreglos, listas enlazadas) mientras mas crece la estructura de arboles de busqueda hace la busqueda mas eficiente tambien al hacer un recorrido en inorden

 

 

OPERACIONES

 

INSERCCION: para insertar par alos nodos las claves en el subarbol izquierdo deben ser menores y las del subarbol derecho mayores la inserccion se hace en la misma forma en que se consiguen las claves

 EJEMPLO

 

ELIMINAR 

  • 1 HOJA:  simplemente se suprime
  • NODO CON UN SUBARBOL: es reemplazado por su descendiente inmediato
  • NODO CON DOS SUBARBOL:  es reemplazado por e descendienre mas a la izquierda del subarbol derecho o por el descendiente as ala derecha del subarbol izquierdo

 

ARBOLES AVL 

arboles abb mejorados ya uqe proveen un algoritmo de auto balanceo que evita la tendencia degenrada enlas operaciones de inserccion y eliminacion

FACTOR DE EQUILIBRIO

FE=hsd-hsi

si( FE>-2 & FE<2)

arbol balanceado

sino 

arbol no balanceadp

fin si

 

OPERACIONES EN AVL 

INSERCCION: inicialmente el mismo proceso de abb pero adicionalmente se calcula en cada inserccion al fe inicial en la hoja insertada siquiendo  la rama hasta la raiz se puden presentar los siquientes casos 

  • llega a al raiz
  • el fe = 0 en algun nodo diferente a la hoja 
  • el fe muestra que hay desbalance en este caso se reestructura el arbol en un proceso llamado rotacion que puede se de los siquientes tipos

 

 

 

 

 

 

 

 

 

[ Modificado: miércoles, 11 de junio de 2014, 16:11 ]
 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...121   ()