2-3-4 Árbol

Un árbol 2-3-4 es un árbol autoequilibrado. El número representa el número de hijos que puede tener cada Node. Cualquier Node interno puede tener dos, tres o cuatro Nodes secundarios. También se le llama árbol 2-4 .

Nota: Es un árbol B de grado cuatro y todos los Nodes hoja al mismo nivel

Propiedades de un árbol 2-3-4:

• Un Node de 2 tiene un elemento de datos y si es un Node interno, entonces tiene dos Nodes secundarios.
• Un Node de 3 tiene dos elementos de datos y, si se trata de un Node interno, tiene tres Nodes secundarios.
• Un Node de 4 tiene tres elementos de datos y si es un Node interno, tiene cuatro Nodes secundarios.
• Los elementos de cada Node deben ordenarse de menor a mayor .
• El árbol 2-3-4 es un árbol perfectamente equilibrado, es decir, en este todos los Nodes hoja están al mismo nivel.
• El tipo de cualquier Node se decide en función de la estructura del árbol (la estructura se decide de manera que el árbol sea siempre un árbol perfectamente equilibrado).

Estructura de un Node en 2-3-4 Tree:

Cada Node puede tener 2, 3 o 4 hijos, cada uno de los cuales contiene 1, 2 o 3 elementos de datos, respectivamente. Los elementos de datos determinan el rango de los elementos que estarán en qué segmento. Vea la siguiente figura para tener una idea de eso:

Operaciones en un árbol 2-3-4:

Hay tres operaciones básicas que se realizan en un árbol 2-3-4. Las operaciones son:

• Inserción de un Node
• Buscando un valor
• Eliminación de un Node

Hemos discutido las operaciones en detalle en las siguientes secciones.

Inserción en un árbol 2-3-4:

En la operación de inserción, se inserta un Node en la ubicación adecuada en el árbol. La operación de inserción siempre se realiza en un Node hoja . Si también hay espacios vacíos en los Nodes internos, aún así no los usamos para la inserción. La operación de inserción se implementa siguiendo los siguientes pasos:

La tarea es buscar el Node hoja adecuado donde se debe insertar el valor. En este proceso, cada vez que obtenemos un Node 4, lo dividimos de tal manera que no necesitamos rastrear desde la hoja hasta la raíz.

1. Si el Node actual (digamos temp ) es un Node 4, ese Node se divide. La siguiente es la forma utilizada para dividir un Node:
   1. Borre el valor medio (digamos X ) del Node y guárdelo.
   2. Ahora divida los 3 Nodes restantes en dos 2 Nodes .
   3. Si la temperatura era la raíz del árbol, cree otra raíz (un Node 2 ) con el valor X que tenga los Nodes recién divididos como su hijo.
   4. De lo contrario, agregue el valor X correspondiente en el Node principal. (Como siempre estamos dividiendo los 4 Nodes mientras nos movemos de arriba hacia abajo, se garantiza que siempre habrá un espacio disponible en el padre).
   5. Ahora organice esos dos 2 Nodes de acuerdo con el Node principal.
2. Encuentre el hijo cuyo intervalo contiene el valor que se está insertando en el árbol.
3. Si el hijo es un Node hoja, inserte el valor. De lo contrario, descienda hasta el niño y repita desde el paso 1 .

Ilustración:

Siga la ilustración para una mejor comprensión.

Digamos que tenemos que insertar los siguientes números en el árbol:
{10, 20, 30, 40, 50, 60}

Inserte 10:
        => Como no hay nada actualmente, inserte 10 en una nueva raíz.
        => La raíz es un Node 2.

Insertar 10

Insertar 20:
        => Insertar 20 en la raíz (que también es la hoja) de manera ordenada.
        => La raíz es ahora un Node 3.

Insertar 20

Insertar 30:
        => Insertar 30 en la raíz (que también es la hoja) de manera ordenada.
        => La raíz es ahora un Node 4.

Insertar 30

Insertar 40:
        => Ahora la raíz es un Node 4. Así que esto necesita ser dividido.
        => Entonces, la nueva raíz será 20. Los dos hijos serán 10 y 30.
        => Ahora, agregue 40 con el Node que contiene 30.

