2-3 árboles | (Buscar, Insertar y Eliminar)

En los árboles de búsqueda binarios, hemos visto que el tiempo de caso promedio para operaciones como buscar/insertar/eliminar es O(log N) y el tiempo en el peor de los casos es O(N) donde N es el número de Nodes en el árbol.

Al igual que otros árboles, se incluyen los árboles AVL, Red Black Tree, B tree, 2-3 Tree también es un árbol de altura equilibrada .

La complejidad de tiempo de búsqueda/inserción/eliminación es O(log N) .

Un árbol 2-3 es un árbol B de orden 3 .

Propiedades del árbol 2-3:

• Los Nodes con dos hijos se llaman 2-Nodes. Los 2 Nodes tienen un valor de datos y dos hijos.
• Los Nodes con tres hijos se denominan 3 Nodes. Los 3 Nodes tienen dos valores de datos y tres hijos.
• Los datos se almacenan en orden ordenado.
• Es un árbol equilibrado.
• Todos los Nodes hoja están al mismo nivel.
• Cada Node puede ser hoja, 2 Nodes o 3 Nodes.
• La inserción siempre se realiza en la hoja.

Búsqueda: Para buscar una clave K en un árbol 2-3 T dado , seguimos el siguiente procedimiento: 
Casos base: 

1. Si T está vacío, devuelve Falso (no se puede encontrar la clave en el árbol).
2. Si el Node actual contiene un valor de datos que es igual a K , devuelve True.
3. Si llegamos al Node hoja y no contiene el valor clave requerido K , devuelve False.

Llamadas recursivas: 
 

1. Si K < currentNode.leftVal, exploramos el subárbol izquierdo del Node actual.
2. De lo contrario, si currentNode.leftVal < K < currentNode.rightVal, exploramos el subárbol central del Node actual.
3. De lo contrario, si K > currentNode.rightVal, exploramos el subárbol derecho del Node actual.

Considere el siguiente ejemplo: 

Inserción: Hay 3 posibles casos de inserción que se han discutido a continuación: 

Caso 1: Insertar en un Node con un solo elemento de datos 

Caso 2: Insertar en un Node con dos elementos de datos cuyo padre contiene solo un elemento de datos. 

Caso 3: Insertar en un Node con dos elementos de datos cuyo padre también contiene dos elementos de datos. 

En Proceso de Eliminación para un valor específico:

• Para eliminar un valor, se reemplaza por su sucesor en orden y luego se elimina.
• Si un Node se queda con menos de un valor de datos, entonces se deben fusionar dos Nodes.
• Si un Node queda vacío después de eliminar un valor, se fusiona con otro Node.

Para entender el proceso de eliminación-

Considere el árbol 2-3 dado a continuación

elimine los siguientes valores: 69,72, 99, 81 .

Para eliminar 69 , intercámbielo con su sucesor en orden, es decir, 72. 69 ahora viene en el Node hoja. Elimine el valor 69 del Node hoja.

Para eliminar 72 , 72 es un Node interno. Para eliminar este valor, intercambie 72 con su sucesor en orden 81 para que 72 ahora se convierta en un Node hoja. Quite el valor 72 del Node hoja.

Ahora hay un Node de hoja que tiene menos de 1 valor de datos, violando así la propiedad de un árbol 2-3. Entonces el Node debe fusionarse.

Para fusionar el Node, despliegue el valor de datos más bajo en el Node principal y fusionelo con su hermano izquierdo.

Para eliminar 99 , 99 está presente en un Node hoja, por lo que el valor de los datos se puede eliminar fácilmente.

Ahora hay un Node hoja que tiene menos de 1 valor de datos, violando así la propiedad de un árbol 2-3.

Entonces el Node debe fusionarse. Para fusionar el Node, despliegue el valor de datos más bajo en el Node principal y fusionelo con su hermano izquierdo.

Para borrar 81 , 81 es un Node interno. Para eliminar este valor, intercambie 81 con su sucesor en orden 90 para que 81 ahora se convierta en un Node hoja. Elimine el valor 81 del Node hoja.

Ahora hay un Node hoja que tiene menos de 1 valor de datos, violando así la propiedad de un árbol 2-3. Entonces el Node debe fusionarse. Para fusionar el Node, despliegue el valor de datos más bajo en el Node principal y fusionelo con su hermano izquierdo.

Como Node interno no puede estar vacío. Así que ahora extraiga el valor de datos más bajo del Node principal y combine el Node vacío con su hermano izquierdo

NOTA: En un árbol 2-3, cada Node interior tiene dos o tres hijos. Esto significa que un árbol 2-3 no es un árbol binario.