árbol de expansión

Árbol de búsqueda binaria autoajustable

Un árbol de distribución es un árbol de búsqueda binario con la propiedad adicional de que los elementos a los que se accedió recientemente son de acceso rápido nuevamente. Al igual que los árboles de búsqueda binarios autoequilibrados , un árbol splay realiza operaciones básicas como inserción, búsqueda y eliminación en tiempo amortizado O (log n ) . Para patrones de acceso aleatorio extraídos de una distribución aleatoria no uniforme, su tiempo de amortización puede ser más rápido que el logarítmico, proporcional a la entropía del patrón de acceso. Además, para muchos patrones de operaciones no aleatorias, los árboles de dispersión pueden tardar más que el tiempo logarítmico, sin requerir un conocimiento previo del patrón. Según la conjetura de optimización dinámica no probada, su desempeño en todos los patrones de acceso está dentro de un factor constante del mejor desempeño posible que podría lograr cualquier otro árbol de búsqueda binario 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 binario se combinan con una operación básica, llamada extensión . Al desplegar el árbol para un determinado elemento, se 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 de árbol binario estándar para el elemento en cuestión y luego usar rotaciones de árbol de una manera específica para llevar el elemento a la cima. 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 splay depende del hecho de que se optimiza automáticamente, 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 ), siendo el promedio O(log n ). Tener nodos de uso frecuente cerca de la raíz es una ventaja para muchas aplicaciones prácticas (consulte también 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 extendidos es que la altura de un árbol extendido puede ser lineal. ^{[2] : 1} Por ejemplo, este será el caso después de acceder a los n elementos en orden no decreciente. Dado que la altura de un á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 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 ) mediante el uso de una variante aleatoria. ^[4]

La representación de los árboles de distribución puede cambiar incluso cuando se accede a ellos en forma de "sólo lectura" (es decir, mediante operaciones de búsqueda ). Esto complica el uso de dichos árboles extendidos en un entorno de subprocesos múltiples. Específicamente, se necesita administración adicional si se permite que varios subprocesos realicen operaciones de búsqueda al mismo tiempo. Esto también los hace inadecuados para uso general en programación puramente funcional, aunque incluso allí pueden usarse de manera limitada para implementar colas de prioridad.

Finalmente, cuando el patrón de acceso es aleatorio, los gastos generales adicionales añaden un factor constante significativo al costo en comparación con alternativas menos dinámicas.

Operaciones

esparciendo

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

Cada paso en 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 ).

Hay tres tipos de pasos abiertos, cada uno de los cuales tiene dos variantes simétricas: para zurdos y para diestros. En aras de la brevedad, sólo se muestra uno de estos dos para cada tipo. (En los siguientes diagramas, 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 de zig: este paso se realiza cuando p es la raíz. El árbol se gira en el borde entre x y p . Los pasos en zig existen para solucionar el problema de la paridad, se realizarán solo como último paso en una operación de expansió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 hijos restantes. El árbol se gira en el borde que une p con su padre g , luego se gira en el borde que une x con p . Los pasos en zig-zig son lo único que diferencia los árboles extendidos del método de rotación hasta raíz introducido por Allen y Munro ^[5] antes de la introducción de los árboles extendidos.

Paso en zig-zag: 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 la izquierda, p es la derecha). El árbol se gira en el borde entre p y x y luego se gira 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 a un solo árbol:

• Muestra 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 nuevos árboles: uno que contiene todos los elementos menores o iguales a x y el otro que contiene todos los elementos mayores que x . Esto se puede hacer de la siguiente manera:

• Extender 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 .
• Divide el subárbol derecho del resto del árbol.

Inserción

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

• Inserte x como con un árbol de búsqueda binario normal .
• Realice un splay 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.
• Cree un nuevo árbol en el que x sea la raíz, S sea 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 forma, el borrado se reduce al problema de eliminar un nodo con 0 o 1 hijos. A diferencia de un árbol de búsqueda binario, en un árbol extendido después de la eliminación, colocamos el padre del nodo eliminado en la parte superior del árbol.

Alternativamente:

