Árbol de expansión

Árbol de búsqueda binaria autoajustable

Un árbol splay es un árbol binario de búsqueda con la propiedad adicional de que los elementos a los que se ha accedido recientemente son rápidamente accesibles nuevamente. Al igual que los árboles binarios de búsqueda 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 los patrones de acceso aleatorio extraídos de una distribución aleatoria no uniforme, su tiempo amortizado puede ser más rápido que el logarítmico, proporcional a la entropía del patrón de acceso. Para muchos patrones de operaciones no aleatorias, también, los árboles splay pueden tardar más que el tiempo logarítmico, sin requerir un 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 binario de búsqueda 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 binario de búsqueda se combinan con una operación básica, llamada "splaying" ( división en espacios). La división en espacios del árbol para un determinado elemento reorganiza el árbol de modo que el elemento se coloque en la raíz del árbol. Una forma de hacer esto con la operación de búsqueda básica es realizar primero una búsqueda estándar en un árbol binario para el elemento en cuestión y luego usar rotaciones de árbol de una manera específica para llevar el elemento a la parte superior. Alternativamente, un algoritmo de arriba hacia abajo puede combinar la búsqueda y la reorganización del árbol en una sola fase.

Ventajas

El buen rendimiento de un árbol de distribución depende del hecho de que se optimiza por sí solo, en el sentido de que los nodos a los que se accede con frecuencia se acercarán a la raíz, donde se puede acceder a ellos más rápidamente. La altura en el peor de los casos (aunque poco probable) es O( n ), y el promedio es O(log n ). Tener nodos de uso frecuente cerca de la raíz es una ventaja para muchas aplicaciones prácticas (consulte también la localidad de referencia ) y es particularmente útil para implementar cachés y algoritmos de recolección de basura .

Las ventajas incluyen:

• Rendimiento comparable: el rendimiento del caso promedio es tan eficiente como el de otros árboles. ^[3]
• Pequeña huella de memoria : los árboles Splay no necesitan almacenar ningún dato contable.

Desventajas

La desventaja más importante de los árboles splay es que la altura de un árbol splay puede ser lineal. ^{[2] : 1} Por ejemplo, este será el caso después de acceder a todos los n elementos en orden no decreciente. Dado que la altura de un árbol corresponde al tiempo de acceso del peor caso, esto significa que el costo real de una sola operación puede ser alto. Sin embargo, el costo de acceso amortizado de este peor caso es logarítmico, O(log n ). Además, el costo de acceso esperado se puede reducir a O(log n ) utilizando una variante aleatoria. ^[4]

La representación de los árboles de distribución puede cambiar incluso cuando se accede a ellos de forma "de solo lectura" (es decir, mediante operaciones de búsqueda ). Esto complica el uso de dichos árboles de distribución en un entorno multiproceso. En concreto, se necesita una gestión adicional si se permite que varios subprocesos realicen operaciones de búsqueda de forma simultánea. Esto también los hace inadecuados para el uso general en la programación puramente funcional, aunque incluso en ese caso se pueden utilizar de forma limitada para implementar colas de prioridad.

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

Operaciones

Extendiéndose

Cuando se accede a un nodo x , se realiza una operación de separación en x para moverlo a la raíz. Una operación de separación es una secuencia de pasos de separación , cada uno de los cuales acerca x a la raíz. Al realizar una operación de separación en el nodo de interés después de cada acceso, los nodos a los que se ha accedido recientemente se mantienen cerca de la raíz y el árbol permanece aproximadamente equilibrado, por lo que proporciona los límites de tiempo amortizados deseados.

Cada paso particular depende de tres factores:

• Si x es el hijo izquierdo o derecho de su nodo padre, p ,
• si p es la raíz o no, y si no
• si p es el hijo izquierdo o derecho de su padre, g (el abuelo de x ).

Existen tres tipos de pasos de separación, cada uno de los cuales tiene dos variantes simétricas: hacia la izquierda y hacia la derecha. Por razones de brevedad, solo se muestra uno de estos dos para cada tipo. (En los diagramas siguientes, los círculos indican nodos de interés y los triángulos indican subárboles de tamaño arbitrario). Los tres tipos de pasos de separación son:

Paso en zigzag: este paso se realiza cuando p es la raíz. El árbol se rota en el borde entre x y p . Los pasos en zigzag existen para solucionar el problema de paridad, se realizarán solo como el último paso en una operación de separación y solo cuando x tenga una profundidad impar al comienzo de la operación.

