Tratar

Estructura de datos del árbol de búsqueda aleatoria

En informática , el treap y el árbol binario de búsqueda aleatorio son dos formas estrechamente relacionadas de estructuras de datos de árboles binarios de búsqueda que mantienen un conjunto dinámico de claves ordenadas y permiten búsquedas binarias entre las claves. Después de cualquier secuencia de inserciones y eliminaciones de claves, la forma del árbol es una variable aleatoria con la misma distribución de probabilidad que un árbol binario aleatorio; en particular, con alta probabilidad su altura es proporcional al logaritmo del número de claves, de modo que cada operación de búsqueda, inserción o eliminación toma un tiempo logarítmico para realizarse.

Descripción

Un treap con clave alfabética y orden numérico máximo de montón

El treap fue descrito por primera vez por Raimund Seidel y Cecilia R. Aragon en 1989; ^{[1] [2]} su nombre es un acrónimo de tree y heap . Es un árbol cartesiano en el que a cada clave se le asigna una prioridad numérica (elegida aleatoriamente). Como con cualquier árbol de búsqueda binario, el orden de recorrido en orden de los nodos es el mismo que el orden ordenado de las claves. La estructura del árbol está determinada por el requisito de que esté ordenado en el montón: es decir, el número de prioridad para cualquier nodo que no sea hoja debe ser mayor o igual que la prioridad de sus hijos. Por lo tanto, como con los árboles cartesianos de manera más general, el nodo raíz es el nodo de máxima prioridad, y sus subárboles izquierdo y derecho se forman de la misma manera a partir de las subsecuencias del orden ordenado a la izquierda y derecha de ese nodo.

Una forma equivalente de describir el treap es que podría formarse insertando los nodos con la mayor prioridad primero en un árbol binario de búsqueda sin hacer ningún reequilibrio. Por lo tanto, si las prioridades son números aleatorios independientes (de una distribución sobre un espacio lo suficientemente grande de prioridades posibles para asegurar que es muy poco probable que dos nodos tengan la misma prioridad), entonces la forma de un treap tiene la misma distribución de probabilidad que la forma de un árbol binario de búsqueda aleatorio , un árbol de búsqueda formado insertando los nodos sin reequilibrar en un orden de inserción elegido aleatoriamente. Debido a que se sabe que los árboles binarios de búsqueda aleatorios tienen una altura logarítmica con alta probabilidad, lo mismo es cierto para los treaps. Esto refleja el argumento del árbol binario de búsqueda de que la ordenación rápida se ejecuta en el tiempo esperado. Si los árboles binarios de búsqueda son soluciones a la versión de ordenación del problema dinámico , entonces los Treaps corresponden específicamente a la ordenación rápida dinámica donde las prioridades guían las elecciones de pivote. ${\displaystyle O(n\log n)}$

Aragon y Seidel también sugieren asignar prioridades más altas a los nodos a los que se accede con frecuencia, por ejemplo mediante un proceso que, en cada acceso, elija un número aleatorio y reemplace la prioridad del nodo con ese número si es mayor que la prioridad anterior. Esta modificación haría que el árbol perdiera su forma aleatoria; en cambio, los nodos a los que se accede con frecuencia tendrían más probabilidades de estar cerca de la raíz del árbol, lo que haría que las búsquedas de ellos fueran más rápidas.

Naor y Nissim ^[3] describen una aplicación para mantener certificados de autorización en criptosistemas de clave pública .

Operaciones

Operaciones básicas

Los treaps admiten las siguientes operaciones básicas:

• Para buscar un valor de clave determinado, aplique un algoritmo de búsqueda binaria estándar en un árbol de búsqueda binaria, ignorando las prioridades.
• Para insertar una nueva clave x en el árbol, genere una prioridad aleatoria y para x . Realice una búsqueda binaria de x en el árbol y cree un nuevo nodo en la posición de la hoja donde la búsqueda binaria determina que debe existir un nodo para x . Luego, siempre que x no sea la raíz del árbol y tenga un número de prioridad mayor que su padre z , realice una rotación del árbol que invierta la relación padre-hijo entre x y z .
• Para eliminar un nodo x del árbol, si x es una hoja del árbol, simplemente elimínelo. Si x tiene un solo hijo z , elimine x del árbol y haga que z sea el hijo del padre de x (o haga que z sea la raíz del árbol si x no tenía padre). Finalmente, si x tiene dos hijos, intercambie su posición en el árbol con la posición de su sucesor inmediato z en el orden ordenado, lo que da como resultado uno de los casos anteriores. En este caso final, el intercambio puede violar la propiedad de ordenamiento del montón para z , por lo que es posible que se deban realizar rotaciones adicionales para restaurar esta propiedad.

