martes, 7 de junio de 2011

Arboles



El árbol es una estructura de datos fundamental en la informática, muy utilizada en todos sus campos, por que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación.
La definición de un árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz.

-----Nodo:
Un nodo es un punto de intersección o unión de varios elementos que confluyen en el mismo lugar.


-----Árboles Binarios:
Existe un tipo de árbol denominado árbol binario que puede ser implementado fácilmente en una computadora.
Un árbol binario es un conjunto finito de cero o más nodos tales que:
-Existe un nodo denominados raíz del árbol.
-Cada nodo puede tener 0, 1 o 2 subárboles, conocidos como subárbol izquierdo y subárbol derecho.
-Y estos no pueden tener más de dos hijos (de ahí el nombre "binario")



-----Arboles AVL:
Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus
nodos es, como mucho 1.
Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n).
El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Arboles

Árboles Binarios

Dispersión

La dispersión es una técnica para hacer inserciones, eliminaciones y búsquedas en un tiempo Constante
Un ejemplo de esto seria un diccionario, que busca los objetos por una clave, y su definición es lo que se devolveria.


La funcion de la dispersion es asegurarse que 2 claves distintas caigan en celdas diferentes.



Algunas veces dos claves caen en el mismo valor y se genera una colision, la cual tiene tambien un método para resolverse

Dispersion hash

Dipersion Hash

Procesamiento secuencial coordinado


Es el procesamiento coordinado de dos o más listas secuénciales para producir una única lista de salida.
Las operaciones secuenciales coordinadas implican el procesamiento coordinado de dos o más listas secuenciales para producir una única lista de salida.
Algunas veces el procesamiento produce una intercalación (merging) o union de las listas de entrada.

Algunas veces el objetivo es una correspondencia (matching) o intersección.
Otras veces es una combinación de intercalación y correspondencia.
Este tipo de operaciones secuenciales son la base de gran parte del procesamiento de archivos.
Parecen sencillas las operaciones. Puede ser asi, pero frecuentemente son confusos, pobremente organizados e incorrectos.

Procesamiento secuencial coordinado

Procesamiento coordinado