Insertar 40

Insertar 50:
        => El Node 50 debe insertarse a la derecha de 20.
        => Se agrega con el Node que tiene los valores 30 y 40.
        => Esta hoja ahora se convierte en un 4 Node.

Insertar 50

Insertar 60:
        => Mientras buscamos la ruta, encontraremos el Node con los valores 30, 40, 50.
        => Divida este Node. Agregue 40 al padre y organice los otros dos Nodes en consecuencia.
        => Ahora inserte 60 en el Node con valor 50.

Insertar 60

Buscando en un árbol 2-3-4:

La operación de búsqueda es similar a un árbol de búsqueda binaria . Siga el siguiente método para buscar anelements:

1. Comienza a buscar desde la raíz del árbol.
2. Si el valor está presente en ese Node, entonces se encuentra el elemento.
3. De lo contrario, encuentre el intervalo adecuado en el que el valor se basa en la estructura del Node (es decir, es 2 Nodes, 3 Nodes o 4 Nodes).
4. Vaya a ese niño y continúe desde el paso 1.
5. Si se llega a un Node hoja y aún no se encuentra el valor, ese valor no existe en el árbol.

Eliminación de un Node del Árbol 2-3-4:

Aquí también la operación de borrado se realiza siempre en la hoja. El borrado se realiza de la siguiente manera:

1. Busque el Node cuyo valor debe eliminarse.
2. Si el Node es un Node hoja, elimine el valor requerido de ese Node y disminuya los elementos de datos en 1.
3. Si el Node no es un Node hoja, entonces:
   1. Encuentre el sucesor de ese Node. Un sucesor de un Node es el elemento más pequeño entre los que son mayores que él o el elemento más grande entre los que son más pequeños que él.
   2. Intercambie el sucesor con el Node actual y elimine ese Node en la hoja.

Pero puede causar un problema de subdesbordamiento si el Node hoja es un Node 2. Para evitar esto, realizamos los siguientes ajustes en 2 Nodes que se encuentran a lo largo de la ruta para llegar al Node que se eliminará mientras se mueve de arriba a abajo.

Caso – 1: Si alguno de los hermanos del Node actual es un Node 3 o 4.

• Realiza una rotación con ese hermano.
• La clave que tiene el valor más cercano a este Node sube al padre que pasa por alto el Node actual y el padre se agrega al Node actual para convertirlo en un Node 3.
• El Node que originalmente era el hijo del hermano rotado ahora es el hijo del Node actual.

Caso – 2: si el padre es un Node 2 y el hermano también es un Node 2. En este caso particular, el padre es root. Entonces combine los tres 2 Nodes para formar un 4 Node y elimine el valor requerido.

Caso – 3: si los hermanos son 2 Nodes pero el padre es un Node 3 o 4 Nodes:

• Los hermanos (que son 2 Nodes) y la clave principal que pasa por alto a los hermanos se fusionan para formar un 4 Node.
• El hijo de los hermanos es llevado a este Node.

Análisis de complejidad de 2-3-4 árboles:

• La búsqueda, la inserción y la eliminación toman una complejidad de tiempo O (logN) en 2-3-4 árboles. Ya que el 2-3-4 siempre está equilibrado. Al repetir la inserción para inicializar el árbol 2-3-4, podemos decir que el costo de tiempo de init es O(n*log(n)). 
• Altura: En el peor de los casos en 2-3-4 árboles la altura es logN y en el mejor de los casos la altura es 1/2 * logN (Es la condición cuando todos los Nodes son 4 Nodes)

Aplicaciones

Construir un árbol B para representar una gran colección de datos existente y luego actualizarlo lentamente usando operaciones de árbol B convencionales es comúnmente beneficioso en las aplicaciones. En este escenario, el método más eficiente para construir el árbol B inicial es producir el conjunto inicial de Nodes de hoja directamente desde la entrada y luego construir los Nodes internos a partir de estos. Carga masiva es el término para este método de construcción de árbol B. Cada hoja, excepto la última, tiene un elemento adicional que se utilizará para construir los Nodes internos.