Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Arboles Multicaminos

No description
by

adair araque

on 16 September 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Arboles Multicaminos

TEORIA DE GRAFOS Ingenieria de Sistemas
Universidad de Cordoba Integrantes:
Stepanny Suarez
Aida Villadiego
Adair Araque Conceptualización Definición Tipos de Árboles Multicaminos Ventajas e inconvenientes Árboles B+ Características Los árboles m-arios de búsqueda son árboles multicamino (aquellos en los que cada nodo puede tener más de dos descendientes directos) cuyas ramas están ordenadas a modo de un árbol binario de búsqueda.

En un árbol multicamino, de grado M, cada nodo interno puede tener como máximo M nodos descendientes, y puede almacenar como máximo M-1 claves ordenadas.

La información se almacena de forma organizada en archivos, en dispositivos de alamcenamiento secundario. Árboles Multicaminos Características Cada nodo tiene hasta m hijos y guarda hasta m-1 elementos (número de hijos <= (número de elementos +1)).

Los valores guardados en un nodo están en orden ascendente.

Los valores de los primeros i hijos de A son menores que el elemento iésimo guardado en A.

Los valores de los últimos m-i hijos de A son mayores que el elemento iésimo guardado en A. Ventajas e Inconvenientes La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos.

El inconveniente más importante que tienen es la mayor ocupación de memoria, pudiendo ocurrir que en ocasiones la mayoría de los nodos no tengan descendientes o al menos no todos los que podrían tener desaprovechándose por tanto gran cantidad de memoria. Cuando esto ocurre lo más frecuente es transformar el árbol multicamino en su binario de búsqueda equivalente. Se han convertido en la técnica mas utilizadas para la organización de archivos indizados. Es de notar que los arboles B+ ocupan un poco mas de espacio que los arboles B. Árboles B+ 1. Cada página, excepto la raíz, contiene entre d y 2d elementos.
2. Cada página, excepto la raíz, tiene entre d+1 y 2d+1 descendientes.
3. La pagina raíz tiene al menos dos descendientes.
4. Las páginas hojas están todas al mismo nivel.
5. Todas las claves se encuentran en las páginas hojas.
6. Las claves de las páginas raíz e interiores se utilizan como índice. Formalmente se define un árbol B+ así: Operaciones con Árboles B+

- Inserción.
- Búsqueda.
- Borrado. Inserción insertamos la clave 13 Búsqueda Búscamos la clave 55 Borrado Eliminamos la clave 25 Árboles B Generalización de arboles balanceados.
Bayer y Mc Creight 1970.
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades:
Cada nodo tiene como máximo M hijos.
Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.
La raíz tiene al menos 2 hijos si no es un nodo hoja.
Todos los nodos hoja aparecen al mismo nivel.
Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:
El primero tiene valor menor que r1.
El segundo tiene valor mayor que r1 y menor que r2, etc.
El último hijo tiene valor mayor que rm. Inserción en Árboles B Busquedas en Árboles B 1. Debe tenerse en memoria la página sobre la cual vamos a trabajar.
Si página <> null
entonces
se avanza hacia el paso 2
sino
se avanza hacia el paso 3 2. Debe especificarse la clave a buscar. Si la clave se encuentra en la página
entonces
EXITO !
sino
se debe tener en cuenta los siguientes pasos
Si X <CL1 entonces
debe localizarse PAG0
Si CLi < X > CLm entonces
debe localizarse PAGi
Si X >CLm entonces
debe localizarse PAGm
Regresar al paso 1. 2. Debe especificarse la clave a buscar. 3. FRACASO !. Borrado en Árboles B Eliminemos la clave 65. Es uno de los casos más sencillos, la clave está en un nodo hoja, y el número de claves del nodo después de eliminarla es mayor del mínimo http://usuarios.multimania.es/arbolesbpro/aplicacion/ArbolB.html Eliminemos la clave 20. debemos sustituir la clave por el siguiente valor osea el 25. Árboles Multicaminos Conceptualización Árboles B La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B. El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentre en un nodo raíz o interior, en dicho caso no debe detenerse el proceso, sino que debe continuarse la búsqueda con el nodo apuntado por la rama derecha de dicha clave. El proceso de inserción en árboles-B+ es relativamente simple, similar al proceso de inserción en árboles-B. La dificultad se presenta cuando desea insertarse una clave en un nodo que se encuentra lleno. En este caso, el nodo afectado se divide en 2, distribuyéndose las claves de la siguiente forma: " las p/2 primeras claves en el nodo de la izquierda y las p/2 + 1 restantes claves en el nodo de la derecha". Una copia de la clave del medio sube al nodo padre. Si al eliminar una clave, la cantidad de llaves queda mayor o igual que p/2 entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas.

Si al eliminar una clave, la cantidad de llaves queda menor que p/2 entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas. Gracias !!
Full transcript