2–3 montón

En informática , un montón 2–3 es una estructura de datos , una variación del montón , diseñada por Tadao Takaoka en 1999. La estructura es similar al montón de Fibonacci y toma prestado del árbol 2–3 .

Los costos de tiempo para algunas operaciones de montón comunes son:

• Delete-min toma tiempo amortizado . ${\displaystyle O(\log(n))}$
• La clave de disminución toma un tiempo amortizado constante.
• La inserción toma un tiempo amortizado constante.

Polinomio de arboles

Fuente: ^[1]

Un árbol lineal de tamaño es una ruta secuencial de nodos con el primer nodo como raíz del árbol y se representa con un negrita (p. ej. es un árbol lineal de un solo nodo). Producto de dos árboles y , es un árbol nuevo con cada nodo de se reemplaza por una copia de y para cada arista de conectamos las raíces de los árboles correspondientes a los puntos finales de la arista. Tenga en cuenta que esta definición de producto es asociativa pero no conmutativa. Suma de dos árboles y es la colección de dos árboles y . ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle \mathbf {r} }$ ${\displaystyle \mathbf {1} }$ ${\displaystyle P=ST}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle S+T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$

Un polinomio r-ario de árboles se define como donde . Esta notación polinómica para árboles de nodos es única. El árbol es en realidad una copia de cuyas raíces están conectadas con aristas de manera secuencial y la ruta de estas aristas se denomina tronco principal del árbol . Además, un polinomio r-ario de árboles se denomina cola r-nómica si los nodos del polinomio de árboles están asociados con claves en la propiedad del montón. ${\displaystyle P=\mathbf {a} _{k-1}\mathbf {r} ^{k-1}+\dots +\mathbf {a} _{1}\mathbf {r} +\mathbf {a} _{0}}$ ${\displaystyle 0\leq a_{i}\leq r-1}$ ${\displaystyle n}$ ${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle \mathbf {r} ^{i}}$ ${\displaystyle a_{i}-1}$ ${\displaystyle a_{i}-1}$ ${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$

Operaciones en colas r-nominales

Para fusionar dos términos de la forma y , simplemente reordenamos los árboles en el tronco principal en función de las claves en la raíz de los árboles. Si tendremos un término de la forma y un árbol de acarreo . De lo contrario, tendríamos solo un árbol . Por lo tanto, la suma de dos colas r-nomiales es en realidad similar a la suma de dos números en base . ${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$ ${\displaystyle \mathbf {a} '_{i}\mathbf {r} ^{i}}$ ${\displaystyle a_{i}+a'_{i}\geq r}$ ${\displaystyle (\mathbf {a} _{i}+\mathbf {a} '_{i}-\mathbf {r} )\mathbf {r} ^{i}}$ ${\displaystyle \mathbf {r} ^{i+1}}$ ${\displaystyle (\mathbf {a} _{i}+\mathbf {a} '_{i})\mathbf {r} ^{i}}$ ${\displaystyle r}$

Insertar una clave en una cola polinomial es como fusionar un solo nodo con la etiqueta de la clave en la cola r-nomial existente, lo cual lleva tiempo. ${\displaystyle O(r\log _{r}{n})}$

Para eliminar el mínimo, primero debemos encontrar el mínimo en la raíz de un árbol, digamos , luego eliminamos el mínimo de y agregamos la cola polinomial resultante a en tiempo total . ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle Q}$ ${\displaystyle P-T}$ ${\displaystyle O(r\log _{r}{n})}$

(2,3)-montón

Fuente: ^[1]

Un árbol se define recursivamente mediante for ( está entre y y las operaciones se evalúan de derecha a izquierda) donde para dos árboles, y , el resultado de la operación es conectar la raíz de como hijo más a la derecha a la raíz de y es un árbol de un solo nodo. Nótese que la raíz del árbol tiene grado . ${\displaystyle (l,r)-}$ ${\displaystyle T(i)}$ ${\displaystyle T(i)=T_{1}(i-1)\triangleleft \dots \triangleleft T_{s}(i-1)}$ ${\displaystyle i\geq 1}$ ${\displaystyle s}$ ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle (s-1)}$ ${\displaystyle \triangleleft }$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\triangleleft B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle T(0)}$ ${\displaystyle T(i)}$ ${\displaystyle i}$

Un polinomio extendido de árboles, , se define por . Si asignamos claves a los nodos de un polinomio extendido de árboles en orden de montón, se denomina , y el caso especial de y se denomina . ${\displaystyle P}$ ${\displaystyle P=a_{k-1}T(k-1)+\dots +a_{1}T(1)+a_{0}}$ ${\displaystyle (l,r)-heap}$ ${\displaystyle l=2}$ ${\displaystyle r=3}$ ${\displaystyle (2,3)-heap}$

Operaciones en el montón (2,3)

Delete-min : Primero, encuentre el mínimo escaneando la raíz de los árboles. Sea el árbol que contiene el elemento mínimo y sea el resultado de eliminar la raíz de . Luego, fusione y (la operación de fusión es similar a la fusión de dos colas r-nomiales ). ${\displaystyle T(i)}$ ${\displaystyle Q}$ ${\displaystyle T(i)}$ ${\displaystyle P-T(i)}$ ${\displaystyle Q}$

Inserción : para insertar una nueva clave, fusione el montón (2,3) existente actualmente con un solo árbol de nodos, etiquetado con esta clave. ${\displaystyle T(0)}$

Tecla Disminuir : ¡Por hacer!

Referencias

1. Takaoka, Tadao (marzo de 2003). "Teoría de 2-3 montones". Matemáticas Aplicadas Discretas . 126 (1): 115–128. doi : 10.1016/S0166-218X(02)00219-6 .