Construyendo un treap

• Para construir un treap, simplemente podemos insertar n valores en el treap, donde cada uno toma tiempo. Por lo tanto, un treap se puede construir en el tiempo a partir de una lista de valores. ${\displaystyle O(\log n)}$ ${\displaystyle O(n\log n)}$

Operaciones a granel

Además de las operaciones de inserción, eliminación y búsqueda de un solo elemento, se han definido varias operaciones rápidas "en masa" en treaps: unión , intersección y diferencia de conjuntos . Estas se basan en dos operaciones auxiliares: división y unión .

• Para dividir un treap en dos treaps más pequeños, aquellos más pequeños que la clave x y aquellos más grandes que la clave x , inserte x en el treap con máxima prioridad (mayor que la prioridad de cualquier nodo en el treap). Después de esta inserción, x será el nodo raíz del treap, todos los valores menores que x se encontrarán en el subtreap izquierdo y todos los valores mayores que x se encontrarán en el subtreap derecho. Esto cuesta tanto como una sola inserción en el treap.
• Al unir dos treaps que son el producto de una división anterior, se puede asumir con seguridad que el valor más grande en el primer treap es menor que el valor más pequeño en el segundo treap. Cree un nuevo nodo con el valor x , de modo que x sea mayor que este valor máximo en el primer treap y menor que el valor mínimo en el segundo treap, asígnele la prioridad mínima, luego establezca su hijo izquierdo en el primer montón y su hijo derecho en el segundo montón. Gire según sea necesario para corregir el orden del montón. Después de eso, será un nodo hoja y se puede eliminar fácilmente. El resultado es un treap fusionado de los dos treaps originales. Esto es efectivamente "deshaciendo" una división y cuesta lo mismo. De manera más general, la operación de unión puede funcionar en dos treaps y una clave con prioridad arbitraria (es decir, no es necesario que sea la más alta).

La unión se realiza en treaps y . El hijo derecho de después de la unión se define como una unión de su hijo derecho anterior y . ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

El algoritmo de unión es el siguiente:

función join(L, k, R) si prior(k, k(L)) y prior(k, k(R)) retorna Nodo(L, k, R) si prior(k(L), k(R)) retorna Nodo(izquierda(L), k(L), join(derecha(L), k, R)) retorna Nodo(join(L, k, izquierda(R)), k(R), derecha(R))

Para dividir por , se realiza una llamada de división recursiva al hijo izquierdo o derecho de . ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle T}$

El algoritmo de división es el siguiente:

función split(T, k) si (T = nulo) devuelve (nulo, falso, nulo) (L, (m, c), R) = exponer(T) si (k = m) devuelve (L, verdadero, R) si (k < m) (L', b, R') = dividir(L, k) devuelve (L', b, unir(R', m, R)) si (k > m) (L', b, R') = dividir(R, k) devolver (unir(L, m, L'), b, R'))

La unión de dos treaps t ₁ y t ₂ , que representan los conjuntos A y B, es una treap t que representa A ∪ B . El siguiente algoritmo recursivo calcula la unión:

función unión(t 1 , t 2 ): si t 1 = nulo: devuelve t 2  si t 2 = nulo: devuelve t 1  si prioridad(t 1 ) < prioridad(t 2 ): intercambia t 1 y t 2 t < , t > ← divide t 2 en clave(t 1 ) devuelve unión(unión(izquierda(t 1 ), t < ), clave(t 1 ), unión(derecha(t 1 ), t > ))

Aquí, se supone que split devuelve dos árboles: uno que contiene las claves menores que su clave de entrada, y otro que contiene las claves mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva en el lugar).

El algoritmo para la intersección es similar, pero requiere la rutina auxiliar de unión . La complejidad de cada unión, intersección y diferencia es O ( m log ⁠norte/metro) para treaps de tamaños m y n , con m ≤ n . Además, dado que las llamadas recursivas a unión son independientes entre sí, se pueden ejecutar en paralelo . ^[4]

Split y Union llaman a Join pero no tratan directamente los criterios de equilibrio de los treaps; este tipo de implementación suele denominarse implementación "basada en join" .

