Árbol desplegado

Un árbol splay es un árbol de búsqueda binaria con la propiedad adicional de que los elementos accedidos recientemente se pueden volver a acceder rápidamente. Al igual que los árboles de búsqueda binaria autoequilibrados , un árbol splay realiza operaciones básicas como inserción, búsqueda y eliminación en un tiempo amortizado de O (log n ) . Para patrones de acceso aleatorios extraídos de una distribución aleatoria no uniforme, su tiempo amortizado puede ser más rápido que logarítmico, proporcional a la entropía del patrón de acceso. Para muchos patrones de operaciones no aleatorias, los árboles splay también pueden tener un tiempo mejor que logarítmico, sin requerir conocimiento previo del patrón. Según la conjetura de optimalidad dinámica no probada, su rendimiento en todos los patrones de acceso está dentro de un factor constante del mejor rendimiento posible que podría lograr cualquier otro árbol de búsqueda binaria autoajustable, incluso uno seleccionado para ajustarse a ese patrón. El árbol splay fue inventado por Daniel Sleator y Robert Tarjan en 1985. ^{[ 1 ]}

Todas las operaciones normales en un árbol de búsqueda binaria se combinan con una operación básica llamada splaying . El splaying del árbol para un elemento específico reorganiza el árbol de manera que dicho elemento se coloque en la raíz. Una forma de lograr esto con la operación de búsqueda básica es realizar primero una búsqueda estándar en el árbol binario para el elemento en cuestión y luego usar rotaciones de árbol de una manera específica para colocar el elemento en la raíz. Alternativamente, un algoritmo descendente puede combinar la búsqueda y la reorganización del árbol en una sola fase.

El buen rendimiento de un árbol splay depende de su capacidad de autooptimización, ya que los nodos de uso frecuente se acercan a la raíz, donde se puede acceder a ellos más rápidamente. La altura máxima, aunque improbable, es O( n ), con un promedio de O(log n ). Tener los nodos de uso frecuente cerca de la raíz representa una ventaja para muchas aplicaciones prácticas (véase también localidad de referencia ) y resulta especialmente útil para implementar cachés y algoritmos de recolección de basura .

Las ventajas incluyen:

• Rendimiento comparable: El rendimiento en el caso promedio es tan eficiente como el de otros árboles. ^{[ 3 ]}
• Bajo consumo de memoria : Los árboles Splay no necesitan almacenar ningún dato contable.

La desventaja más significativa de los árboles splay es que su altura puede ser lineal. ^{[ 2 ] : 1} Por ejemplo, esto ocurrirá tras acceder a todos los n elementos en orden no decreciente. Dado que la altura del árbol corresponde al tiempo de acceso en el peor de los casos, esto significa que el coste real de una sola operación puede ser elevado. Sin embargo, el coste de acceso amortizado de este peor caso es logarítmico, O(log n ). Además, el coste de acceso esperado puede reducirse a O(log n ) mediante el uso de una variante aleatoria. ^{[ 4 ]}

La representación de los árboles splay puede cambiar incluso cuando se accede a ellos en modo de solo lectura (es decir, mediante operaciones de búsqueda ). Esto complica su uso en entornos multihilo. En concreto, se requiere una gestión adicional si se permite que varios hilos realicen operaciones de búsqueda simultáneamente. Esto también los hace inadecuados para su uso general en programación puramente funcional, aunque incluso en este ámbito pueden utilizarse de forma limitada para implementar colas de prioridad.

Finalmente, cuando el patrón de acceso es aleatorio, la sobrecarga adicional de dispersión añade un factor constante significativo al coste en comparación con alternativas menos dinámicas.

Como se mencionó anteriormente, el splaying se realiza durante una segunda pasada ascendente sobre la ruta de acceso de un nodo. Es posible registrar la ruta de acceso durante la primera pasada para usarla durante la segunda, pero esto requiere espacio adicional durante la operación de acceso. Otra alternativa es mantener un puntero padre en cada nodo, lo que evita la necesidad de espacio adicional durante las operaciones de acceso, pero puede reducir la eficiencia general del tiempo debido a la necesidad de actualizar dichos punteros. ^{[ 1 ]}

