Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Y otras organizaciones de archivos estructurados en forma de árbol ESTRUCTURA DE DATOS II /ÁRBOLES B 9.7 -9.12 # # # 9.7 - 9.12 “Son árboles equilibrados que permiten construir los árboles hacia arriba a partir de la base, en lugar de hacerlo hacia abajo desde la cima”. ● Evitan toda dificultad. ● Permiten que la raíz emerja, en vez de colocarla y después encontrar la manera de cambiarla. ¿Qué propone el árbol B? /Árboles B: construcción ascendente ESTRUCTURA DE DATOS II Problema anterior ● Se requiere que el nodo raíz divida parejamente el conjunto de las otras llaves ○ Al tener raices incorrectas, se requiere pensar en algoritmos rebuscados de reacomodo. - ● ¿Cómo evitar que se agrupen llaves incorrectas en una página? ¿Cómo garantizar que una página tenga un número mínimo de llaves? # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 /División y promoción /9.8 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 /9.8 Componentes del árbol Nodo / Pagina ● Secuencia ordenada de llaves y un conjunto de apuntadores. ● Si existen K claves, existen K+1 apuntadores/hijos ● En donde K1 < K2 < K3 Orden / Grado ● Es el número máximo de apuntadores / hijos que pueden almacenarse en un nodo ○ Un árbol B de grado M puede tener M hijos y M-1 claves . ○ Los nodos tienen al menos M/2 hijos, menos la raíz que puede tener menos, incluso 1. ○ Los nodos tienen al menos M-1 claves, excepto la raíz. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Orden / Grado Ejemplos de árboles B de orden M M = 4 M = 3 3 llaves y 4 apuntadores 2 llaves y 3 apuntadores * * * * * * * # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Más sobre nodos y un ejemplo Figura 9.14 pagina 421 Nodo de orden 8: 7 llaves y 8 apuntadores A B C D E F G* * * * * * * * Los campos marcados con asteriscos (*) son los campos apuntadores. ● En este ejemplo, que es un nodo hoja, todos los apuntadores apuntan a -1 (posición inválida), indicando el final de la lista. En este caso, esta hoja también es la raíz. ● En la práctica los apuntadores también tienen información adicional, como una referencia al registro que contiene datos asociados con la llave, almacenado en otro lugar. ● La hoja inicial del árbol puede tener una estructura similar a esta. # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 1. Construir la primera hoja Cuando se insertan nuevas llaves, solo se usa un acceso al disco para transferir la página a memoria e insertar la llave en su lugar en la página. Al trabajar en memoria electrónica, la inserción resulta relativamente barata, comparada con el costo de los accesos adicionales al disco. /9.8 Cómo se crea el árbol A B C D E F G* * * * * * * * Se deben insertar llaves hasta llegar al máximo de llaves que se pueden tener de acuerdo al orden. Nodo de orden 8 con 7 claves # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 2. Agregar llaves nuevas Supóngase que se quiere insertar la llave J y se encuentra que el nodo ya está lleno (ya tiene 7 llaves). Se debe dividir el nodo anterior en 2 hojas distintas tan equitativamente como sea posible con las claves que se tenían. /9.8 Cómo se crea el árbol A B C D E F G* * * * * * * * *J Se verifica que la hoja ya excede su orden al insertar la J A B C D* * * * * * * * E F G J* * * * * * * * Se crean dos hojas separadas para acomodar la J Figura 9.15 pagina 422 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 3. Crecimiento del árbol Como ahora se tienen dos hojas, es necesario crear un nivel superior en el árbol para que, cuando se esté buscando una llave, se pueda elegir entre ellas. Es necesario crear una raíz nueva. Para ello, se promueve una llave que separe las hojas. /9.8 Cómo se crea el árbol En este caso, se promueve la E de la primera posición en la segunda hoja A B C D* * * * * * * * F G J* * * * * * * * Figura 9.16 pagina 422 E* * * * * * * * En este ejemplo la división y promoción se hace en dos pasos, pero en la práctica se hacen en una sola operación. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de cómo crece un árbol B Figura 9.17 y 9.18, páginas 423 y 424 Se quiere insertar la secuencia C S D T A M P I B W N G U R K E H O L J Y Q Z F X V en un árbol B de grado 4 C D S 1. Se inserta C, S, D en orden alfabetico C D S T 2. Se inserta T en orden alfabetico, identificamos que excede el orden y pomocionamos tercer llave S TC D 3. Se promueve la S, del lado izq van las letras antes de la S, y del derech., las letras que van después 0 0 0 1 2 Excede!! # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de un árbol B Figura 9.17 y 9.18, páginas 423 y 424 C S D T A M P I B W N G U R K E H O L J Y Q Z F X V 4. Se inserta la A en hoja existente y M S TA C D M0 1 2 5. Se promueve la D D S TA C 1 2 0 M 3 6. Se inserta P, I, B, W en hojas existentes y ND S T WA B C 1 2 0 I M N P 3 Excede!! Excede!! # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de un árbol B C S D T A M P I B W N G U R K E H O L J Y Q Z F X V 7. Se promueve N D N S A B C 1 2 0 I M 3 4 8. Se inserta G, U, R en las hojas existentes y K P T W D N S A B C 1 2 0 I G K M 3 4 P R T U W Excede!! 9. Se promueve K D K N S A B C 1 2 0 I G 3 4 P R T U W Excede!! M 5 # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de un árbol B C S D T A M P I B W N G U R K E H O L J Y Q Z F X V 10. Se promueve N, se inserta E en hojas existentes, y se inserta H D K A B C 1 2 0 3 4 P R T U W S N E G H I M 7 6 5 Excede!!Antes Figura 9.17 y 9.18, páginas 423 y 424 # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de un árbol B C S D T A M P I B W N G U R K E H O L J Y Q Z F X V Antes D H K A B C 1 2 0 3 4 O P R T U W Y S N E G L M 7 6 5 Excede!!11. Se promueve la H, se inserta O, L, J, en hojas existentes, y se inserta Y I J 8 Figura 9.17 y 9.18, páginas 423 y 424 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de un árbol B C S D T A M P I B W N G U R K E H O L J Y Q Z F X V Antes D H K A B C 1 2 0 3 4 O P Q R T U S W N E G L M 7 6 5 Excede!! 12. Se promueve la W, y se inserta la Q I J 8 Y 9 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Ejemplo de un árbol B C S D T A M P I B W N G U R K E H O L J Y Q Z F X V Antes D H K A B C 10 2 0 3 4 O P R Q S W N L M 7 6 5 13. Se promueve la Q , y se inserta la Z, F, X, V en hojas existentes I J 8 1 E F G T U V X Y Z 9 Figura 9.17 y 9.18, páginas 423 y 424 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Notese que… ● El árbol siempre está perfectamente balanceado con respecto a la altura; la trayectoria que va de la raíz a una hoja es la misma para todas las hojas. ● Las llaves que se promueven hacia arriba son necesariamente el tipo de llaves que se desean en la raíz. ● Al trabajar por encima del nivel de hoja, dividiendo y promoviendo conforme se llenan las páginas, se evitan los problemas que plagaron a los árboles binarios paginados. D H K A B C 10 2 0 3 4 O P R Q S W N L M 7 6 5 I J 8 1 E F G T U V X Y Z 9 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 /Algoritmos para la búsqueda e inserción en árboles B /9.9 # # # ESTRUCTURA DE LA PÁGINA. Existen formas diferentes de construir páginas de un árbol B. Parte de un árbol B. Árbol B de orden cuatro. Un nodo interno y 4 nodos hoja. Contenido de las páginas 2 y 3. La búsqueda es un buen punto para comenzar porque ilustra las características de la mayoría de los algoritmos para los árboles B: /9.9 Inserción, división y promoción ESTRUCTURA DE DATOS II Funcionan en dos estepas Operando en un forma alterna sobre las páginas enteras Y desde dentro de las páginas # # # # El procedimiento de búsqueda se llama así mismo para localizar una página y después busca en ella hasta que encuentra la llave por niveles de manera descendente hasta que ya no pueda descender más. /9.9 Inserción, división y promoción ESTRUCTURA DE DATOS II 5 3 7 641 8 # ## # FUNCION: busca (NRR, LLAVE, NRR_ENCONTRADO, POR_ENCONTRADA) Si NRR==NULO entonces Devuelve NO ENCONTRADA Otro Lee la página NRR en PÁGINA Busca LLAVE en PÁGINA, haciendo POS igual a la posición donde LLAVE este o debería estar, /9.9 Inserción, división y promoción ESTRUCTURA DE DATOS II FUNCION BUSQUEDA # # # # Si se encontró la LLAVE entonces NRR_ENCONTRADO:= NRR POS_ENCONTRADA := POS Devuelve ENCONTRADA Otro Devuelve (busca {PAGINA. HIJO[POS], LLAVE, NRR_ENCONTRADO. POS_ENCONTRADA}) Fin FUNCION /9.9 Inserción, división y promoción ESTRUCTURA DE DATOS II # # # # NO ENCONTRADA esta se devuelve en varios niveles de posiciones con return() hasta que la llamada busca() recibe la información de que no encontró la llave /9.9 Inserción, división y promoción ESTRUCTURA DE DATOS II # # # # Hay 2 observaciones importantes que pueden hacerse acerca del proceso de inserción, división y promoción: /9.9 Inserción, división y promoción En consecuencia, se puede pensar en el procedimiento recursivo con tres fases; ESTRUCTURA DE DATOS II □ Comienza con una búsqueda que llega abajo hasta el nivel de hoja, y □ Después de encontrar el lugar de inserción en el nivel hoja, el trabajo de inserción, división y promoción continúa en forma ascendente desde abajo. # # # # 1.- Un paso de búsqueda en páginas que, como en función buscaO, ocurre antes de llamada recursiva 2.- La llamada recursiva misma, que mueve la operación hacia abajo en el árbol conforme busca ya sea la llave o el lugar para insertarla, y 3.- La lógica de inserción, división y promoción que se ejecuta después de la llamada recursiva; la acción tiene lugar en la trayectoria de vuelta luego del descenso recursivo. ESTRUCTURA DE DATOS II /9.9 Inserción, división y promoción # # /9.9 Inserción ESTRUCTURA DE DATOS II Se necesita un ejemplo de una inserción para que pueda verse el trabajo del procedimiento de inserción a lo largo de estas fases. Se va a insertar el carácter $ dentro del árbol que se muestra en la mitad superior de la figura 9,22, que contiene todas las letras del alfabeto. D H K A B C O P R Q S W N L M I JE F G T U V X Y Z # # /9.9 Inserción Ahora se estudiará cómo la función insertaO realiza esta división y promoción. Puesto que la función opera en forma recursiva, es importante comprender cómo se usan en llamadas sucesivas los argumentos de la función. La función insertaO que se describe emplea cuatro argumentos: ESTRUCTURA DE DATOS II NRR_ACTUAL El NRR de la página del árbol B que se usa actualmente. Como la función desciende y asciende recursivamente en el árbol, se usan todos los NRR en la trayectoria de búsqueda e inserción. LLAVE La llave que se va a insertar. LLAVE_PROMO Argumento que se usa sólo para regresar el valor devuelto. Si de la inserción resultan una división y la promoción de una llave, LLAVE_PROMO contiene la llave promovida en el regreso ascendente del árbol HIJO_D_PROMO Este es otro valor de argumento devuelto. Si hay una # # /9.9 Diagrama La figura 9.23 ilustra la forma en que cambian los valores de estos argumentos cuando se llama a la función insertaO y ésta se llama a sí misma para efectuar la inserción del carácter $. La figura señala varios puntos importantes: ESTRUCTURA DE DATOS II ANTES DE $ DESPUES DE $ # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Función InsertaO ➢ Durante el paso de búsqueda de la inserción, mientras la función se llama a sí misma sólo NRR_ACTUAL cambia, haciendo el descenso en el árbol. ➢ El paso de búsqueda termina cuando NRR_ACTUAL es NULO; ya no existen niveles adicionales en donde se pueda buscar. ➢ Conforme regresa cada llamada recursiva, se ejecuta la lógica de inserción y división en ese nivel. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 ➢ Si la función de nivel inferior devuelve el valor PROMOCION, entonces se tiene una llave para insertar en este nivel. ➢ En caso contrario, no hay nada que hacer y sólo regresa. ➢ Una vez que se codifica la función insertaO emplea varias funciones de apoyo, una de ellas es divideO La cual crea una página nueva, distribuye las llaves entre una página original y la nueva. Además determina cuál llave y cuál NRR hay que promover. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Variables locales importantes. ➢ PAGINA: La página que de momento está examinando insertaO* ➢ PAGINA_NUEVA: La nueva página que se crea si ocurre una división. ➢ POS: La posición en PAGINA donde ocurre la llave (si está presente) u ocurriría (si se inserta). ➢ NRR_P_A: El número relativo de registro promovido desde abajo y hasta este nivel Si ocurre una división en el siguiente nivel inferior. ➢ PAGINA LLAVE_P_A La llave promovida desde abajo y hasta este nivel. Esta llave, junto con NRR_P_A, se inserta en PAGINA. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Pseudocodigo de función Inserta si NRR_ACTUAL - NULO entonces devuelve PROMOCION leer la página de NRR_ACTUAL en PAGINA r I V buscar la LLAVE en PAGINA POS: - la posición en donde esta debería estar LLAVE si se encuentra LLAVE entonces emitir mensaje de error indicando llave duplicada devuelve ERROR VALOR_DEVUELTO inserta (PAGINA.HIJO [POS], LLAVE, NRR_P_A, LLAVE_P_A) si VALOR_DEVUELT0 - - NO PROMOCION o ERROR entonces devuelve VALOR_DEVUELTO otro si hay espacio en PAGINA para LLAVE_P_A entonces insertar LIAVE_P_A y NRR_P_A (promovida desde abajo, en PAGINA devuelve NO PROMOCION otro divide (LLAVE_P_A, NRR_P___A, PAGINA, LLAVE_PR0M0, HIJ0_D PROMO, PAGINANUEVA) " escribe PAGINA al archivo en el NRR_ACTUAL escribe PAGINANUEVA al archivo en el nrr HIJO_D_PROM0 devuelve PROMOCION fin FUNCION La función PROMOCION dado que un nuevo índice ha sido creado en este nivel, la nueva llave debe ser insertada en el siguiente nodo con un nivel más alto. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Divide -Ocurre cuando al realizar una inserción nos percatamos que el nodo tiene más claves de lo permitido. -Se busca pivote que será la mediana de los elementos L -Trasladamos las claves e hijos mayores que L a un nuevo nodo y las retiramos del nodo viejo -Empujamos el pivote hacia arriba del arbol aunque este puede colapsar. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Divide # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Pseudocodigo “divide” PROCEDIMIENTO: divide (LLAVEI, NRRJ, PAGINA, LLAVE_PROMO, HIJO_D_PR0MO, PAGINANUEVA) copiar todas las llaves y apuntadores de PAGINA en una página de trabajo que puede almacenar una llave adicional y un hijo, insertar LLAVE_I y NRR_I en sus lugares correctos en la página de Trabajo. asignar e iniciar nueva página en el archivo del árbol B para que contenga PAGINANUEVA. asignar a LLAVE_PROMO el valor de la llave de enmedio, la cual será promovida después de la división. asignar a HIJO_D_PROM0 el NRR de PAGINANUEVA. copiar las llaves y apuntadores a los hijos que preceden a LIAVE_PR0MO, de la página de trabajo a PAGINA. copiar las llaves y apuntadores a los hijos que siguen a LLAVE PROMO, de la página de trabajo a PAGINANUEVA. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Pseudocodigo “Manejador” PROCEDIMIENTO PRINCIPAL: manejador si el archivo del árbol B existe, entonces abrir el archivo del árbol B otro crear un archivo de árbol B y colocar la primera llave en la raiz tomar el NRR de la página raiz del archivo y almacenarla en RAIZ tomar una llave y almacenarla en LLAVE mientras existan llaves si (inserta (RAIZ, LLAVE, HIJO_D_PROMO, LLAVE_PROMOJ — PROMOCION) Entonces crear una nueva página raiz con la llave : - fllJO_D__PROMO ■'/"¡ hijo izquierdo :- RAIZ e hijo derecho HIJO_D_PROMO asignar*T*AIZ el NRR de la nueva página raiz tomar la siguiente llave y almacenarla en LIAVE^fin mientras escribe el NRR almacenado en RAI2 de regreso al archivo del árbol B cerrar el archivo del árbol fin PROCEDIMIENTO PRINCIPAL # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 /Nomenclaturade árboles B. /9.10 # # # ● Antes de pasar al análisis del desempeño de los árboles B y a las variaciones sobre sus algoritmos básicos, es necesario formalizar la terminología sobre los árboles B. Orden de un árbol B: Es el mínimo número de llaves que pueden estar dentro de una página de un árbol. Bayer y McCreight [1972], Comer [1979] y algunos otros se refieren. Orden 3. Máximo de 7 llaves. Pero hay un problema con esta definición debido a que se vuelve difícil de aplicar cuando se toman en cuenta páginas que almacenan un número máximo de llaves que es impar. Hay que considerar considérese la siguiente pregunta: dentro del esquema de Bayer y McCreight, ¿la página de un árbol B de la orden tres está llena cuando contiene seis llaves o cuando contiene siete? Knuth [1973b] y otros han resuelto la confusión. Knuth [1973b] y otros definieron el orden de un árbol B como: El número máximo de descendientes que puede tener una página. 8 descendientes. 7 llaves. ● Un árbol B de orden 8 tiene un máximo de 7 llaves por página. ● Un árbol B de orden m, el número máximo de llaves por página es m -1 Defiere de Bayer y McCreight en dos aspectos: 1 Hace referencia a un máximo, no a un mínimo, y cuenta descendientes en vez de llaves. 2 El número de llaves en una página de árbol B siempre es uno menos que el número de descendientes de la página. Cuando se divide la página de un árbol B, los descendientes se dividen lo más equitativamente posible entre la página nueva y la vieja. En consecuencia, cada página, excepto la raíz y las hojas, tiene al menos m/2 descendientes. Expresado en términos de una función de redondeo hacia arriba: El mínimo número de descendientes es [m/2]. Se concluye que el mínimo número de llaves por página es [m/2-1]. El ejemplo es de orden ocho, significa: Que no puede almacenar más de siete llaves por página. Todas las páginas, excepto la raíz, contienen por lo menos tres llaves. ¿QUE ES UNA HOJA? Bayer y McCreight Otros autores, entre ellos Knuth • Las hojas están en un nivel por debajo del nivel más bajo de llaves. En otras palabras. • Consideran que las hojas son los registros de datos reales a los cuales puede apuntar el nivel más bajo de llaves del árbol. • Se refieren al nivel más bajo de llaves dentro de un árbol B como el nivel hoja. ESTRUCTURA DE DATOS II 9.7 - 9.12 /Definición formal de las propiedades de los árboles B /9.11 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 9.11 Propiedades del árbol B Con estas definiciones de orden y hoja puede formularse una definición precisa de las propiedades de un árbol B de orden m: 1. Cada página tiene un máximo de m descendientes. 2. Cada página, excepto la raíz y las hojas, tiene por lo menos [m/2] descendientes. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 9.11 Propiedades del árbol B 3. La raíz tiene por lo menos dos descendientes (a menos que sea una hoja). 4. Todas las hojas aparecen en el mismo nivel. 5. Una página que no es hoja con k descendientes contiene k -1 llaves. 6. Una página hoja contiene por lo menos [m/2] -1 llaves y no más de m - 1 llaves. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 /Profundidad de la búsqueda en el peor caso /9.12 # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 9.12 ¿Que es el peor caso? El número de descendientes de cualquier nivel de un árbol B es 1 + el número de llaves contenidas en ese nivel y todos los que lo preceden. El peor caso ocurre cuando cada página del árbol sólo contiene el número mínimo de descendientes. En tal caso las llaves se distribuyen sobre una altura máxima para el árbol y una amplitud mínima. Peor caso número máximo de accesos a disco requeridos Profundidad del árbol= = # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Árbol B de 27 llaves Figura 9.28 de la página 442 B D K H N E F GS A T U V Q S W C I J L M O P R X Y Z **Un árbol B con N cantidad de llaves puede tener (fV+1) descendientes a partir del nivel de hoja. ***Este árbol contiene 27 llaves pero 28 descendientes. # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 9.12 Profundidad Para un árbol B de orden M, el número mínimo de descendientes a partir de la página raíz es dos, así que el segundo nivel del árbol contiene sólo dos páginas. Cada una de estas páginas, a su vez, tiene al menos [m/2]^(d-1) descendientes. Por tanto, el tercer nivel contiene 2 veces eso = 2 * [m/2]^(d-1). Así, en general, para cualquier nivel d de un árbol B, el mínimo número de descendientes que se extienden a partir de ese nivel es N + 1 => 2 x [m/2]^(d-1). Ahora ya sabemos que un árbol con N llaves tiene N + 1 descendientes desde su nivel hoja. A la profundidad del árbol en el nivel hoja se le llamará d. puesto que se sabe que el número de descendientes de cualquier árbol no puede ser menor que el número para el peor caso de un árbol de esa profundidad. # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 Arbol B de 27 llaves Figura 9.28 de la página 442 B D K H N E F GS A T U V Q S W C I J L M O P R X Y Z d d d d d d d d d d d d d d d d d d d d d d d d d d d Al despejar d nos entrega la siguiente expresión. d <= 1 + log[m/2]((N +1)/2). # # # # ESTRUCTURA DE DATOS II 9.7 - 9.12 9.12 Ejemplo Para un árbol B de 1 000 000 llaves, es razonable emplear un árbol B de orden 512 (un máximo de 511 llaves por página). Un árbol de orden 512 que contenga 1 000 000 de llaves. Al sustituir estos números específicos dentro de la expresión Se encuentra que d <= log[256](500000.5) , entonces d <= 3.37. De esta manera se puede decir que, dadas 1000 000 de llaves, un árbol B de orden 512 tiene una profundidad de no más de tres niveles. M = 511 +1 N + 1 = 1 000 001 d<= log[512/2](1 000 001/2) d<=3.37 # # # /BIBLIOGRAFÍA ● Folk, M. (1992). Estructuras de Archivos. Addison-Wesley Iberoamericana. Delaware, EUA. ESTRUCTURA DE DATOS II 9.7 - 9.12 # # #
Compartir