• El nodo que se va a eliminar primero se expande, 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 recorrido por el camino de acceso en lugar de realizar una segunda pasada. Esta rutina de distribución de arriba hacia abajo 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 del medio consta del subárbol con raíz en el nodo actual. Estos tres conjuntos se actualizan a lo largo de la ruta de acceso mientras se mantienen bajo control las operaciones de expansión. Otro método, el semisplaying, modifica el caso en zig-zig para reducir la cantidad de reestructuración realizada en todas las operaciones. ^{[dieciséis ]}

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

#incluir <funcional> #ifndef SPLAY_TREE #define SPLAY_TREEplantilla < nombre de tipo T , nombre de tipo Comp = std :: menos < T >> clase splay_tree { privado : Comp comp ; p_size largo sin firmar ; nodo de estructura { nodo * izquierda , * derecha ; nodo * padre ; tecla T ; 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 ; si ( y -> izquierda ) y -> izquierda -> padre = x ; y -> padre = x -> padre ; } if ( ! x -> padre ) raíz = y ; de lo contrario si ( x == x -> padre -> izquierda ) x -> padre -> izquierda = y ; else x -> padre -> derecha = y ; si ( y ) y -> izquierda = x ; x -> padre = y ; } void right_rotate ( nodo * x ) { nodo * y = x -> izquierda ; if ( y ) { x -> izquierda = y -> derecha ; si ( y -> derecha ) y -> derecha -> padre = x ; y -> padre = x -> padre ; } if ( ! x -> padre ) raíz = y ; de lo contrario si ( x == x -> padre -> izquierda ) x -> padre -> izquierda = y ; más x ->                                                                                            padre -> derecha = y ; si ( y ) y -> derecha = x ; x -> padre = y ; } void splay ( nodo * x ) { while ( x -> padre ) { if ( ! x -> padre -> padre ) { if ( x -> padre -> izquierda == x ) right_rotate ( x -> padre ); de lo contrario left_rotate ( x -> padre ); } else if ( x -> padre -> izquierda == x && x -> padre -> padre -> izquierda == x -> padre ) { right_rotate ( x -> padre -> padre ); rotación_derecha ( x -> padre ); } else if ( x -> padre -> derecha == x && x -> padre -> padre -> derecha == x -> padre ) { left_rotate ( x -> padre -> padre ); left_rotate ( x -> padre ); } else if ( x -> padre -> izquierda == x && x -> padre -> padre -> derecha == x -> padre ) { right_rotate ( x -> padre ); left_rotate ( x -> padre ); } demás {                                                                        left_rotate ( x -> padre ); rotación_derecha ( x -> padre ); } } } void reemplazar ( nodo * u , nodo * v ) { if ( ! u -> padre ) raíz = v ; de lo contrario si ( u == u -> padre -> izquierda ) u -> padre -> izquierda = v ; de lo contrario u -> padre -> derecha = v ; si ( v ) v -> padre = u -> padre ; } nodo * subárbol_mínimo ( nodo * u ) { mientras ( u -> izquierda ) u = u -> izquierda ; devolverte ;​ } nodo * subárbol_máximo ( nodo * u ) { mientras ( u -> derecha ) u = u -> derecha ; devolverte ;​ } público : splay_tree () : raíz ( nullptr ), p_size ( 0 ) { } inserción vacía ( const T & clave ) { nodo * z = raíz ; nodo * p = nullptr ; mientras ( z ) { p = z ; if ( comp ( z -> clave , clave )) 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 ; extender ( z ); p_tamaño ++ ; } nodo * buscar ( const T & clave ) { nodo * z = raíz ; mientras ( z ) { if ( comp ( z -> clave , clave )) z = z -> derecha ; de lo contrario si ( comp ( tecla , z -> tecla )) z = z -> izquierda ; de lo contrario , devuelve z ; } devolver nuloptr ; } borrado vacío ( const T & clave ) { nodo * z = buscar ( clave ); si ( ! z ) regresa ; extender ( z ); si ( ! z -> izquierda ) reemplace ( z , z -> derecha ); de lo contrario , si ( ! z -> derecha ) reemplace ( 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 ; tamaño_p -- ; }                          /* //la implementación alternativa  void erase(const T &key) {  node *z = find(key);  si (!z) regresa;  reproducir(z);  nodo *s = z->izquierda;  nodo *t = z->derecha;  eliminar z;  nodo *sMax = NULL;  si (s) {  s->padre = NULL;  sMax = subárbol_máximo(s);  desplegar(sMax);  raíz = sMax;  }  si (t) {  si (s)  sMax->derecha = t;  de lo contrario  raíz = t;  t->padre = sMax;  }  p_size--;  } */ const T & mínimo () { return subtree_minimum ( raíz ) -> clave ; } const T & máximo () { return subtree_maximum ( raíz ) -> clave ; } bool vacío () const { return raíz == nullptr ; } tamaño largo sin firmar () const { return p_size ; } };                                     #endif // SPLAY_TREE