Otro método que se puede utilizar se basa en el argumento de que el árbol se puede reestructurar durante el recorrido de acceso en lugar de realizar una segunda pasada. Esta rutina de splaying descendente utiliza tres conjuntos de nodos: árbol izquierdo, árbol derecho y árbol central. Los dos primeros contienen todos los elementos del árbol original que se sabe que son menores o mayores que el elemento actual, respectivamente. El árbol central consta del subárbol con raíz en el nodo actual. Estos tres conjuntos se actualizan a lo largo del recorrido de acceso mientras se controlan las operaciones de splay. Otro método, el semisplaying, modifica el caso zig-zig para reducir la cantidad de reestructuración realizada en todas las operaciones. ^{[ 1 ] [ 6 ]}

A continuación se presenta una implementación de árboles splay en C++, que utiliza punteros para representar cada nodo del árbol. Esta implementación se basa en la versión de splay ascendente y utiliza el segundo método de eliminación en un árbol splay. Además, a diferencia de la definición anterior, esta versión en C++ no realiza el splay en las búsquedas, sino únicamente en las inserciones y eliminaciones; por lo tanto, la operación de búsqueda tiene una complejidad temporal lineal.

#include <functional>#ifndef SPLAY_TREE #define SPLAY_TREEplantilla < typename T , typename Comp = std :: less < T >> clase splay_tree { privado : Comp comp ; unsigned long p_size ; struct nodo { nodo * izquierda , * derecha ; nodo * padre ; T clave ; nodo ( const T & init = T ()) : izquierda ( nullptr ), derecha ( nullptr ), padre ( nullptr ), clave ( init ) { } ~ nodo () {} } * raíz ; void left_rotate ( nodo * x ) { nodo * y = x -> derecha ; if ( y ) { x -> derecha = y -> izquierda ; if ( y -> izquierda ) y -> izquierda -> padre = x ; y -> padre = x -> padre ; } if ( ! x -> padre ) raíz = y ; else if ( x == x -> padre -> izquierda ) x -> padre -> izquierda = y ; else x -> padre -> derecha = y ; if ( y ) y -> izquierda = x ; x -> padre = y ; } void right_rotate ( nodo * x ) { nodo * y = x -> izquierda ; if ( y ) { x -> izquierda = y -> derecha ; if ( y -> derecha ) y -> derecha -> padre = x ; y -> padre = x -> padre ; } if ( ! x -> padre ) raíz = y ; else if ( x == x -> padre -> izquierda ) x -> padre -> izquierda = y ; else x ->padre -> derecha = y ; si ( y ) y -> derecha = x ; x -> padre = y ; } void splay ( nodo * x ) { mientras ( x -> padre ) { si ( !x -> padre -> padre ) { if ( x -> padre -> izquierda == x ) rotación_derecha ( x -> padre ); else rotación_izquierda ( x -> padre ); } else if ( x -> padre -> izquierda == x && x -> padre -> padre -> izquierda == x -> padre ) { rotación_derecha ( x -> padre -> padre ); rotación_derecha ( x -> padre ); } else if ( x -> padre -> derecha == x && x -> padre -> padre -> derecha == x -> padre ) { rotación_izquierda ( x -> padre -> padre ); rotación_izquierda ( x -> padre ); } else if ( x -> padre -> izquierda == x && x -> padre -> padre -> derecha == x -> padre ) { rotación_derecha ( x -> padre ); rotación_izquierda ( x -> padre ); } else {left_rotate ( x -> parent ); right_rotate ( x -> parent ); } } } void replace ( node * u , node * v ) { if ( ! u -> parent ) root = v ; else if ( u == u -> parent -> left ) u -> parent -> left = v ; else u -> parent -> right = v ; if ( v ) v -> parent = u -> parent ; } node * subtree_minimum ( node * u ) { while ( u -> left ) u = u -> left ; return u ; } node * subtree_maximum ( node * u ) { while ( u -> right ) u = u -> right ; return u ; } public : splay_tree () : root ( nullptr ), p_size ( 0 ) { } void insert ( const T & key ) { node * z = root ; node * p = nullptr ; mientras ( z ) { p = z ; si ( comp ( z -> key , key )) z = z -> right ; de lo contrario z = z ->izquierda ; } z = nuevo nodo ( clave ); z -> padre = p ; si ( ! p ) raíz = z ; si no si ( comp ( p -> clave , z -> clave )) p -> derecha = z ; si no p -> izquierda = z ; splay ( z ); p_size ++ ; } nodo * encontrar ( const T & clave ) { nodo * z = raíz ; mientras ( z ) { si ( comp ( z -> clave , clave )) z = z -> derecha ; si no si ( comp ( clave , z -> clave )) z = z -> izquierda ; si no, devolver z ; } devolver nullptr ; } void borrar ( const T & clave ) { nodo * z = encontrar ( clave ); si ( ! z ) devolver ; splay ( z ); si ( ! z -> izquierda ) reemplazar ( z , z -> derecha ); si no si ( ! z -> derecha ) reemplazar ( z , z -> izquierda ); else { nodo * y = subárbol_mínimo ( z -> derecha ); si ( y ->padre != z ) { reemplazar ( y , y -> derecha ); y -> derecha = z -> derecha ; y -> derecha -> padre = y ; } reemplazar ( z , y ); y -> izquierda = z -> izquierda ; y -> izquierda -> padre = y ; } eliminar z ; p_size -- ; }/* //la implementación alternativa  void erase(const T &key) {  node *z = find(key);  if (!z) return;  splay(z);  node *s = z->left;  node *t = z->right;  delete z;  node *sMax = NULL;  if (s) {  s->parent = NULL;  sMax = subtree_maximum(s);  splay(sMax);  root = sMax;  }  if (t) {  if (s)  sMax->right = t;  else  root = t;  t->parent = sMax;  }  p_size--;  } */ const T & minimum () { return subtree_minimum ( root ) -> key ; } const T & maximum () { return subtree_maximum ( root ) -> key ; } bool empty () const { return root == nullptr ; } unsigned long size () const { return p_size ; } };#endif // SPLAY_TREE