Paso en zig-zig: este paso se realiza cuando p no es la raíz y x y p son ambos hijos derechos o ambos hijos izquierdos. La siguiente imagen muestra el caso en el que x y p son ambos hijos izquierdos. El árbol se rota en el borde que une p con su padre g , luego se rota en el borde que une x con p . Los pasos en zig-zig son lo único que diferencia a los árboles splay del método de rotación a raíz introducido por Allen y Munro ^[5] antes de la introducción de los árboles splay.

Paso en zigzag: este paso se realiza cuando p no es la raíz y x es un hijo derecho y p es un hijo izquierdo o viceversa ( x es izquierdo, p es derecho). El árbol se rota en el borde entre p y x , y luego se rota en el borde resultante entre x y g .

Unirse

Dados dos árboles S y T tales que todos los elementos de S son más pequeños que los elementos de T, se pueden utilizar los siguientes pasos para unirlos en un solo árbol:

• Despliega el elemento más grande en S. Ahora este elemento está en la raíz de S y tiene un hijo derecho nulo.
• Establezca el hijo derecho de la nueva raíz en T.

Dividir

Dado un árbol y un elemento x , devuelve dos árboles nuevos: uno que contenga todos los elementos menores o iguales a x y el otro que contenga todos los elementos mayores que x . Esto se puede hacer de la siguiente manera:

• Desdobla x . Ahora está en la raíz, por lo que el árbol a su izquierda contiene todos los elementos menores que x y el árbol a su derecha contiene todos los elementos mayores que x .
• Dividir el subárbol derecho del resto del árbol.

Inserción

Para insertar un valor x en un árbol de distribución:

• Inserte x como con un árbol de búsqueda binario normal .
• Realizar una extensión en x .

Como resultado, el nodo x recién insertado se convierte en la raíz del árbol.

Alternativamente:

• Utilice la operación de división para dividir el árbol en el valor de x en dos subárboles: S y T.
• Crea un nuevo árbol en el que x es la raíz, S es su subárbol izquierdo y T su subárbol derecho.

Supresión

Para eliminar un nodo x , utilice el mismo método que con un árbol de búsqueda binario:

• Si x tiene dos hijos:
  • Intercambie su valor con el del nodo más a la derecha de su subárbol izquierdo (su predecesor en orden) o el nodo más a la izquierda de su subárbol derecho (su sucesor en orden).
  • En su lugar, elimine ese nodo.

De esta manera, la eliminación se reduce al problema de quitar un nodo con 0 o 1 hijos. A diferencia de un árbol de búsqueda binario, en un árbol de expansión, después de la eliminación, expandimos el padre del nodo eliminado a la parte superior del árbol.

Alternativamente:

• El nodo que se va a eliminar primero se extiende, es decir, se lleva a la raíz del árbol y luego se elimina. Deja el árbol con dos subárboles.
• Luego los dos subárboles se unen mediante una operación de "unión".

Implementación y variantes

La expansión, como se mencionó anteriormente, se realiza durante un segundo paso de abajo hacia arriba sobre la ruta de acceso de un nodo. Es posible registrar la ruta de acceso durante el primer paso para usarla durante el segundo, pero eso requiere espacio adicional durante la operación de acceso. Otra alternativa es mantener un puntero principal 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 esos punteros. ^[1]

Otro método que se puede utilizar se basa en el argumento de que el árbol se puede reestructurar durante el camino de acceso en lugar de hacer una segunda pasada. Esta rutina de expansión 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 camino de acceso mientras se mantienen bajo control las operaciones de expansión. Otro método, la semiexpansión, modifica el caso zig-zig para reducir la cantidad de reestructuración realizada en todas las operaciones. ^{[1] [6]}

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