Análisis

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 enraizado 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 alta en árboles mal equilibrados y baja en árboles bien equilibrados.

Para aplicar el método del potencial , primero calculamos ΔΦ: el cambio en el potencial causado por una operación de separación. Comprobamos cada caso por separado. Denota 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 arriba).

Paso en zigzag

Paso en zig-zig

Paso en zigzag

El coste amortizado de cualquier operación es ΔΦ más el coste real. El coste real de cualquier operación en zig-zig o zig-zag es 2 ya que hay dos rotaciones que realizar. Por eso:

Cuando se suma toda la operación de dispersión, esto se reduce a 1 + 3(rango(raíz)−rango( x )) que es O(log n ), ya que usamos la operación Zig como máximo una vez y el costo amortizado de zig es de más 1+3(rango'( x )−rango( 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 ) al 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 última desigualdad proviene del 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 la hora 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.

• Asigne a cada nodo r un peso w ( r ).
• Defina tamaño ( r ) = la suma de los pesos de los nodos en el subárbol enraizado en el nodo r (incluido r ).
• Defina rango ( r ) y Φ exactamente como se indicó anteriormente.

Se aplica el mismo análisis y el costo amortizado de una operación de esparcimiento 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 es W y el mínimo es w(x) .

Por 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 sobre el peor tiempo de ejecución para realizar una secuencia S de m accesos en un árbol splay que contiene n elementos.

Teorema del 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, para cada nodo x . Entonces . ${\displaystyle w(x)=1}$ ${\displaystyle W=n}$

Este teorema implica que los árboles splay funcionan tan bien como los árboles de búsqueda binarios equilibrados estáticos en secuencias de al menos n accesos. ^[1]

Teorema de optimización 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

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

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

Teorema del dedo estático  :  suponga 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

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

Teorema dinámico del dedo  :  suponga que el 'dedo' de 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 de que se accediera al elemento x anterior. 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

Dejar . Tenga en cuenta que aquí los pesos cambian durante la secuencia. Sin embargo, la secuencia de pesos sigue siendo una permutación de . Así 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 que los árboles splay tengan optimidad independiente de la clave . ^[1]

Teorema de exploración  :  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 lleva O ( n ) tiempo, 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 optimización dinámica

Problema no resuelto en informática :

¿Los árboles de distribución 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 esparcidos, existe una conjetura no comprobada de gran interés procedente del artículo original de Sleator y Tarjan. Esta conjetura se conoce como conjetura de optimización dinámica y básicamente afirma que los árboles splay funcionan tan bien como cualquier otro algoritmo de árbol de búsqueda binario hasta un factor constante.

Conjetura de Optimidad Dinámica: ^[1] Sea cualquier algoritmo de árbol de búsqueda binario que acceda a un elemento recorriendo el camino 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 de que un árbol 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 la optimización dinámica que aún no se han demostrado:

Conjetura transversal: ^[1] Sean y dos árboles extendidos que contengan los mismos elementos. Sea la secuencia obtenida visitando los elementos en preorden (es decir, primer orden de búsqueda en profundidad). El coste total de realizar la secuencia de accesos 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 (empujar, hacer estallar, inyectar, expulsar). Entonces el costo de actuar en un árbol extendido es . ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle O(m+n)}$

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

Variantes

Para reducir el número de operaciones de reestructuración, es posible sustituir el ensanchamiento por un semiensanchamiento , en el que un elemento se ensancha sólo hasta la mitad de 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]

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

Ver también