Tenga en cuenta que si se utilizan valores hash de claves como prioridades y se fusionan nodos estructuralmente iguales ya en la construcción, cada nodo fusionado será una representación única de un conjunto de claves. Siempre que solo pueda haber un nodo raíz simultáneo que represente un conjunto de claves determinado, se puede probar la igualdad de dos conjuntos mediante una comparación de punteros, que es constante en el tiempo.

Esta técnica se puede utilizar para mejorar los algoritmos de fusión para que funcionen más rápido incluso cuando la diferencia entre dos conjuntos es pequeña. Si los conjuntos de entrada son iguales, las funciones de unión e intersección podrían interrumpirse inmediatamente y devolver uno de los conjuntos de entrada como resultado, mientras que la función de diferencia debería devolver el conjunto vacío.

Sea d el tamaño de la diferencia simétrica. Los algoritmos de fusión modificados también estarán entonces limitados por O ( d log ⁠norte/d⁠ ) ​​. ^{[5] [6]}

Árbol de búsqueda binaria aleatorizado

El árbol binario de búsqueda aleatorio, introducido por Martínez y Roura posteriormente al trabajo de Aragon y Seidel sobre treaps, ^[7] almacena los mismos nodos con la misma distribución aleatoria de la forma del árbol, pero mantiene información diferente dentro de los nodos del árbol para mantener su estructura aleatoria.

En lugar de almacenar prioridades aleatorias en cada nodo, el árbol binario de búsqueda aleatorizado almacena un pequeño entero en cada nodo, el número de sus descendientes (contándose a sí mismo como uno); estos números pueden mantenerse durante las operaciones de rotación del árbol con solo una cantidad constante de tiempo adicional por rotación. Cuando se inserta una clave x en un árbol que ya tiene n nodos, el algoritmo de inserción elige con probabilidad 1/( n  + 1) colocar x como la nueva raíz del árbol, y de lo contrario, llama al procedimiento de inserción recursivamente para insertar x dentro del subárbol izquierdo o derecho (dependiendo de si su clave es menor o mayor que la raíz). El algoritmo usa los números de descendientes para calcular las probabilidades necesarias para las elecciones aleatorias en cada paso. Colocar x en la raíz de un subárbol puede realizarse como en el treap insertándolo en una hoja y luego rotándolo hacia arriba, o mediante un algoritmo alternativo descrito por Martínez y Roura que divide el subárbol en dos partes para usarlas como los hijos izquierdo y derecho del nuevo nodo.

El procedimiento de eliminación de un árbol binario de búsqueda aleatorio utiliza la misma información por nodo que el procedimiento de inserción, pero a diferencia del procedimiento de inserción, solo necesita en promedio O(1) decisiones aleatorias para unir los dos subárboles que descienden de los hijos izquierdo y derecho del nodo eliminado en un solo árbol. Esto se debe a que los subárboles que se unirán tienen en promedio una profundidad de Θ(log n); unir dos árboles de tamaño n y m necesita Θ(log(n+m)) elecciones aleatorias en promedio. Si el subárbol izquierdo o derecho del nodo que se eliminará está vacío, la operación de unión es trivial; de lo contrario, se selecciona el hijo izquierdo o derecho del nodo eliminado como la nueva raíz del subárbol con una probabilidad proporcional a su número de descendientes, y la unión se realiza de forma recursiva.

Comparación

La información almacenada por nodo en el árbol binario aleatorio es más simple que en un treap (un entero pequeño en lugar de un número aleatorio de alta precisión), pero realiza un mayor número de llamadas al generador de números aleatorios (O(log  n ) llamadas por inserción o eliminación en lugar de una llamada por inserción) y el procedimiento de inserción es ligeramente más complicado debido a la necesidad de actualizar el número de descendientes por nodo. Una diferencia técnica menor es que, en un treap, hay una pequeña probabilidad de colisión (dos claves que obtienen la misma prioridad), y en ambos casos, habrá diferencias estadísticas entre un verdadero generador de números aleatorios y el generador de números pseudoaleatorios que se usa típicamente en las computadoras digitales. Sin embargo, en cualquier caso, las diferencias entre el modelo teórico de elecciones aleatorias perfectas usado para diseñar el algoritmo y las capacidades de los generadores de números aleatorios reales son extremadamente pequeñas.