#include <funcional> #ifndef ÁRBOL_DE_REPRODUCCIÓN #define ÁRBOL_DE_REPRODUCCIÓNplantilla < typename T , typename Comp = std :: less < T >> clase splay_tree { privado : Comp comp ; unsigned long p_size ; estructura 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 rotación_izquierda ( 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 rotación_derecha ( 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 ; De lo contrario 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 ) girar_derecha ( x -> padre ); de lo contrario girar_izquierda ( x -> padre ); } de lo contrario if ( x -> padre -> izquierda == x && x -> padre -> padre -> izquierda == x -> padre ) { girar_derecha ( x -> padre -> padre ); girar_derecha ( x -> padre ); } de lo contrario if ( x -> padre -> derecha == x && x -> padre -> padre -> derecha == x -> padre ) { girar_izquierda ( x -> padre -> padre ); girar_izquierda ( x -> padre ); } de lo contrario if ( x -> padre -> izquierda == x && x -> padre -> padre -> derecha == x -> padre ) { girar_derecha ( x -> padre ); girar_izquierda ( x -> padre ); } de lo contrario {                                                                        izquierda_rotar ( x -> padre ); derecha_rotar ( x -> padre ); } } } void replace ( nodo * u , nodo * v ) { if ( ! u -> padre ) raíz = v ; de lo contrario if ( u == u -> padre -> izquierda ) u -> padre -> izquierda = v ; de lo contrario u -> padre -> derecha = v ; if ( v ) v -> padre = u -> padre ; } nodo * subárbol_mínimo ( nodo * u ) { while ( u -> izquierda ) u = u -> izquierda ; return u ; } nodo * subárbol_máximo ( nodo * u ) { while ( u -> derecha ) u = u -> derecha ; return u ; } público : splay_tree () : raíz ( nullptr ), p_size ( 0 ) { } void insert ( const T & key ) { nodo * z = raíz ; nodo * p = nullptr ; mientras ( z ) { p = z ; si ( comp ( z -> tecla , tecla )) z = z -> derecha ; de lo contrario z = z ->                                                                                                 izquierda ; } z = nuevo nodo ( clave ); z -> padre = p ; si ( ! p ) raíz = z ; de lo contrario si ( comp ( p -> clave , z -> clave )) p -> derecha = z ; de lo contrario p -> izquierda = z ; splay ( z ); p_size ++ ; } nodo * buscar ( const T & clave ) { nodo * z = raíz ; mientras ( z ) { si ( comp ( z -> clave , clave )) z = z -> derecha ; de lo contrario si ( comp ( clave , z -> clave )) z = z -> izquierda ; de lo contrario devolver z ; } devolver nullptr ; } void borrar ( const T & clave ) { nodo * z = buscar ( clave ); si ( ! z ) devolver ; splay ( z ); si ( ! z -> izquierda ) reemplazar ( z , z -> derecha ); de lo contrario si ( ! z -> derecha ) reemplazar ( z , z -> izquierda ); de lo contrario { 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) {  nodo *z = find(key);  if (!z) return;  splay(z);  nodo *s = z->left;  nodo *t = z->right;  delete z;  nodo *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 // ÁRBOL_DE_REPRODUCCIÓN

Análisis

Se puede realizar un análisis amortizado simple de árboles de expansión estática 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 de potencial , primero calculamos ΔΦ: el cambio en el potencial causado por una operación de rotación. Comprobamos 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 las figuras anteriores).

Paso en zigzag

Paso en zig-zig

Paso en zigzag

El costo amortizado de cualquier operación es ΔΦ más el costo real. El costo real de cualquier operación en zig-zig o en zig-zag es 2, ya que hay que hacer dos rotaciones. Por lo tanto:

Cuando se suma toda la operación de dispersión, esto se eleva a 1 + 3(rank(root)−rank( x )) que es O(log n ), ya que utilizamos la operación Zig como máximo una vez y el costo amortizado de zig es como máximo 1+3(rank'( x )−rank( x )).

Ahora sabemos que el tiempo total amortizado para una secuencia de m operaciones es:

${\displaystyle T_{\mathrm {amortized} }(m)=O(m\log n)}$

Para pasar del tiempo amortizado al tiempo real, debemos sumar la disminución de potencial desde el estado inicial antes de realizar cualquier operación (Φ _i ) hasta el estado final después de completar todas las operaciones (Φ _f ).

${\displaystyle \Phi _{i}-\Phi _{f}=\sum _{x}{\mathrm {rank} _{i}(x)-\mathrm {rank} _{f}(x)}=O(n\log n)}$

donde la notación O grande puede justificarse por el hecho de que para cada nodo x , el rango mínimo es 0 y el rango máximo es log( n ).

Ahora finalmente podemos limitar el tiempo real:

${\displaystyle T_{\mathrm {actual} }(m)=O(m\log n+n\log n)}$

Análisis ponderado

El análisis anterior se puede generalizar de la siguiente manera.

• Asignar a cada nodo r un peso w ( r ).
• Defina tamaño( r ) = la suma de los pesos de los nodos en el subárbol con raíz en el nodo r (incluido r ).
• Defina rango( r ) y Φ exactamente como arriba.

Se aplica el mismo análisis y el costo amortizado de una operación de expansión es nuevamente:

${\displaystyle 1+3(\mathrm {rank} (root)-\mathrm {rank} (x))}$

donde W es la suma de todos los pesos.

La disminución del potencial inicial al final está limitada por:

${\displaystyle \Phi _{i}-\Phi _{f}\leq \sum _{x\in tree}{\log {\frac {W}{w(x)}}}}$

ya que el tamaño máximo de cualquier nodo individual es W y el mínimo es w(x) .

Por lo tanto, el tiempo real está limitado por:

${\displaystyle O\left(\sum _{x\in sequence}{\left(1+3\log {\frac {W}{w(x)}}\right)}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)=O\left(m+\sum _{x\in sequence}{\log {\frac {W}{w(x)}}}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)}$

Teoremas de rendimiento

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

Teorema de equilibrio  :  el costo de realizar la secuencia S es . ${\displaystyle O\left[m\log n+n\log n\right]}$

Prueba

Tome un peso constante, por ejemplo, ⁠ ⁠ ${\displaystyle w(x)=1}$ para cada nodo x . Entonces ⁠ ⁠ ${\displaystyle W=n}$ .

Este teorema implica que los árboles de búsqueda binaria estática balanceada funcionan tan bien como los árboles de búsqueda binaria estática balanceada en secuencias de al menos n accesos. ^[1]

Teorema de optimalidad estática  :  sea el número de veces que se accede al elemento x en S. Si se accede a cada elemento al menos una vez, entonces el costo de realizar S es ${\displaystyle q_{x}}$ ${\displaystyle O\left[m+\sum _{x\in tree}q_{x}\log {\frac {m}{q_{x}}}\right]}$

Prueba

Sea . Entonces . ${\displaystyle w(x)=q_{x}}$ ${\displaystyle W=m}$

Este teorema implica que los árboles de búsqueda binaria estática funcionan tan bien como un árbol de búsqueda binaria estático óptimo en secuencias de al menos n accesos. ^[7] Pasan menos tiempo en los elementos más frecuentes. ^[1] Otra forma de expresar el mismo resultado es que, en secuencias de entrada donde los elementos se extraen de forma independiente al azar de una distribución de probabilidad no uniforme en n elementos, el costo esperado amortizado ( caso promedio ) de cada acceso es proporcional a la entropía de la distribución. ^[8]

Teorema del dedo estático  :  supongamos que los elementos están numerados del 1 al n en orden ascendente. Sea f cualquier elemento fijo (el "dedo"). Entonces, el costo de realizar S es . ${\displaystyle O\left[m+n\log n+\sum _{x\in sequence}\log(|x-f|+1)\right]}$

Prueba

Sea . Entonces ⁠ ⁠ . La caída de potencial neta es O ( n log n ) ya que el peso de cualquier elemento es al menos ⁠ ⁠ . ^[1] ${\displaystyle w(x)=1/(|x-f|+1)^{2}}$ ${\displaystyle W=O(1)}$ ${\displaystyle 1/n^{2}}$

Teorema del dedo dinámico  :  supongamos que el 'dedo' para cada paso que accede a un elemento y es el elemento al que se accedió en el paso anterior, x . El costo de realizar S es . ^{[9] [10]} ${\displaystyle O\left[m+n+\sum _{x,y\in sequence}^{m}\log(|y-x|+1)\right]}$

Teorema del conjunto de trabajo  :  en cualquier momento durante la secuencia, sea el número de elementos distintos a los que se accedió antes del momento anterior en que se accedió al elemento x. El costo de realizar S es ${\displaystyle t(x)}$ ${\displaystyle O\left[m+n\log n+\sum _{x\in sequence}\log(t(x)+1)\right]}$

Prueba

Sea . Nótese que aquí los pesos cambian durante la secuencia. Sin embargo, la secuencia de pesos sigue siendo una permutación de ⁠ ⁠ . Entonces, como antes ⁠ ⁠ . La caída de potencial neta es O ( n log n ). ${\displaystyle w(x)=1/(t(x)+1)^{2}}$ ${\displaystyle 1,{\tfrac {1}{4}},{\tfrac {1}{9}},\cdots ,{\tfrac {1}{n^{2}}}}$ ${\displaystyle W=O(1)}$

Este teorema es equivalente a árboles splay que tienen optimalidad independiente de la clave . ^[1]

Teorema de escaneo  :  también conocido como teorema de acceso secuencial o teorema de cola . Acceder a los n elementos de un árbol de distribución en orden simétrico requiere un tiempo O ( n ), independientemente de la estructura inicial del árbol de distribución. ^[11] El límite superior más estricto demostrado hasta ahora es . ^[12] ${\displaystyle 4.5n}$

Conjetura de optimalidad dinámica

Problema sin resolver en informática :

¿Los árboles de búsqueda binaria funcionan tan bien como cualquier otro algoritmo de árbol de búsqueda binario?

(más problemas sin resolver en informática)

Además de las garantías de rendimiento comprobadas para los árboles de búsqueda binaria, existe una conjetura no comprobada de gran interés en el 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 de búsqueda binaria funcionan tan bien como cualquier otro algoritmo de árbol de búsqueda binaria hasta un factor constante.

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

Hay varios corolarios de la conjetura de optimalidad dinámica que siguen sin demostrarse:

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

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

Conjetura de división: ^[6] Sea cualquier permutación de los elementos del árbol de distribución. Entonces, el costo de eliminar los elementos en el orden es . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle O(n)}$

