Preguntas de práctica sobre árboles B y B+

En este artículo, discutiremos diferentes tipos de problemas basados ​​en árboles B y B+. Antes de comprender este artículo, debe comprender los conceptos básicos de los árboles B y B+ (consulte: Introducción , Insertar , Eliminar ).

Estos son los tipos de preguntas que se hacen en GATE basadas en árboles B y B+.

Tipo 1. Basado en el orden y la cantidad de claves en el árbol B y B+:
estos son algunos puntos clave relacionados con el orden y la cantidad de claves:

• El árbol AB/B+ con orden p tiene un máximo de p punteros y, por lo tanto, un máximo de p hijos.
• El árbol AB/B+ con orden p tiene punteros de techo mínimo (p/2) y, por lo tanto, hijos de techo mínimo (p/2).
• El árbol AB/B+ con orden p tiene claves máximas (p – 1) y mínimas (p/2) – 1.

Que – 1. Considere un árbol B+ en el que el número máximo de claves en un Node es 5. ¿Cuál es el número mínimo de claves en cualquier Node no raíz? (GATE CS 2010)
(A) 1
(B) 2
(C) 3
(D) 4

Solución: Suponiendo que el orden del árbol B+ sea p, el número máximo de claves será (p – 1). Como se da que,
p – 1 = 5 => p = 6
Por tanto, número mínimo de claves:
ceil(p/2) – 1 = 2

Tipo 2. Basado en la inserción de una clave en el árbol B/B+:
dado el orden del árbol B/B+ y las claves que se insertarán, se puede pedir que encuentre el árbol B/B+ resultante o la altura del árbol B/B+.

Que – 2. Considere el siguiente árbol 2-3-4 (es decir, árbol B con un grado mínimo de dos) en el que cada elemento de datos es una letra. El orden alfabético habitual de las letras se utiliza para construir el árbol.

¿Cuál es el resultado de insertar G en el árbol anterior?
(A)

(B)

(C)

(D) Ninguno

Solución: Dado que el árbol B dado tiene un grado mínimo de 2, el grado u orden máximo será 2*2 = 4. Por lo tanto, tendrá como máximo 4 punteros o 3 claves.
Atravesaremos desde la raíz hasta el Node hoja donde se insertará G. Como G es menor que L, se insertará en el Node hoja con elementos BHI. Después de la inserción de G, el Node hoja en orden ordenado será BGHI, lo que conduce al desbordamiento. Se dividirá en dos partes BG e I y el elemento medio H se enviará a su Node principal como:

Ahora, el Node raíz con las claves H, L, P, U se desborda, lo que conduce a la división del Node raíz en dos partes, HL y U, y el elemento central P será el Node raíz que coincide con la opción B.
Nota:

• Se producen 2 divisiones para la inserción de G.
• La altura del árbol B es 1 (ruta desde el Node raíz hasta el Node hoja) antes de la inserción de G. Después de la inserción de G, la altura del árbol B alcanza 2.

Tipo 3. Basado en la búsqueda de una clave en el árbol B/B+:
estos son los puntos clave relacionados con la búsqueda en los árboles B/B+:

• Para buscar una clave en el árbol B, comenzamos desde el Node raíz y recorremos hasta encontrar la clave o alcanzar el Node hoja.
• Para buscar una clave en el árbol B+, comenzamos desde el Node raíz y recorremos hasta llegar al Node hoja, ya que cada clave está presente en los Nodes hoja. Además, los Nodes de hoja están conectados entre sí, lo que ayuda a un acceso más rápido a los datos para consultas de rango.

Que – 3. Con referencia al índice de árbol B+ de orden 1 que se muestra a continuación, el número mínimo de Nodes (incluido el Node raíz) que se deben buscar para satisfacer la siguiente consulta: “Obtener todos los registros con una clave de búsqueda mayor que o igual a 7 y menor a 15” es ____. (GATE-CS-2015)

(A) 4
(B) 5
(C) 6
(D) 7

Solución: Primero buscaremos la clave igual a 7. Para encontrar 7, comenzaremos desde el Node raíz y nos moveremos al Node con la clave 5 y luego al Node hoja con las claves 5 y 7. Entonces, para buscar 7, necesitamos acceder 3 Nodes.

Una vez que se busca 7, podemos ir al siguiente Node de hoja que contiene las claves 9 y 11. Desde aquí, podemos ir al Node de hoja con las claves 13 y 15. Como queremos claves menores a 15, podemos detenernos aquí. Por lo tanto, el total de Nodes accedidos = 3 (para buscar 7) + 2 (para encontrar claves de menos de 15) = 5.

Nota: si usamos el árbol B, entonces necesitamos buscar 7, 8, 9, 10, 11 individualmente debido a qué Node el acceso será mayor. Por lo tanto, se prefiere B+ tee para consultas de rango.

Tipo 4. Recuento de división de Nodes en el árbol B/B+ –

Que – 4. Un árbol B de orden 4 se construye desde cero mediante 10 inserciones sucesivas. ¿Cuál es el número máximo de operaciones de división de Nodes que se pueden realizar? (GATE CS 2008)
(A) 3
(B) 4
(C) 5
(D) 6

Solución: el árbol AB de orden 4 puede tener un máximo de 3 claves.

Las primeras 3 inserciones no tendrán ninguna división como se muestra en la Figura (a).
Al insertar el cuarto elemento, habrá 1 división como se muestra en la Figura (b).
Al insertar el quinto elemento, no habrá división, pero lo insertaremos en ese Node de hoja que tenga el elemento máximo para producir más divisiones en inserciones adicionales, como se muestra en la Figura (c).
Al insertar el sexto elemento, habrá 1 división como se muestra en la Figura (d).
Al insertar el 7º elemento, no habrá división, pero lo insertaremos en ese Node de hoja que tenga el elemento máximo para producir más divisiones en inserciones adicionales, como se muestra en la Figura (e).
Al insertar el octavo elemento, habrá 1 división como se muestra en la Figura (f).
Al insertar el noveno elemento, no habrá división, pero insertaremos en ese Node de hoja que tenga el elemento máximo para producir más divisiones en inserciones posteriores, como se muestra en la Figura (g).
Al insertar el décimo elemento, habrá 2 divisiones como se muestra en la Figura (h).
Número total de divisiones = 5.