• árbol AVL
• árbol B
• árbol de dedos
• Geometría de árboles de búsqueda binarios.
• Estructura del conjunto de trabajo de Iacono
• Enlace/cortar árbol
• Lista de estructuras de datos
• árbol chivo expiatorio
• Splaysort , un algoritmo de clasificación que utiliza árboles de distribución
• árbol en T
• Tragar
• 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 col. (1995).
9. Cole y col. 2000.
10. Cole 2000.
11. Tarjan 1985.
12. Elmasry 2004.
13. Pettie 2008.
14. Domingo 1992.
15. Bender y col. 2023.

Referencias

• Albers, Susana; Karpinski, Marek (28 de febrero de 2002). "Árboles de distribución aleatorios: resultados teóricos y experimentales" (PDF) . Cartas de procesamiento de información . 81 (4): 213–221. doi :10.1016/s0020-0190(01)00230-7.
• Allen, Brian; Munro, Ian (octubre de 1978). "Árboles de búsqueda binarios autoorganizados". Revista de la ACM . 25 (4): 526–535. doi : 10.1145/322092.322094 . S2CID  15967344.
• Brinkmann, Gunnar; Degraer, enero; De Loof, Karel (enero de 2009). «Rehabilitación de un niño no amado: semi-juego» (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-ensanchamiento, que se introdujo en el mismo artículo que el ensanchamiento, funciona mejor que el ensanchamiento en casi todas las condiciones posibles. Esto hace que el semi-ensanchamiento sea una buena alternativa para todas las aplicaciones en las que normalmente se aplicaría el ensanchamiento. La razón por la cual 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, brote; Schmidt, Jeanette; Siegel, Alan (enero de 2000). "Sobre la conjetura dinámica del dedo para árboles de visualización. Parte I: Secuencias de n bloques de registro de clasificación de visualización". 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 dinámica de los dedos para los árboles extendidos. Parte II: la prueba". Revista SIAM de Computación . 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 extendidos". Informática Teórica . 314 (3): 459–466. doi : 10.1016/j.tcs.2004.01.019.
• Goodrich, Michael; Tamasia, Roberto; Goldwasser, Michael (2014). Estructuras de datos y algoritmos en Java (6 ed.). Wiley. pag. 506.ISBN​ 978-1-118-77133-4.
• Grinberg, Dennis; Rajagopalan, Sivaramakrishnan; Venkatesan, Ramarathnam; Wei, Víctor K. (1995). "Distribuir árboles para la compresión de datos". En Clarkson, Kenneth L. (ed.). Actas del sexto simposio anual ACM-SIAM sobre algoritmos discretos, 22 a 24 de enero de 1995. San Francisco, California, EE. UU . ACM/SIAM. págs. 522–530. La profundidad promedio 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: Clasificación y búsqueda (3ª ed.). Addison-Wesley. pag. 478.ISBN​ 0-201-89685-0. Se sabe que el tiempo necesario para acceder a los datos en un árbol de distribución 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 esparcidos: relaciones con el problema de búsqueda de sindicatos". Algoritmos en línea: actas de un taller DIMACS, 11 al 13 de febrero de 1991 . Serie de Matemática Discreta e Informática Teórica. vol. 7. Centro de Matemática Discreta e Informática Teórica . págs. 95-124. ISBN 0-8218-7111-0.
• Pettie, Seth (2008). Árboles distribuidos, secuencias de Davenport-Schinzel y la conjetura de Deque (PDF) . Proc. XIX Simposio ACM-SIAM sobre Algoritmos Discretos . vol. 0707, págs. 1115-1124. arXiv : 0707.2160 . Código Bib : 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 de Deque para el algoritmo de dispersión". Combinatoria . 12 (1): 95-124. doi :10.1007/BF01191208. S2CID  27422556.
• Tarjan, Robert E. (1985). "El acceso secuencial en árboles extendidos requiere un tiempo lineal". Combinatoria . 5 (4): 367–378. doi :10.1007/BF02579253. S2CID  34757821.
• Bender, Michael A.; Conway, Alex; Farach-Colton, Martín; Kuszmaul, William; Tagliavini, Guido (2023). "Pequeños consejos". 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. S2CID  244709005.

enlaces externos

• Diccionario de algoritmos y estructuras de datos del NIST: árbol de distribución
• Implementaciones en C y Java (por Daniel Sleator)
• Consejos para desplegar visualizaciones de árbol
• Implementación rápida y eficiente de árboles Splay
• Implementación de Java de árbol de visualización de arriba hacia abajo
• Árboles de cremallera