2–3–4 árboles

En informática , un árbol 2–3–4 (también llamado árbol 2–4 ) es una estructura de datos autoequilibrada que se puede utilizar para implementar diccionarios . Los números indican un árbol en el que cada nodo con hijos ( nodo interno ) tiene dos, tres o cuatro nodos hijos:

• un nodo de 2 tiene un elemento de datos y, si es interno, tiene dos nodos secundarios;
• un nodo de 3 tiene dos elementos de datos y, si es interno, tiene tres nodos secundarios;
• un nodo de 4 tiene tres elementos de datos y, si es interno, tiene cuatro nodos secundarios;

• 
  2 nodos
• 
  3 nodos
• 
  4 nodos

Los árboles 2–3–4 son árboles B de orden 4; ^[1] como los árboles B en general, pueden buscar, insertar y eliminar en tiempo O (log n ). Una propiedad de un árbol 2–3–4 es que todos los nodos externos están a la misma profundidad.

Los árboles 2–3–4 están estrechamente relacionados con los árboles rojo-negros al interpretar los enlaces rojos (es decir, enlaces a hijos rojos) como enlaces internos de 3 nodos y 4 nodos, aunque esta correspondencia no es uno a uno. ^[2] Los árboles rojo-negros con tendencia a la izquierda restringen los árboles rojo-negros al prohibir los nodos con un solo hijo derecho rojo, lo que produce una correspondencia uno a uno entre los árboles rojo-negros con tendencia a la izquierda y los árboles 2–3–4.

Propiedades

• Cada nodo (hoja o interno) es de 2, 3 o 4 nodos y contiene uno, dos o tres elementos de datos, respectivamente.
• Todas las hojas están a la misma profundidad (el nivel inferior).
• Todos los datos se mantienen en orden.

Inserción

Para insertar un valor, comenzamos en la raíz del árbol 2–3–4:

1. Si el nodo actual es de 4 nodos:
   • Elimine y guarde el valor medio para obtener 3 nodos.
   • Divida los 3 nodos restantes en un par de 2 nodos (el valor medio que ahora falta se maneja en el siguiente paso).
   • Si este es el nodo raíz (que por lo tanto no tiene padre):
     • El valor medio se convierte en el nuevo nodo raíz 2 y la altura del árbol aumenta en 1. Asciende a la raíz.
   • De lo contrario, empuje el valor del medio hacia el nodo principal. Ascienda al nodo principal.
2. Encuentra al niño cuyo intervalo contiene el valor a insertar.
3. Si ese niño es una hoja, inserte el valor en el nodo hijo y finalice.
   • De lo contrario, descienda hacia el niño y repita desde el paso 1. ^{[3] [4]}

Ejemplo

Para insertar el valor "25" en este árbol 2–3–4:

• Comienza en la raíz (10, 20) y desciende hacia el hijo más a la derecha (22, 24, 29). (Su intervalo (20, ∞) contiene 25.)
• El nodo (22, 24, 29) es un nodo 4, por lo que su elemento central 24 se empuja hacia arriba, hacia el nodo padre.

• El nodo 3 restante (22, 29) se divide en un par de nodos 2 (22) y (29). Asciende nuevamente hacia el nuevo nodo padre (10, 20, 24).
• Desciende hacia el hijo más a la derecha (29). (Su intervalo (24, ∞) contiene 25.)

• El nodo (29) no tiene ningún hijo más a la izquierda. (El hijo del intervalo (24, 29) está vacío). Deténgase aquí e inserte el valor 25 en este nodo.

Supresión

La posibilidad más sencilla de eliminar un elemento es simplemente dejarlo allí y marcarlo como "eliminado", adaptando los algoritmos anteriores para que los elementos eliminados se ignoren. Los elementos eliminados se pueden volver a utilizar sobrescribiéndolos al realizar una inserción posterior. Sin embargo, el inconveniente de este método es que el tamaño del árbol no disminuye. Si se elimina una gran proporción de los elementos del árbol, el árbol se volverá mucho más grande que el tamaño actual de los elementos almacenados y el rendimiento de otras operaciones se verá afectado negativamente por los elementos eliminados.

Cuando esto no es deseable, se puede seguir el siguiente algoritmo para eliminar un valor del árbol 2–3–4:

1. Encuentra el elemento que deseas eliminar.
   • Si el elemento no está en un nodo hoja, recuerde su ubicación y continúe buscando hasta llegar a una hoja que contendrá el sucesor del elemento. El sucesor puede ser la clave más grande que sea más pequeña que la que se va a eliminar, o la clave más pequeña que sea más grande que la que se va a eliminar. Es más simple realizar ajustes en el árbol de arriba hacia abajo de modo que el nodo hoja encontrado no sea un nodo de 2. De esa manera, después del intercambio, no habrá un nodo hoja vacío.
   • Si el elemento está en una hoja de 2 nodos, simplemente realice los ajustes a continuación.

Realice los siguientes ajustes cuando se encuentre un nodo de 2 (excepto el nodo raíz) en el camino hacia la hoja que deseamos eliminar:

1. Si un hermano en cualquier lado de este nodo es un nodo 3 o 4 (y por lo tanto tiene más de una clave), realice una rotación con ese hermano:
   • La clave del otro hermano más cercano a este nodo se mueve hacia la clave principal que supervisa los dos nodos.
   • La clave principal se mueve hacia abajo a este nodo para formar un nodo de 3.
   • El hijo que originalmente tenía la clave hermana rotada ahora es el hijo adicional de este nodo.
2. Si el padre es un nodo 2 y el hermano también es un nodo 2, combine los tres elementos para formar un nuevo nodo 4 y acorte el árbol. (Esta regla solo se puede activar si el nodo 2 padre es la raíz, ya que todos los demás nodos 2 a lo largo del camino se habrán modificado para que no sean nodos 2. Es por eso que "acortar el árbol" aquí preserva el equilibrio; este también es un supuesto importante para la operación de fusión).
3. Si el padre es un nodo 3 o 4 y todos los hermanos adyacentes son nodos 2, realice una operación de fusión con el padre y un hermano adyacente:
   • El hermano adyacente y la clave principal que supervisa los dos nodos hermanos se unen para formar un nodo de 4.
   • Transfiere los hijos del hermano a este nodo.

Una vez que se alcanza el valor buscado, ahora se puede colocar en la ubicación de la entrada eliminada sin problema porque nos hemos asegurado de que el nodo hoja tenga más de una clave.

La eliminación en un árbol 2–3–4 es O(log n), suponiendo que la transferencia y la fusión se realizan en tiempo constante (O(1)). ^{[3] [5]}

Operaciones paralelas

Dado que los árboles 2–3–4 son similares en estructura a los árboles rojo-negros , los algoritmos paralelos para árboles rojo-negros también se pueden aplicar a los árboles 2–3–4.

Véase también

• Portal de programación informática

• 2–3 árboles
• Árbol rojo-negro
• Árbol B
• Quejarse

Referencias

1. Knuth, Donald (1998). Ordenación y búsqueda . El arte de la programación informática . Vol. 3 (segunda edición). Addison–Wesley. ISBN 0-201-89685-0.Sección 6.2.4: Árboles multidireccionales, págs. 481–491. Además, en las págs. 476–477 de la sección 6.2.3 (Árboles equilibrados) se analizan árboles de 2 a 3 vías.
2. Sedgewick, Robert (2008). "Left-Leaning Red–Black Trees" (PDF) . Árboles rojo-negros con tendencia a la izquierda . Departamento de Ciencias de la Computación, Universidad de Princeton.
3. Ford, William; Topp, William (2002), Estructuras de datos con C++ utilizando STL (2.ª ed.), Nueva Jersey: Prentice Hall, pág. 683, ISBN 0-13-085850-1
4. Goodrich, Michael T ; Tamassia, Roberto ; Mount, David M (2002), Estructuras de datos y algoritmos en C++ , Wiley , ISBN 0-471-20208-8
5. Grama, Ananth (2004). "(2,4) Árboles" (PDF) . CS251: Apuntes de la clase sobre estructuras de datos . Departamento de Ciencias de la Computación, Universidad de Purdue . Consultado el 10 de abril de 2008 .

Enlaces externos

• Algoritmos en acción, con animación de árbol 2-3-4
• Árboles rojos y negros con tendencia izquierdista – Robert Sedgewick, Universidad de Princeton, 2008
• Estructuras de datos abiertas – Sección 9.1 – Árboles 2–4, Pat Morin
• 2–3–4 Árboles: Una introducción visual, 2017