Se puede realizar un análisis amortizado simple de árboles de dispersión estáticos utilizando el método potencial . Definir:

• tamaño( r ) = el número de nodos en el subárbol con raíz en el nodo r (incluido r ).
• rango( r ) = log ₂ (tamaño( r )).
• Φ = la suma de los rangos de todos los nodos del árbol.

Φ tenderá a ser alto para árboles mal equilibrados y bajo para árboles bien equilibrados.

Para aplicar el método del potencial , primero calculamos ΔΦ: el cambio en el potencial causado por una operación de dispersión. Verificamos cada caso por separado. Denotamos por rango' la función de rango después de la operación. x, p y g son los nodos afectados por la operación de rotación (ver figuras anteriores).

Existen varios teoremas y conjeturas con respecto al tiempo de ejecución en el peor de los casos para realizar una secuencia S de m accesos en un árbol splay que contiene n elementos.

Además de las garantías de rendimiento comprobadas para los árboles splay, existe una conjetura no demostrada de gran interés proveniente del artículo original de Sleator y Tarjan. Esta conjetura se conoce como la conjetura de optimalidad dinámica y básicamente afirma que los árboles splay tienen un rendimiento tan bueno como cualquier otro algoritmo de árbol de búsqueda binaria, salvo por un factor constante.

Conjetura de optimalidad dinámica: ^{[ 1 ]} Sea${\displaystyle A}$cualquier algoritmo de árbol de búsqueda binaria que acceda a un elemento${\displaystyle x}$recorriendo el camino desde la raíz hasta${\displaystyle x}$a un costo de${\displaystyle d(x)+1}$y que entre accesos puede realizar cualquier rotación en el árbol a un costo de 1 por rotación. Sea${\displaystyle A(S)}$ser el costo de${\displaystyle A}$para realizar la secuencia${\displaystyle S}$de accesos. Entonces, el costo para que un árbol splay realice los mismos accesos es${\displaystyle O[n+A(S)]}$.

Existen varios corolarios de la conjetura de optimalidad dinámica que aún no han sido demostrados:

Conjetura de recorrido: ^{[ 1 ]} Sea${\displaystyle T_{1}}$y${\displaystyle T_{2}}$Sean dos árboles splay que contengan los mismos elementos.${\displaystyle S}$sea ​​la secuencia obtenida al visitar los elementos en${\displaystyle T_{2}}$en preorden (es decir, orden de búsqueda en profundidad). El costo total de realizar la secuencia${\displaystyle S}$de accesos en${\displaystyle T_{1}}$es${\displaystyle O(n)}$.

Conjetura de Deque: ^{[ 11 ] [ 13 ] [ 14 ]} Sea${\displaystyle S}$ser una secuencia de${\displaystyle m}$operaciones de cola de doble extremo (push, pop, inject, eyec). Luego, el costo de realizar${\displaystyle S}$en un árbol ramificado es${\displaystyle O(m+n)}$.

Conjetura de división: ^{[ 6 ]} Sea${\displaystyle S}$sea ​​cualquier permutación de los elementos del árbol splay. Entonces, el costo de eliminar los elementos en el orden${\displaystyle S}$, dividiendo cada árbol en dos árboles separados en cada elemento eliminado, es${\displaystyle O(n)}$.

Para reducir el número de operaciones de reestructuración, es posible reemplazar el splaying con semi-splaying , en el que un elemento se splaya solo hasta la mitad hacia la raíz. ^{[ 1 ] [ 2 ]}

Otra forma de reducir la reestructuración es realizar una dispersión completa, pero solo en algunas de las operaciones de acceso: solo cuando la ruta de acceso sea más larga que un umbral, o solo en las primeras m operaciones de acceso. ^{[ 1 ]}

El CBTree aumenta el árbol splay con recuentos de acceso en cada nodo y los utiliza para reestructurarlo con poca frecuencia. Una variante del CBTree, llamada LazyCBTree, realiza como máximo una rotación en cada búsqueda. Esto se utiliza junto con un esquema de validación optimista de mano a mano para crear un árbol concurrente autoajustable. ^{[ 15 ]}

Utilizando técnicas de compresión de punteros, ^{[ 16 ]} es posible construir un árbol splay conciso .

• Árbol AVL
• Árbol B
• Árbol de dedos
• Geometría de los árboles de búsqueda binaria
• Estructura del conjunto de trabajo de Iacono
• Árbol de enlace/corte
• Lista de estructuras de datos
• Árbol del chivo expiatorio
• Splaysort , un algoritmo de ordenación que utiliza árboles splay.
• Árbol en T
• Trepa
• rotación de árboles
• Árboles
• Cremallera (estructura de datos)

• Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E. (2014). "El árbol CB: un árbol de búsqueda práctico, concurrente y autoajustable" . Distributed Computing . 27 (6): 393– 417. doi : 10.1007/s00446-014-0229-0 .
• Albers, Susanne; Karpinski, Marek (28 de febrero de 2002). "Árboles de dispersión aleatorios: resultados teóricos y experimentales" (PDF) . Information Processing Letters . 81 (4): 213– 221. doi : 10.1016/s0020-0190(01)00230-7 .
• Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Fagerberg, Rolf (2010). "Un árbol de búsqueda binaria competitivo O(log log n) con tiempos de acceso óptimos en el peor de los casos". En Kaplan, H. (ed.). Teoría de algoritmos - SWAT 2010. Notas de clase en ciencias de la computación. Vol.  6139. pp. 38–49 . arXiv : 1003.0139 . doi : 10.1007/978-3-642-13731-0_5 . ISBN  978-3-642-13730-3.
• Allen, Brian; Munro, Ian (octubre de 1978). "Árboles de búsqueda binaria autoorganizados" . Journal of the ACM . 25 (4): 526– 535. doi : 10.1145/322092.322094 . S2CID 15967344 . 
• Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (enero de 2009). "Rehabilitación de un niño no querido: semi-splaying" (PDF) . Software: Practice and Experience . 39 (1): 33– 45. CiteSeerX 10.1.1.84.790 . doi : 10.1002/spe.v39:1 . hdl : 11382/102133 . Los resultados muestran que el semi-splaying, que se introdujo en el mismo artículo que el splaying, funciona mejor que el splaying en casi todas las condiciones posibles. Esto hace que el semi-splaying sea una buena alternativa para todas las aplicaciones donde normalmente se aplicaría el splaying. La razón por la que el splaying se volvió tan prominente mientras que el semi-splaying es relativamente desconocido y mucho menos estudiado es difícil de entender. 
• Cole, Richard; Mishra, Bud; Schmidt, Jeanette; Siegel, Alan (enero de 2000). "Sobre la conjetura del dedo dinámico para árboles splay. Parte I: Ordenación splay de secuencias de log n-bloques". SIAM Journal on Computing . 30 (1): 1– 43. CiteSeerX 10.1.1.36.4558 . doi : 10.1137/s0097539797326988 . 
• Cole, Richard (enero de 2000). "Sobre la conjetura del dedo dinámico para árboles splay. Parte II: La demostración". SIAM Journal on Computing . 30 (1): 44– 85. CiteSeerX 10.1.1.36.2713 . doi : 10.1137/S009753979732699X . 
• Elmasry, Amr (abril de 2004). "Sobre el teorema de acceso secuencial y la conjetura Deque para árboles splay" . Theoretical Computer Science . 314 (3): 459– 466. doi : 10.1016/j.tcs.2004.01.019 .
• Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014). Estructuras de datos y algoritmos en Java (6.ª  ed.). Wiley. pág.  506. ISBN 978-1-118-77133-4.
• Grinberg, Dennis; Rajagopalan, Sivaramakrishnan; Venkatesan, Ramarathnam; Wei, Victor K. (1995). "Árboles splay para compresión de datos" . En Clarkson, Kenneth L. (ed.). Actas del Sexto Simposio Anual ACM-SIAM sobre Algoritmos Discretos, 22-24 de enero de 1995. San Francisco, California, EE. UU . ACM/SIAM. págs. 522-530 . La profundidad media de acceso en un árbol splay es proporcional a la entropía. 
• Knuth, Donald (1997). El arte de la programación informática . Vol.  3: Ordenación y búsqueda (3.ª  ed.). Addison-Wesley. pág.  478. ISBN 0-201-89685-0Se sabe que el tiempo necesario para acceder a los datos en un árbol splay es, como máximo, un pequeño múltiplo constante del tiempo de acceso de un árbol estáticamente óptimo, cuando se amortiza sobre cualquier serie de operaciones.
• Lucas, Joan M. (1991). «Sobre la competitividad de los árboles splay: relaciones con el problema de unión-búsqueda». Algoritmos en línea: Actas de un taller de DIMACS, 11-13 de febrero de 1991. Serie de Matemáticas Discretas e Informática Teórica. Vol.  7. Centro de Matemáticas Discretas e Informática Teórica . págs. 95-124 . ISBN  0-8218-7111-0.
• Pettie, Seth (2008). "Árboles Splay, secuencias de Davenport-Schinzel y la conjetura de Deque". Actas del 19.º Simposio ACM-SIAM sobre algoritmos discretos (PDF) . págs. 1115–1124 . arXiv : 0707.2160 . 
• Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Árboles de búsqueda binaria autoajustables" (PDF) . Journal of the ACM . 32 (3): 652– 686. doi : 10.1145/3828.3835 . S2CID 1165848 . 
• Sundar, Rajamani (1992). "Sobre la conjetura Deque para el algoritmo splay". Combinatorica . 12 (1): 95– 124. doi : 10.1007/BF01191208 . S2CID 27422556 . 
• Tarjan, Robert E. (1985). "El acceso secuencial en árboles splay requiere tiempo lineal". Combinatorica . 5 (4): 367– 378. doi : 10.1007/BF02579253 . S2CID 34757821 . 
• Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Kuszmaul, William; Tagliavini, Guido (2023). «Tiny Pointers». Actas del Simposio Anual ACM-SIAM de 2023 sobre Algoritmos Discretos (SODA) . págs. 477–508 . doi : 10.1137/1.9781611977554.ch21 . ISBN  978-1-61197-755-4. S2CID 244709005 . 

• Diccionario de algoritmos y estructuras de datos del NIST: Árbol Splay
• Implementaciones en C y Java (por Daniel Sleator)
• Consejos para visualizaciones de árboles de dispersión
• Implementación rápida y eficiente de árboles Splay
• Implementación en Java de un árbol Splay descendente