Aunque tanto el treap como el árbol de búsqueda binaria aleatorizado tienen la misma distribución aleatoria de formas de árboles después de cada actualización, el historial de modificaciones de los árboles realizadas por estas dos estructuras de datos a lo largo de una secuencia de operaciones de inserción y eliminación puede ser diferente. Por ejemplo, en un treap, si se insertan los tres números 1, 2 y 3 en el orden 1, 3, 2 y luego se elimina el número 2, los dos nodos restantes tendrán la misma relación padre-hijo que tenían antes de la inserción del número del medio. En un árbol de búsqueda binaria aleatorizado, el árbol después de la eliminación tiene la misma probabilidad de ser cualquiera de los dos árboles posibles en sus dos nodos, independientemente de cómo se veía el árbol antes de la inserción del número del medio.

Trato implícito

Un treap implícito ^{[8] [¿ fuente no confiable? ]} es una variación simple de un treap ordinario que puede verse como una matriz dinámica que admite las siguientes operaciones en : ${\displaystyle O(\log n)}$

• Insertar un elemento en cualquier posición
• Eliminar un elemento de cualquier posición
• Encontrar la suma, mínimo o máximo de elementos en un rango dado.
• Adición, pintura en un rango determinado
• Invertir elementos en un rango determinado

La idea detrás de un árbol implícito es utilizar el índice de la matriz como clave, pero no almacenarlo explícitamente. De lo contrario, una actualización (inserción/eliminación) daría como resultado cambios en las claves de los nodos del árbol. ${\displaystyle O(n)}$

El valor de la clave ( clave implícita) de un nodo T es el número de nodos menores que ese nodo más uno. Nótese que dichos nodos pueden estar presentes no sólo en su subárbol izquierdo sino también en los subárboles izquierdos de sus antecesores P, si T está en el subárbol derecho de P.

Por lo tanto, podemos calcular rápidamente la clave implícita del nodo actual mientras realizamos una operación acumulando la suma de todos los nodos a medida que descendemos por el árbol. Tenga en cuenta que esta suma no cambia cuando visitamos el subárbol izquierdo, pero aumentará cuando visitemos el subárbol derecho. ${\displaystyle cnt(T\rightarrow L)+1}$

El algoritmo de unión para un treap implícito es el siguiente:

unión vacía ( pitem & t , pitem l , pitem r ) {          si ( ! l || ! r )    t = l ? l : r ;       de lo contrario si ( l -> prior > r -> prior )     unir ( l -> r , l -> r , r ), t = l ;       demás unir ( r -> l , l , r -> l ), ​​t = r ;       actualizar_cnt ( t ); }

^[8] El algoritmo de división para un treap implícito es el siguiente:

