Trepa

En informática , el árbol de búsqueda binaria aleatorio (treap) y el árbol de búsqueda binaria aleatorio (binary search tree) son dos formas estrechamente relacionadas de estructuras de datos de árboles de búsqueda binaria que mantienen un conjunto dinámico de claves ordenadas y permiten búsquedas binarias entre ellas. Tras 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 requiere un tiempo logarítmico.

Descripción

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

El árbol de búsqueda binaria (treap) fue descrito por primera vez por Raimund Seidel y Cecilia R. Aragon en 1989; ^{[ 1 ]}^{[ 2 ]} su nombre es una combinación de árbol y montón . Es un árbol cartesiano en el que a cada clave se le asigna una prioridad numérica (elegida aleatoriamente). Al igual que en cualquier árbol de búsqueda binaria, 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 como un montón: es decir, el número de prioridad de cualquier nodo que no sea una hoja debe ser mayor o igual que la prioridad de sus hijos. Así, como en los árboles cartesianos en 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 a la derecha de ese nodo.

Una forma equivalente de describir el treap es que podría formarse insertando los nodos de mayor prioridad primero en un árbol de búsqueda binaria sin realizar ningún reequilibrio. Por lo tanto, si las prioridades son números aleatorios independientes (de una distribución sobre un espacio suficientemente grande de prioridades posibles para asegurar que sea muy improbable 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 de búsqueda binaria aleatorio , un árbol de búsqueda formado al insertar los nodos sin reequilibrio en un orden de inserción elegido aleatoriamente. Dado que se sabe que los árboles de búsqueda binaria aleatorios tienen una altura logarítmica con alta probabilidad, lo mismo ocurre con los treaps. Esto refleja el argumento del árbol de búsqueda binaria de que quicksort se ejecuta en un orden esperado. $O(n\log n)$ tiempo. Si los árboles de búsqueda binaria son soluciones a la versión dinámica del problema de ordenación, entonces los Treaps corresponden específicamente a la ordenación rápida dinámica donde las prioridades guían las elecciones de pivote.

Aragon y Seidel también sugieren asignar mayor prioridad a los nodos de acceso frecuente, 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 de acceso frecuente tendrían más probabilidades de estar cerca de la raíz del árbol, lo que haría que las búsquedas en ellos fueran más rápidas.

Naor y Nissim ^{[ 3 ]} describen una aplicación para el mantenimiento de 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 determine que debería 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, simplemente elimínelo. Si x tiene un único hijo z , elimine x del árbol y haga que z sea 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 resulta en uno de los casos anteriores. En este último caso, el intercambio puede violar la propiedad de ordenación del montón para z , por lo que podrían ser necesarias rotaciones adicionales para restaurar esta propiedad.

Construyendo un treap

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

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 de "procesamiento masivo" en los treaps: unión , intersección y diferencia de conjuntos . Estas dependen de dos operaciones auxiliares: división y unión .

Para dividir un treap en dos treaps más pequeños (uno con clave menor que x y otro con clave mayor que x) , inserta x en el treap con prioridad máxima (mayor que la prioridad de cualquier nodo del treap). Tras 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 tiene el mismo coste que una sola inserción en el treap.
Al unir dos treaps que son producto de una división anterior, se puede asumir con seguridad que el valor máximo en el primer treap es menor que el valor mínimo en el segundo treap. Cree un nuevo nodo con 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 heap y su hijo derecho en el segundo heap. Rote según sea necesario para corregir el orden del heap. Después de eso, será un nodo hoja y se puede eliminar fácilmente. El resultado es un treap fusionado a partir de los dos treaps originales. Esto es efectivamente "deshacer" una división y cuesta lo mismo. De manera más general, la operación de unión puede funcionar con dos treaps y una clave con prioridad arbitraria (es decir, no necesariamente la más alta).

{\displaystyle T_{1}} — Unirse realizado en treaps $T_{1}$ y $T_{2}$ . Hijo derecho de $T_{1}$ después de que la unión se define como una unión de su antiguo hijo derecho y $T_{2}$ .

El algoritmo de unión es el siguiente:

función unir(L, k, R) si prior(k, k(L)) y prior(k, k(R)) devolver Nodo(L, k, R) si prior(k(L), k(R)) devolver Nodo(izquierda(L), k(L), unir(derecha(L), k, R)) devolver Nodo(unir(L, k, izquierda(R)), k(R), derecha(R))

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

El algoritmo de división es el siguiente:

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

La unión de dos treaps $t 1$ y $t 2$ , que representan los conjuntos $A$ y $B$ , es un treap $t$ que representa $A \cup B.$ El siguiente algoritmo recursivo calcula la unión:

función unión(t ₁ , t ₂ ): si t ₁ = nil: devolver t ₂si t ₂ = nil: devolver t ₁si prioridad(t ₁ ) < prioridad(t ₂ ): intercambiar t ₁ y t ₂ t _< , t _> ← dividir t ₂ en clave(t ₁ ) devolver unir(unión(izquierda(t ₁ ), t _< ), clave(t ₁ ), unión(derecha(t ₁ ), t _> ))

Aquí, se supone que la función `split` devuelve dos árboles: uno con las claves menores que la clave de entrada y otro con las claves mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva in situ).

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

