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..
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. 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. .
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) centro| Rotações ZIG e ZAGminiaturadaimagem|358x358px 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: centro|miniaturadaimagem|378x378px 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: centro 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: centro 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 struct node *splay(struct node *root, int key) { // Base cases: root is NULL or key is present at root if (root == NULL || root→key == key) return root;
// Key lies in left subtree if (root→key > key)
// Key is not in tree, we are done if (root→left == NULL) return root;
// Zig-Zig (Left Left) if (root→left→key > key)
// First recursively bring the key as root of left-left root→left→left = splay(root→left→left, key);
// Do first rotation for root, second rotation is done after else root = rightRotate(root);
else if (root→left→key < key) // Zig-Zag (Left Right)
// First recursively bring the key as root of left-right root→left→right = splay(root→left→right, key);
// Do first rotation for root→left if (root→left→right != NULL) root→left = leftRotate(root→left);
// Do second rotation for root return (root→left == NULL)? root: rightRotate(root);
else // Key lies in right subtree
// Key is not in tree, we are done if (root→right == NULL) return root;
// Zag-Zig (Right Left) if (root→right→key > key)
// Bring the key as root of right-left root→right→left = splay(root→right→left, key);
// Do first rotation for root→right if (root→right→left != NULL) root→right = rightRotate(root→right);
else if (root→right→key < key)// Zag-Zag (Right Right)
// Bring the key as root of right-right and do first rotation root→right→right = splay(root→right→right, key); root = leftRotate(root);
// Do second rotation for root return (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. struct node *search(struct node *root, int key) { return splay(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.
struct node *insert(struct node *root, int k) { // Simple Case: If tree is empty if (root == NULL) return newNode(k);
// Bring the closest leaf node to root root = splay(root, k);
// If key is already present, then return if (root→key == k) return root;
// Otherwise allocate memory for new node struct node *newnode = newNode(k);
// If root's key is greater, make root as right child // of newnode and copy the left child of root to newnode if (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 newnode else
newnode→left = root; newnode→right = root→right; root→right = NULL;
return newnode; // newnode becomes new root }
Bibliografia
Categoria:Árvores (teoria dos grafos) Categoria:Estruturas de dados