miniatura|centro|350px|alt=Paso zig nunha árbore splay.|Paso zig nunha árbore splay.
Unha árbore splay é unha árbore binaria de busca coa propiedade adicional de que os elementos accedidos recentemente se poden volver acceder con rapidez. Como as árbores binarias de busca auto-equilibradas, unha árbore splay realiza as operacións básicas —inserción, busca e borrado— en tempo amortizado . Para patróns de acceso non uniformes, a cota amortizada pode mellorar segundo a entropía das frecuencias de acceso, mantendo un custo constante adicional por operación. Para moitos patróns de operacións non aleatorias tamén pode ser mellor ca o logarítmico, sen necesidade de coñecer o patrón de antemán. Segundo a non demostrada conxectura de optimalidade dinámica, o seu rendemento en todos os patróns de acceso está dentro dun factor constante do mellor posible acadable por calquera outra árbore binaria de busca auto-axustable. A árbore splay foi inventada por Daniel Sleator e Robert Tarjan en 1985.
Todas as operacións normais dunha árbore binaria de busca combínanse cunha operación básica chamada splay. Facer splay da árbore para un elemento reordénaa de xeito que o elemento queda na raíz. Un xeito de facelo é realizar primeiro unha busca binaria estándar e despois usar rotacións dunha forma específica para levar o elemento á cima. Alternativamente, un algoritmo descendente pode combinar a busca e a reorganización nunha soa fase.
Vantaxes O bo rendemento dunha árbore splay débese á súa adaptación aos accesos: os nós usados con frecuencia tenden a achegarse á raíz. A garantía de é amortizada sobre unha secuencia de operacións; non é unha garantía de altura logarítmica nin depende de que as entradas sexan aleatorias. Por exemplo, os accesos en orde poden deixar unha árbore de altura linear. A adaptación á localidade de referencia resulta útil en aplicacións como as cachés. Rendemento comparable: o rendemento medio é tan eficiente como o doutras árbores. Pegada de memoria pequena: as árbores splay non necesitan almacenar datos de control.
Inconvenientes O inconveniente máis importante é que a altura dunha árbore splay pode ser linear. Isto sucede, por exemplo, tras acceder aos elementos en orde non decrecente. Como a altura corresponde ao tempo de acceso no peor caso, o custo real dunha soa operación pode ser alto; con todo, o custo amortizado dese peor caso é logarítmico, . Ademais, o custo esperado pódese reducir a cunha variante aleatorizada.
A representación das árbores splay pode cambiar mesmo cando se acceden en modo «só lectura» (é dicir, con operacións de busca). Isto complica o seu uso nun contorno con múltiples fíos de execución. Tamén as fai pouco axeitadas para o uso xeral en programación funcional pura, aínda que aí se poden usar de forma limitada para implementar colas de prioridade.
Por último, cando o patrón de acceso é aleatorio, o custo adicional do splay engade un factor constante significativo fronte a alternativas menos dinámicas.
Operacións Splay Cando se accede a un nó x, realízase unha operación de splay sobre x para levalo á raíz. Unha operación de splay é unha secuencia de pasos de splay, cada un dos cales achega x á raíz. Repetila tras os accesos permite obter as cotas amortizadas da estrutura, pero non mantén necesariamente a árbore equilibrada en altura.
Cada paso depende de tres factores: se x é fillo esquerdo ou dereito do seu pai p; se p é a raíz ou non; e, se non o é, se p é fillo esquerdo ou dereito do seu pai g (o avó de x).
Hai tres tipos de pasos de splay, cada un con dúas variantes simétricas (esquerda e dereita): Paso zig: faise cando p é a raíz. Rótase a árbore na aresta entre x e p. Os pasos zig tratan a paridade e só se fan como último paso dunha operación de splay. Paso zig-zig: faise cando p non é a raíz e x e p son ambos fillos dereitos ou ambos fillos esquerdos. Rótase primeiro na aresta que une p co seu pai g e logo na aresta que une x con p. Os pasos zig-zig son o único que diferencia as árbores splay do método de «rotar ata a raíz» de Allen e Munro anterior. Paso zig-zag: faise cando p non é a raíz e x é fillo dereito e p é fillo esquerdo, ou viceversa. Rótase na aresta entre p e x e despois na aresta resultante entre x e g.
Join Dadas dúas árbores S e T tales que todos os elementos de S son menores que os de T, pódense unir nunha soa árbore así: Se unha das árbores está baleira, devolver a outra. Se non, facer splay do maior elemento de S; agora está na raíz de S e ten fillo dereito nulo. Facer que o fillo dereito da nova raíz sexa T.
Split Dada unha árbore e un elemento x, devolver dúas árbores: unha con todos os elementos menores ou iguais a x e outra cos maiores que x. Pódese facer así: Se a árbore está baleira, devolver dúas árbores baleiras. Buscar x e facer splay do nó atopado ou, se non existe, do último nó visitado. Se a chave da raíz é menor ou igual a x, separar a subárbore dereita: o resto contén os elementos menores ou iguais e a subárbore separada, os maiores. Se a chave da raíz é maior ca x, separar a subárbore esquerda: esta contén os menores ou iguais e o resto, os maiores.
Inserción Para inserir un valor x nunha árbore splay: Inserir x como nunha árbore binaria de busca normal. Facer splay de x. Como resultado, o nó inserido queda como raíz. Alternativamente, pódese usar a operación split e crear unha nova árbore con x na raíz.
Borrado Para borrar un nó x úsase o mesmo método ca nunha árbore binaria de busca: se ten dous fillos, intercámbiase o valor co do predecesor ou sucesor en orde e bórrase ese. A diferenza dunha árbore binaria de busca, tras o borrado faise splay do pai do nó eliminado ata a raíz. Alternativamente, faise splay do nó que se vai borrar, bórrase e únense as dúas subárbores resultantes cunha operación join.
Implementación e variantes O splay realízase, como se dixo, nunha segunda pasada ascendente sobre o camiño de acceso. Pódese rexistrar o camiño na primeira pasada, o que require espazo adicional, ou ben gardar un punteiro ao pai en cada nó, o que evita o espazo extra pero pode reducir a eficiencia global polas actualizacións deses punteiros.
Outro método reestrutura a árbore durante o descenso, sen unha segunda pasada. Esta rutina de splay descendente usa tres conxuntos de nós (árbore esquerda, dereita e central). Outro método, o semisplaying, modifica o caso zig-zig para reducir a reestruturación.
A continuación móstrase a esencia da operación splay, con rotacións simples: void splay(node *x) { while (x->parent) { if (!x->parent->parent) { if (x->parent->left == x) right_rotate(x->parent); else left_rotate(x->parent); } else if (x->parent->left == x && x->parent->parent->left == x->parent) { right_rotate(x->parent->parent); right_rotate(x->parent); } else if (x->parent->right == x && x->parent->parent->right == x->parent) { left_rotate(x->parent->parent); left_rotate(x->parent); } else if (x->parent->left == x && x->parent->parent->right == x->parent) { right_rotate(x->parent); left_rotate(x->parent); } else { left_rotate(x->parent); right_rotate(x->parent);
Análise Pódese facer unha análise amortizada sinxela das árbores splay estáticas co método do potencial. Defínense: tamaño(r) = número de nós da subárbore con raíz en r (incluído r). rango(r) = log2(tamaño(r)). Φ = suma dos rangos de todos os nós da árbore.
Φ tende a ser alto para árbores mal equilibradas e baixo para árbores ben equilibradas. Para aplicar o método do potencial, calcúlase ΔΦ, a variación do potencial causada por unha operación de splay, en cada caso:
Paso zig: ΔΦ ≤ rango'(x) − rango(x). Paso zig-zig: ΔΦ ≤ 3(rango'(x) − rango(x)) − 2. Paso zig-zag: ΔΦ ≤ 3(rango'(x) − rango(x)) − 2.
O custo amortizado de calquera operación é ΔΦ máis o custo real. Como o custo real dun zig-zig ou zig-zag é 2, tense que o custo amortizado é como máximo . Sumando ao longo de toda a operación, telescopa a , que é .
Así, o tempo total amortizado dunha secuencia de operacións é . Para pasar ao tempo real hai que engadir a diminución de potencial entre o estado inicial e o final, que é , de onde .
Análise ponderada A análise anterior pódese xeneralizar asignando a cada nó r un peso w(r), definindo tamaño(r) como a suma dos pesos dos nós da subárbore con raíz en r e o rango igual que antes. A mesma análise é válida e o custo amortizado dunha operación de splay é outra vez . A diminución de potencial entre o inicio e o final está acoutada por , onde é a suma de todos os pesos.
Teoremas de rendemento Hai varios teoremas e conxecturas sobre o tempo no peor caso de executar unha secuencia de accesos nunha árbore splay con elementos.
Teorema do equilibrio: o custo de realizar é . Isto implica que as árbores splay se comportan tan ben como as árbores binarias de busca equilibradas estáticas en secuencias de polo menos accesos. Teorema da optimalidade estática: se é o número de veces que se accede a en e cada elemento se accede polo menos unha vez, o custo de é . Dividindo entre , a cota media por acceso é , onde é a entropía das frecuencias de acceso. O termo constante mantense mesmo cando a entropía é cero. Teorema do dedo estático: numerando os elementos de 1 a en orde ascendente e sendo un elemento fixo (o «dedo»), o custo de é . Teorema do dedo dinámico: se o «dedo» de cada paso é o elemento accedido no paso anterior, o custo é . Teorema do conxunto de traballo: para cada acceso a , sexa o número de elementos distintos accedidos desde o acceso anterior a , ou se é o primeiro. O custo é . Relaciónase coa optimalidade independente da chave. Teorema do escaneo: tamén chamado teorema do acceso secuencial ou teorema da cola. Acceder aos elementos dunha árbore splay en orde simétrica leva tempo , independentemente da estrutura inicial.
Conxectura da optimalidade dinámica Ademais das garantías de rendemento demostradas, existe unha conxectura sen demostrar de grande interese, procedente do artigo orixinal de Sleator e Tarjan: a conxectura da optimalidade dinámica, que afirma que as árbores splay se comportan tan ben como calquera outro algoritmo de árbore binaria de busca, agás un factor constante.
Entre os corolarios desta conxectura, aínda sen demostrar, están a conxectura do percorrido, a conxectura da cola de dobre extremo e a conxectura de split.
Variantes Para reducir o número de operacións de reestruturación, pódese substituír o splay por semisplaying, no que un elemento só se fai splay ata a metade do camiño cara á raíz.
Outra forma de reducir a reestruturación é facer o splay completo só nalgunhas operacións (cando o camiño de acceso é máis longo ca un limiar, ou só nas primeiras operacións).
A CBTree aumenta a árbore splay con contadores de acceso en cada nó e úsea para reestruturar con pouca frecuencia. Unha variante chamada LazyCBTree fai como máximo unha rotación por busca. Usando técnicas de compresión de punteiros pódese construír unha árbore splay sucinta.
Notas
Véxase tamén Bibliografía Sleator, Daniel D.; Tarjan, Robert E. «Self-Adjusting Binary Search Trees», Journal of the ACM, 32(3):652–686, 1985, . Allen, Brian; Munro, Ian. «Self-organizing binary search trees», Journal of the ACM, 25(4):526–535, 1978, . Donald Knuth. The Art of Computer Programming, volume 3: Sorting and Searching, segunda edición, Addison-Wesley, 1998, páxina 478. ISBN 0-201-89685-0. Sundar, Rajamani. «On the Deque conjecture for the splay algorithm», Combinatorica, 12(1):95–124, 1992, . Grinberg, Dennis et al. «Splay trees for data compression», Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, páxinas 522–530, 1995.
Outros artigos Árbore AVL Árbore rubinegra Árbore binaria de busca Árbore-B Rotación de árbore Treap
Ligazóns externas Árbore splay no Dictionary of Algorithms and Data Structures do NIST Implementacións en C e Java, de Daniel Sleator Implementación rápida e eficiente de árbores splay