Split y Union llaman a Join pero no manejan directamente los criterios de equilibrio de los treaps, dicha implementación generalmente se denomina implementación "basada en join" .

Cabe destacar que si se utilizan los valores hash de las claves como prioridades y los nodos estructuralmente iguales se fusionan durante la construcción, cada nodo fusionado representará de forma única un conjunto de claves. Dado que solo puede existir un nodo raíz simultáneo que represente un conjunto de claves determinado, se puede comprobar la igualdad de dos conjuntos mediante una comparación de punteros, que es constante en el tiempo.

Esta técnica puede utilizarse para mejorar los algoritmos de fusión y lograr un rendimiento 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 fallar inmediatamente, devolviendo uno de los conjuntos 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 acotados por $O (d log n / d)$ . ^{[ 5 ]}^{[ 6 ]}

Árbol de búsqueda binaria aleatorio

El árbol de búsqueda binaria 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 de búsqueda binaria aleatorio almacena un pequeño número 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 va a insertar 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 en caso 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 número de descendientes es utilizado por el algoritmo 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 ser utilizadas como hijos izquierdo y derecho del nuevo nodo.

El procedimiento de eliminación para un árbol de búsqueda binaria aleatorio utiliza la misma información por nodo que el procedimiento de inserción, pero a diferencia de este último, solo requiere 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 van a unir tienen, en promedio, una profundidad Θ(log n); unir dos árboles de tamaño n y m requiere, en promedio, Θ(log(n+m)) elecciones aleatorias. Si el subárbol izquierdo o derecho del nodo que se va a eliminar está vacío, la operación de unión es trivial; de lo contrario, el hijo izquierdo o derecho del nodo eliminado se selecciona como la nueva raíz del subárbol con una probabilidad proporcional a su número de descendientes, y la unión procede recursivamente.

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 requiere 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 complejo debido a la necesidad de actualizar el número de descendientes por nodo. Una pequeña diferencia técnica es que, en un treap, existe una pequeña probabilidad de colisión (dos claves con la misma prioridad), y en ambos casos, habrá diferencias estadísticas entre un generador de números aleatorios verdadero y el generador de números pseudoaleatorios que se usa habitualmente en las computadoras digitales. Sin embargo, en cualquier caso, las diferencias entre el modelo teórico de elecciones aleatorias perfectas utilizado para diseñar el algoritmo y las capacidades de los generadores de números aleatorios reales son prácticamente nulas.

