|
Árvore splay
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] VantagensO 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:
DesvantagensA 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çõesSplayQuando 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)
 Se pai(B) é raiz fazemos apenas uma rotação para esquerda ou direita. Rotação dupla (ZIG-ZIG, 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
 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
 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. BuscaComo 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çãoA 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
Referências |
||||||||||||||||||||||||||||||||||
Portal di Ensiklopedia Dunia
