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 significan un árbol donde cada nodo con hijos ( nodo interno ) tiene dos, tres o cuatro nodos secundarios:
- un 2-nodo tiene un elemento de datos , y si interno tiene dos nodos secundarios;
- un 3-nodo tiene dos elementos de datos, y si es interno tiene tres nodos secundarios;
- un 4-nodo tiene tres elementos de datos, y si es interno tiene cuatro nodos secundarios;
2–3–4 árboles | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
2 nodos
3 nodos
4 nodos
2–3–4 árboles son árboles B de orden 4; [1] al igual que 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.
2–3–4 árboles son una isometría de árboles rojo-negro , lo que significa que son estructuras de datos equivalentes. En otras palabras, por cada 2–3–4 árboles, existe al menos un árbol rojo-negro con elementos de datos en el mismo orden. Además, las operaciones de inserción y eliminación en 2–3–4 árboles que causan expansiones, divisiones y fusiones de nodos son equivalentes a los cambios de color y rotaciones en árboles rojo-negro. Las introducciones a los árboles rojo-negro suelen presentar primero de 2 a 3 a 4 árboles, porque son conceptualmente más simples. 2–3–4 árboles, sin embargo, pueden ser difíciles de implementar en la mayoría de los lenguajes de programación debido a la gran cantidad de casos especiales involucrados en las operaciones en el árbol. Los árboles rojo-negro son más fáciles de implementar, [2] por lo que tienden a usarse en su lugar.
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 ordenados.
Inserción
Para insertar un valor, comenzamos en la raíz del árbol 2–3–4:
- Si el nodo actual es de 4 nodos:
- Elimine y guarde el valor medio para obtener un nodo de 3.
- 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 la nueva raíz de 2 nodos y la altura del árbol aumenta en 1. Asciende a la raíz.
- De lo contrario, empuje el valor medio hacia arriba en el nodo principal. Asciende al nodo principal.
- Encuentre el niño cuyo intervalo contiene el valor que se va a insertar.
- Si ese hijo es una hoja, inserte el valor en el nodo hijo y termine.
Ejemplo
Para insertar el valor "25" en este árbol 2–3–4:
- Comience en la raíz (10, 20) y descienda hacia el niño más a la derecha (22, 24, 29). (Su intervalo (20, ∞) contiene 25.)
- El nodo (22, 24, 29) es un nodo de 4, por lo que su elemento intermedio 24 se empuja hacia arriba en el nodo principal.
- Los 3 nodos restantes (22, 29) se dividen en un par de 2 nodos (22) y (29). Asciende de nuevo al nuevo padre (10, 20, 24).
- Desciende hacia el niño más a la derecha (29). (Su intervalo (24, ∞) contiene 25.)
- El nodo (29) no tiene un hijo situado más a la izquierda. (El elemento secundario 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 dejar el elemento allí y marcarlo como "eliminado", adaptando los algoritmos anteriores para que los elementos eliminados se ignoren. Los elementos eliminados se pueden reutilizar sobrescribiéndolos al realizar una inserción más adelante. 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, entonces el árbol será 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 sea deseable, se puede seguir el siguiente algoritmo para eliminar un valor del árbol 2–3–4:
- Busque el elemento que desea eliminar.
- Si el elemento no está en un nodo hoja, recuerde su ubicación y continúe buscando hasta alcanzar una hoja, que contendrá el sucesor del elemento. El sucesor puede ser la clave más grande que es más pequeña que la que se va a quitar o la clave más pequeña que es más grande que la que se va a quitar. Lo más sencillo es realizar ajustes en el árbol de arriba hacia abajo, de modo que el nodo hoja encontrado no sea de 2 nodos. De esa forma, 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 queremos eliminar:
- Si un hermano a cada lado de este nodo es de 3 o 4 nodos (por lo tanto, tiene más de 1 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 pasa por alto 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 de hermano rotada ahora es el hijo adicional de este nodo.
- Si el padre es de 2 nodos y el hermano también es de 2 nodos, combine los tres elementos para formar un nuevo 4 nodos y acorte el árbol. (Esta regla solo puede activarse si el 2-nodo principal es la raíz, ya que todos los otros 2 nodos a lo largo del camino se habrán modificado para que no sean 2 nodos. Es por eso que "acortar el árbol" aquí preserva el equilibrio; esto es también una suposición importante para la operación de fusión.)
- Si el padre es de 3 o 4 nodos y todos los hermanos adyacentes son de 2 nodos, realice una operación de fusión con el padre y un hermano adyacente:
- El hermano adyacente y la clave principal con vistas a los dos nodos hermanos se unen para formar un nodo de 4.
- Transfiera a 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 problemas porque nos hemos asegurado de que el nodo hoja tenga más de 1 clave.
La eliminación en un árbol 2–3–4 es O (log n), suponiendo que la transferencia y la fusión se ejecuten en un tiempo constante (O (1)). [3] [5]
Operaciones paralelas
Dado que 2–3–4 árboles son similares en estructura a los árboles rojo-negro , los algoritmos paralelos para árboles rojo-negro también se pueden aplicar a 2–3–4 árboles.
Ver también
Referencias
- ^ Knuth, Donald (1998). Clasificación y búsqueda . El arte de la programación informática . Volumen 3 (Segunda ed.). Addison – Wesley. ISBN 0-201-89685-0.
|volume=
tiene texto extra ( ayuda ). Sección 6.2.4: Árboles de múltiples vías, págs. 481–491. Además, las páginas 476–477 de la sección 6.2.3 (Árboles equilibrados) discuten 2–3 árboles. - ^ Sedgewick, Robert (2008). "Árboles rojo-negros inclinados a la izquierda" (PDF) . Árboles rojo-negros inclinados a la izquierda . Departamento de Ciencias de la Computación, Universidad de Princeton.
- ^ a b Ford, William; Topp, William (2002), Estructuras de datos con C ++ usando STL (2ª ed.), Nueva Jersey: Prentice Hall, p. 683, ISBN 0-13-085850-1
- ^ Goodrich, Michael T ; Tamassia, Roberto ; Mount, David M (2002), Estructuras de datos y algoritmos en C ++ , Wiley , ISBN 0-471-20208-8
- ^ Grama, Ananth (2004). "(2,4) Árboles" (PDF) . CS251: Notas de clase sobre estructuras de datos . Departamento de Ciencias de la Computación, Universidad de Purdue . Consultado el 10 de abril de 2008 .