Aunque tanto el árbol de búsqueda binaria aleatorio (treap) como el árbol de búsqueda binaria aleatorio (binary search tree) presentan la misma distribución aleatoria de formas de árbol tras cada actualización, el historial de modificaciones realizadas a los árboles 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 números 1, 2 y 3 en el orden 1, 3, 2, y luego se elimina el número 2, los dos nodos restantes mantendrán la misma relación padre-hijo que tenían antes de la inserción del número central. En un árbol de búsqueda binaria aleatorio, el árbol resultante tras la eliminación tiene la misma probabilidad de ser cualquiera de los dos árboles posibles en sus dos nodos, independientemente de cómo fuera el árbol antes de la inserción del número central.

trepa implícito

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

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

La idea detrás de un treap implícito es usar el índice del array como clave, pero no almacenarlo explícitamente. De lo contrario, una actualización (inserción/eliminación) resultaría en cambios de las claves en $O(n)$ nodos del árbol.

El valor clave ( clave implícita) de un nodo T es el número de nodos menores que ese nodo más uno. Cabe destacar que dichos nodos pueden estar presentes no solo en su subárbol izquierdo, sino también en los subárboles izquierdos de sus ancestros P, si T se encuentra 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á en $cnt(T\rightarrow L)+1$ cuando visitamos el subárbol correcto.

Considere la siguiente definición:

importar std ;clase ImplicitTreap { privado : int clave ; int prior ; ImplicitTreap * izquierda ; ImplicitTreap * derecha ; público : explícito ImplicitTreap ( int clave = 0 , int prior = std :: rand ()) : clave { clave }, prior { std :: rand ()}, izquierda { nullptr }, derecha { nullptr } {}// gettersint count () const ; void updateCount (); void join ( ImplicitTreap * left , ImplicitTreap * right ); void split ( ImplicitTreap *& left , ImplicitTreap *& right ; int key , int add = 0 ); };

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

void ImplicitTreap::join ( ImplicitTreap * left , ImplicitTreap * right ) { if ( ! left || ! right ) { this = left ? left : right ; } else if ( left- > getPrior () > right- > getPrior ()) { left- > getRight (). join ( left- > getRight , right ); this = left ; } else { right- > getLeft (). join ( left , right- > getLeft ()); this = right ; } updateCount (); }

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

void ImplicitTreap::split ( ImplicitTreap *& left , ImplicitTreap * & right , int key , int add = 0 ) { int currentKey = add + this- > left.count (); // clave implícita if ( key <= currentKey ) { this- > left.split ( left , this- > left , key , add ) ; right = this ; } else { this- > right.split ( this- > right , right , key , add + 1 + this- > left.count ( ) ) ; left = this ; } updateCount ( ) ; }

Operaciones

Insertar elemento

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

Eliminar elemento

Localizamos el elemento que se va a eliminar y realizamos una unión con sus elementos hijos L y R. A continuación, reemplazamos el elemento que se va a eliminar con el árbol resultante de la operación de unión.

Calcular 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 objetivo para el rango representado por ese nodo. Crearemos una función que calcule el valor de F en función de los valores de los hijos L y R del nodo. Llamaremos a esta función objetivo al final de todas las funciones que modifican el árbol, es decir , split y join.
Segundo, necesitamos procesar una consulta para un rango dado [A..B]: Llamaremos a la función s split dos veces y dividiremos el treap en $T1$ que contiene $\{1..A-1\}$ , $T2$ que contiene $\{A..B\}$ , y $T3$ que contiene $\{B+1..n\}$ . Una vez respondida la consulta, llamaremos a la función join dos veces para restaurar el treap original.

Adición/pintura en un rango determinado

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

Crearemos un campo adicional D que contendrá el valor añadido para el subárbol. Crearemos una función `push` que se utilizará para propagar este cambio de un nodo a sus hijos. Llamaremos a esta función al inicio de todas las funciones que modifiquen el árbol, es decir , `split` y `join`, para que, tras 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 dado debe invertirse para cada nodo, crearemos un campo booleano adicional R y le asignaremos el valor verdadero. Para propagar este cambio, intercambiaremos los hijos del nodo y asignaremos el valor verdadero a R para todos ellos.

Véase también

Referencias

↑ Aragon, Cecilia R.; Seidel, Raimund (1989), "Árboles de búsqueda aleatorios" (PDF) , 30.º Simposio anual sobre fundamentos de la informática , Washington, DC: IEEE Computer Society Press, pp. 540–545 , doi : 10.1109/SFCS.1989.63531 , ISBN 0-8186-1982-1
↑ Seidel, Raimund; Aragon, Cecilia R. (1996), "Árboles de búsqueda aleatorios" , Algorithmica , 16 (4/5): 464–497 , doi : 10.1007/BF01940876
↑ Naor, M. ; Nissim, K. (abril de 2000), "Revocación y actualización de certificados" (PDF) , IEEE Journal on Selected Areas in Communications , 18 (4): 561– 570, doi : 10.1109/49.839932 , S2CID 13833836 .
↑ Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Operaciones rápidas con conjuntos usando 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, S2CID 7342709 .
↑ Liljenzin, Olle (2013). "Conjuntos y mapas persistentes confluentes". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
↑ Conjuntos y mapas de Confluent en GitHub
↑ Martínez, Conrado; Roura, Salvador (1997), "Árboles de búsqueda binaria aleatorios" , Journal of the ACM , 45 (2): 288–323 , doi : 10.1145/274787.274812 , S2CID 714621
1 2 3 "Treap - Algoritmos de programación competitiva" . cp-algorithms.com . Consultado el 21/11/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 aleatorio , Pat Morin
Treap animado archivado el 15/03/2005 en Wayback Machine.
Árboles de búsqueda binaria aleatorios . Apuntes de clase de un curso impartido por Jeff Erickson en la UIUC. A pesar del título, el curso trata principalmente sobre treaps y listas de salto ; los árboles de búsqueda binaria aleatorios se mencionan solo brevemente.
Un almacén de clave-valor de alto rendimiento basado en treap por 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, implementados con Python puro y Cython.
Treaps en C# . Por Roy Clemmons
Go puro en memoria, treaps inmutables
Biblioteca de almacenamiento de clave-valor persistente Pure Go treap

[paper89-1] Aragon, Cecilia R.; Seidel, Raimund (1989), "Árboles de búsqueda aleatorios" (PDF) , 30.º Simposio anual sobre fundamentos de la informática , Washington, DC: IEEE Computer Society Press, pp. 540–545 , doi : 10.1109/SFCS.1989.63531 , ISBN 0-8186-1982-1

[paper96-2] Seidel, Raimund; Aragon, Cecilia R. (1996), "Árboles de búsqueda aleatorios" , Algorithmica , 16 (4/5): 464–497 , doi : 10.1007/BF01940876

[3] Naor, M. ; Nissim, K. (abril de 2000), "Revocación y actualización de certificados" (PDF) , IEEE Journal on Selected Areas in Communications , 18 (4): 561– 570, doi : 10.1109/49.839932 , S2CID 13833836 .

[4] Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Operaciones rápidas con conjuntos usando 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, S2CID 7342709 .

[5] Liljenzin, Olle (2013). "Conjuntos y mapas persistentes confluentes". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )

[Confluent_Sets_and_Maps-6] Conjuntos y mapas de Confluent en GitHub

[7] Martínez, Conrado; Roura, Salvador (1997), "Árboles de búsqueda binaria aleatorios" , Journal of the ACM , 45 (2): 288–323 , doi : 10.1145/274787.274812 , S2CID 714621

[:0-8] 1 2 3 "Treap - Algoritmos de programación competitiva" . cp-algorithms.com . Consultado el 21/11/2021 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

Descripción

Operaciones

Operaciones básicas

Construyendo un treap

Operaciones a granel

Árbol de búsqueda binaria aleatorio

Comparación

trepa implícito

Operaciones

Insertar elemento

Eliminar elemento

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

Adición/pintura en un rango determinado

Invertir en un rango determinado

Véase también

Referencias

Enlaces externos

Articulos relacionados