Uma árvore splay é uma árvore binária de busca autoajustável, com a propriedade adicional de tornar os elementos recentemente acessados, fáceis de acesso novamente, pois os mantém em sua raiz. Suas operações básicas, como remoção e inserção, são executadas em O(log n). Todas as suas operações colocam o elemento envolvido na operação na raiz, através de rotações. Para muitas sequências de operações não aleatórias, as árvores splay têm melhor desempenho do que outras árvores de busca, mesmo quando o padrão específico da sequência é desconhecido. A árvore splay foi inventada por Daniel Sleator e Robert Tarjan em 1985.[1]
Vantagens
O bom desempenho para uma árvore de splay depende do fato de que é autoajustável, na medida em que os nós com acesso frequente se moverão mais próximos da raiz onde eles podem ser acessados mais rapidamente. A altura do pior caso - embora improvável - é O (n), sendo a média O (log n ).
As vantagens incluem:
Desempenho comparável: O desempenho médio do caso é tão eficiente quanto outras árvores.[2]
Fácil de implementar;
Desvantagens
A desvantagem mais significativa é que a altura de uma árvore splay pode ser linear. Por exemplo, este será o caso depois de acessar todos os elementos n em ordem não decrescente. Uma vez que a altura de uma árvore corresponde ao pior caso de tempo de acesso, isso significa que o custo real de uma operação pode ser alto. No entanto, o custo de acesso deste pior caso é, O (log n ). Além disso, o custo de acesso esperado pode ser reduzido a O (log n ) usando uma variante aleatória.[3]
O pior caso ocorre quando os nodos da árvore são acessados sequencialmente em ordem. Isto deixa a árvore completamente desbalanceada.
A representação de árvores de splay pode mudar mesmo quando elas são acessadas de forma "somente leitura" (isto é, por operações de "pesquisa"). Isto complica o uso de tais em um ambiente multi-threaded. Especificamente, gerenciamento extra é necessário se vários segmentos são autorizados a executar operações de pesquisa simultaneamente. Isso também os torna inadequados para uso geral em programação puramente funcional, embora mesmo lá eles possam ser usados de maneiras limitadas para implementar filas de prioridade.
Operações
Splay
Quando um nó n é acessado, uma operação de splay é executada em n para movê-lo para a raiz. Para executar uma operação de splay, realizamos uma sequência de rotações, cada um dos quais move n mais próximo da raiz. Ao executar uma operação de splay no nó de interesse após cada acesso, os nós recentemente acessados são mantidos perto da raiz e a árvore permanece aproximadamente equilibrada.
Rotação simples (ZIG)
ZIG (Rotação para Direita) e ZAG (Rotação para Esquerda)
Se pai(B) é raiz fazemos apenas uma rotação para esquerda ou direita.
Rotação dupla (ZIG-ZIG, ZAG-ZAG)
ZIG-ZIG e ZAG-ZAG:
Se pai(C) não é raiz e C e pai(C) são filhos do mesmo lado, fazemos duas rotações para direita ou duas rotações para a esquerda, no mesmo sentido começando pelo pai(pai(C)).
Rotação dupla ZIG-ZAG
ZIG-ZAG:
Se pai(C) não é raiz e C e pai(C) são filhos do lado oposto, faz uma rotação em pai(C) para direita e outra rotação no avô para esquerda de C.
Rotação dupla ZAG-ZIG
ZAG-ZIG:
Se pai(C) não é raiz e C e pai(C) são filhos do lado oposto, faz uma rotação em pai(C) para esquerda e outra rotação no avô para direita de C.
Busca
Como a Splay Tree é um algoritmo, que ao passar das operações ela vai se balanceando, inicia na raiz da árvore t procurando pelo item i, se a busca encontra um nodo x que contenha i, o nodo x é splayed.Se a busca não encontra i, último nodo não nulo da árvore é splayed e um ponteiro nulo é retornado
structnode*splay(structnode*root,intkey){// Base cases: root is NULL or key is present at rootif(root==NULL||root→key==key)returnroot;// Key lies in left subtreeif(root→key>key){// Key is not in tree, we are doneif(root→left==NULL)returnroot;// Zig-Zig (Left Left)if(root→left→key>key){// First recursively bring the key as root of left-leftroot→left→left=splay(root→left→left,key);// Do first rotation for root, second rotation is done after elseroot=rightRotate(root);}elseif(root→left→key<key)// Zig-Zag (Left Right){// First recursively bring the key as root of left-rightroot→left→right=splay(root→left→right,key);// Do first rotation for root→leftif(root→left→right!=NULL)root→left=leftRotate(root→left);}// Do second rotation for rootreturn(root→left==NULL)?root:rightRotate(root);}else// Key lies in right subtree{// Key is not in tree, we are doneif(root→right==NULL)returnroot;// Zag-Zig (Right Left)if(root→right→key>key){// Bring the key as root of right-leftroot→right→left=splay(root→right→left,key);// Do first rotation for root→rightif(root→right→left!=NULL)root→right=rightRotate(root→right);}elseif(root→right→key<key)// Zag-Zag (Right Right){// Bring the key as root of right-right and do first rotationroot→right→right=splay(root→right→right,key);root=leftRotate(root);}// Do second rotation for rootreturn(root→right==NULL)?root:leftRotate(root);}}// The search function for Splay tree. Note that this function// returns the new root of Splay Tree. If key is present in tree// then, it is moved to root.structnode*search(structnode*root,intkey){returnsplay(root,key);}
Inserção
A inserção na Splay tree é parecida com a que ocorre nas Árvores Binarias de Pesquisa - BST -, apenas com uma adição que o elemento que foi adicionado se torna a nova raiz.
structnode*insert(structnode*root,intk){// Simple Case: If tree is emptyif(root==NULL)returnnewNode(k);// Bring the closest leaf node to rootroot=splay(root,k);// If key is already present, then returnif(root→key==k)returnroot;// Otherwise allocate memory for new nodestructnode*newnode=newNode(k);// If root's key is greater, make root as right child// of newnode and copy the left child of root to newnodeif(root→key>k){newnode→right=root;newnode→left=root→left;root→left=NULL;}// If root's key is smaller, make root as left child// of newnode and copy the right child of root to newnodeelse{newnode→left=root;newnode→right=root→right;root→right=NULL;}returnnewnode;// newnode becomes new root}
Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (janeiro de 2009). «Rehabilitation of an unloved child: semi-splaying»(PDF). Software—Practice and Experience. 39 (1): 33–45. CiteSeerX10.1.1.84.790. doi:10.1002/spe.v39:1. Consultado em 2 de abril de 2017. Arquivado do original(PDF) em 4 de julho de 2009. The results show that semi-splaying, which was introduced in the same paper as splaying, performs better than splaying under almost all possible conditions. This makes semi-splaying a good alternative for all applications where normally splaying would be applied. The reason why splaying became so prominent while semi-splaying is relatively unknown and much less studied is hard to understand.
Cole, Richard; Mishra, Bud; Schmidt, Jeanette; Siegel, Alan (janeiro de 2000). «On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences». SIAM Journal on Computing. 30 (1): 1–43. doi:10.1137/s0097539797326988
Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014). Data Structures and Algorithms in Java (em inglês) 6 ed. [S.l.]: Wiley. p. 506. ISBN978-1-118-77133-4
Lucas, Joan M. (1991). «On the Competitiveness of Splay Trees: Relations to the Union-Find Problem». On-line Algorithms: Proceedings of a DIMACS Workshop, February 11–13, 1991. Col: Series in Discrete Mathematics and Theoretical Computer Science. 7. [S.l.]: Center for Discrete Mathematics and Theoretical Computer Science. pp. 95–124. ISBN0-8218-7111-0