void split ( pitem t , pitem & l , pitem & r , int clave , int suma = 0 ) {                 si ( ! t )  devuelve vacío ( l = r = 0 );        int cur_key = add + cnt ( t -> l ); //clave implícita       si ( clave <= cur_key )    dividir ( t -> l , l , t -> l , clave , agregar ), r = t ;         demás dividir ( t -> r , t -> r , r , clave , sumar + 1 + cnt ( t -> l )), l = t ;             actualizar_cnt ( t ); }

^[8]

Operaciones

Insertar elemento

Para insertar un elemento en la posición pos dividimos la matriz en dos subsecciones [0...pos-1] y [pos..sz] llamando a la función split y obtenemos dos árboles y . Luego fusionamos con el nuevo nodo llamando a la función join . Finalmente llamamos a la función join para fusionar y . ${\displaystyle T1}$ ${\displaystyle T2}$ ${\displaystyle T1}$ ${\displaystyle T1}$ ${\displaystyle T2}$

Eliminar elemento

Encontramos el elemento a eliminar y realizamos una unión en sus hijos L y R. Luego reemplazamos el elemento a eliminar con el árbol resultante de la operación de unión.

Encuentra la suma, el mínimo o el máximo en un rango dado

Para realizar este cálculo procederemos de la siguiente manera:

• Primero crearemos un campo adicional F para almacenar el valor de la función de destino para el rango representado por ese nodo. Crearemos una función que calcule el valor F en función de los valores de los hijos L y R del nodo. Llamaremos a esta función de destino al final de todas las funciones que modifican el árbol, es decir , split y join.
• En segundo lugar, necesitamos procesar una consulta para un rango determinado [A..B]: llamaremos a la función s split dos veces y dividiremos el treap en que contiene , que contiene , y que contiene . Después de que se responda la consulta, llamaremos a la función join dos veces para restaurar el treap original. ${\displaystyle T1}$ ${\displaystyle \{1..A-1\}}$ ${\displaystyle T2}$ ${\displaystyle \{A..B\}}$ ${\displaystyle T3}$ ${\displaystyle \{B+1..n\}}$

Adición/pintura en un rango determinado

Para realizar esta operación procederemos de la siguiente manera:

• Crearemos un campo extra D que contendrá el valor añadido para el subárbol. Crearemos una función push que se utilizará para propagar este cambio desde un nodo a sus hijos. Llamaremos a esta función al comienzo de todas las funciones que modifican el árbol, es decir , split y join, de modo que después de cualquier cambio realizado en el árbol, la información no se pierda.

Invertir en un rango determinado

Para demostrar que el subárbol de un nodo determinado debe invertirse para cada nodo, crearemos un campo booleano adicional R y estableceremos su valor en verdadero. Para propagar este cambio, intercambiaremos los hijos del nodo y estableceremos R en verdadero para todos ellos.

Véase también

• Árbol de segmentos para suma, mínimo o máximo. El árbol de segmentos de Wikipedia trata sobre geometría computacional, y las solicitudes como la suma se describen en el árbol de Fenwick , que es un árbol implícito y no es compatible con la inserción y eliminación en el medio. Si el árbol implícito no es posible, se utiliza el árbol explícito, llamado árbol de segmentos , pero Wikipedia carece de una página adecuada
• Árbol de estadísticas de orden para indexación. Es como un árbol de segmentos diseñado para sumar "1" en cada nodo.

Véase también

• Búsqueda con los dedos

Referencias

1. Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF) , 30.º Simposio anual sobre fundamentos de la informática , Washington, DC: IEEE Computer Society Press, págs. 540-545, doi :10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1
2. Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica , 16 (4/5): 464–497, doi :10.1007/s004539900061 (inactivo el 1 de noviembre de 2024){{citation}}: CS1 maint: DOI inactivo a partir de noviembre de 2024 ( enlace )
3. Naor, M. ; Nissim, K. (abril de 2000), "Revocación de certificados y actualización de certificados" (PDF) , IEEE Journal on Selected Areas in Communications , 18 (4): 561–570, doi :10.1109/49.839932, S2CID  13833836^{[ enlace muerto permanente ]} .
4. Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Operaciones de conjuntos rápidos utilizando treaps", Actas del décimo simposio anual de la ACM sobre algoritmos y arquitecturas paralelas - SPAA '98 , Nueva York, NY, EE. UU.: ACM, págs. 16-26, doi : 10.1145/277651.277660, ISBN 0-89791-989-0, Número de identificación del sujeto  7342709.
5. Liljenzin, Olle (2013). "Conjuntos y mapas persistentes confluentes". arXiv : 1301.3388 . Código Bibliográfico :2013arXiv1301.3388L. {{cite journal}}: Requiere citar revista |journal=( ayuda )
6. Conjuntos y mapas confluentes en GitHub
7. Martínez, Conrado; Roura, Salvador (1997), "Árboles binarios de búsqueda aleatorizados", Journal of the ACM , 45 (2): 288–323, doi : 10.1145/274787.274812 , S2CID  714621
8. "Treap - Algoritmos de programación competitiva". cp-algorithms.com . Consultado el 21 de noviembre de 2021 .

Enlaces externos

• Recopilación de referencias e información sobre treap por Cecilia Aragon
• Estructuras de datos abiertas - Sección 7.2 - Treap: un árbol de búsqueda binaria aleatorizado, Pat Morin
• Trap animado
• Árboles binarios de búsqueda aleatorios. Notas de clase de un curso dictado por Jeff Erickson en la UIUC. A pesar del título, se trata principalmente de treaps y listas de omisión ; los árboles binarios de búsqueda aleatorios se mencionan solo brevemente.
• Un almacén de clave-valor de alto rendimiento basado en treap de Junyi Sun
• Implementación de treaps en VB6. Implementación de treaps en Visual Basic 6 como objeto COM.
• Implementación de un treap en ActionScript3
• Treap y duptreap en memoria con Python y Cython puros
• Treaps en C#. Por Roy Clemmons
• Go puro en memoria, treaps inmutables
• Biblioteca de almacenamiento de clave-valor de treap persistente de Pure Go