Variantes

Para reducir el número de operaciones de reestructuración, es posible reemplazar el ensanchamiento por un semiensanchamiento , en el que un elemento se ensancha solo hasta la mitad hacia la raíz. ^{[1] [2]}

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

El CBTree aumenta el árbol de distribución 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 mano a mano para crear un árbol autoajustable concurrente. ^[15]

Utilizando técnicas de compresión de punteros, ^[16] es posible construir un árbol de distribución sucinto .

Véase también

• Árbol AVL
• Árbol B
• Árbol de dedos
• Geometría de árboles binarios de búsqueda
• Estructura del conjunto de trabajo de Iacono
• Enlace/corte de árbol
• Lista de estructuras de datos
• Árbol del chivo expiatorio
• Splaysort , un algoritmo de ordenación que utiliza árboles splay
• árbol T
• Tratar
• Rotación de árboles
• Árboles
• Cremallera (estructura de datos)

Notas

1. Sleator y Tarjan 1985.
2. Brinkmann, Degraer y De Loof 2009.
3. Goodrich, Tamassia y Goldwasser 2014.
4. Albers y Karpinski 2002.
5. Allen y Munro 1978.
6. Lucas 1991.
7. Knuth 1997, pág. 478
8. Grinberg y otros (1995).
9. Cole y otros. 2000.
10. Cole 2000.
11. Tarjan 1985.
12. Elmasry 2004.
13. Petite 2008.
14. Sundar 1992.
15. Afek y otros, 2014
16. Bender y otros. 2023.

Referencias

• Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E. (2014). "El árbol CB: un árbol de búsqueda concurrente autoajustable práctico". Computación distribuida . 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.
• Allen, Brian; Munro, Ian (octubre de 1978). "Árboles binarios de búsqueda autoorganizados". Revista de la 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 amado: semi-splaying" (PDF) . Software: Práctica y Experiencia . 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 en las que 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 desconocida y mucho menos estudiada 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 log n-bloque". Revista SIAM de Computación . 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". Revista SIAM de informática . 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 de Deque para árboles splay". Ciencias de la computación teórica . 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 de distribución 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 de acceso promedio en un árbol de distribución 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 en cualquier serie de operaciones.
• Lucas, Joan M. (1991). "Sobre la competitividad de los árboles de dispersión: relaciones con el problema de búsqueda de unión". Algoritmos en línea: actas de un taller de DIMACS, 11-13 de febrero de 1991. Series en Matemáticas discretas y Ciencias de la computación teórica. Vol. 7. Centro de Matemáticas discretas y Ciencias de la computación teórica . págs. 95-124. ISBN 0-8218-7111-0.
• Pettie, Seth (2008). Árboles splay, secuencias Davenport-Schinzel y la conjetura Deque (PDF) . Proc. 19.° Simposio ACM-SIAM sobre algoritmos discretos . Vol. 0707. págs. 1115–1124. arXiv : 0707.2160 . Código Bibliográfico :2007arXiv0707.2160P.
• Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Árboles de búsqueda binaria autoajustables" (PDF) . Revista de la 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 de 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) : 477–508. doi :10.1137/1.9781611977554.ch21. ISBN 978-1-61197-755-4.S2CID244709005  .​

Enlaces externos

• Diccionario de algoritmos y estructuras de datos del NIST: árbol de distribución
• Implementaciones en C y Java (por Daniel Sleator)
• Indicadores para visualizar árboles de expansión
• Implementación rápida y eficiente de árboles Splay
• Implementación de Java de árbol de distribución descendente
• Árboles con cremallera