As árvores Splay são árvores de busca binária com autoequilíbrio ou autoajustadas. Em outras palavras, podemos dizer que as árvores splay são variantes das árvores binárias de busca. O pré-requisito para as árvores splay que devemos saber é sobre as árvores de busca binária.
Como já sabemos, a complexidade temporal de uma árvore de busca binária em todos os casos. A complexidade de tempo de uma árvore de pesquisa binária no caso médio é O(logn) e a complexidade de tempo no pior caso é O(n). Em uma árvore de pesquisa binária, o valor da subárvore esquerda é menor que o nó raiz e o valor da subárvore direita é maior que o nó raiz; nesse caso, a complexidade do tempo seria O(logn) . Se a árvore binária for inclinada para a esquerda ou para a direita, então a complexidade do tempo seria O (n). Para limitar a assimetria, o AVL e árvore rubro-negra entrou em cena, tendo O(logn ) complexidade de tempo para todas as operações em todos os casos. Também podemos melhorar essa complexidade de tempo fazendo implementações mais práticas, então a nova Árvore O que é uma Árvore Splay?
Uma árvore splay é uma árvore com equilíbrio automático, mas As árvores AVL e Red-Black também são árvores com equilíbrio automático. O que torna a árvore splay única são duas árvores. Ele tem uma propriedade extra que o torna único: a expansão.
Uma árvore splay contém as mesmas operações que uma Árvore de pesquisa binária , ou seja, inserção, exclusão e pesquisa, mas também contém mais uma operação, ou seja, expansão. Então. todas as operações na árvore de expansão são seguidas de expansão.
As árvores espalhadas não são árvores estritamente equilibradas, mas são árvores aproximadamente equilibradas. Vamos entender a operação de busca na splay-tree.
Suponha que queiramos pesquisar 7 elementos na árvore, mostrado abaixo:
Para pesquisar qualquer elemento na árvore splay, primeiro realizaremos a operação padrão da árvore de pesquisa binária. Como 7 é menor que 10, iremos para a esquerda do nó raiz. Depois de realizar a operação de pesquisa, precisamos realizar o splaying. Aqui, espalhar significa que a operação que estamos realizando em qualquer elemento deve se tornar o nó raiz após realizar alguns rearranjos. O rearranjo da árvore será feito através das rotações.
Nota: A árvore splay pode ser definida como a árvore autoajustada na qual qualquer operação executada no elemento reorganizaria a árvore de modo que o elemento no qual a operação foi executada se tornasse o nó raiz da árvore.
Rotações
Existem seis tipos de rotações usadas para espalhar:
- Rotação Zig (rotação para a direita)
- Rotação Zag (rotação à esquerda)
- Zig zag (Zig seguido de zag)
- Zag zig (Zag seguido de zig)
- Zig zig (duas rotações à direita)
- Zag zag (duas rotações para a esquerda)
Fatores necessários para selecionar um tipo de rotação
A seguir estão os fatores usados para selecionar um tipo de rotação:
- O nó que estamos tentando girar tem um avô?
- O nó é filho esquerdo ou direito do pai?
- O nó esquerdo ou direito é filho do avô?
Casos para as rotações
Caso 1: Se o nó não tiver avô e for o filho direito do pai, então realizamos a rotação para a esquerda; caso contrário, a rotação direita será executada.
Caso 2: Se o nó tiver um avô, então com base nos seguintes cenários; a rotação seria realizada:
Cenário 1: Se o nó estiver à direita do pai e o pai também estiver à direita de seu pai, então zig zig direita rotação direita é desempenhado.
Cenário 2: Se o nó estiver à esquerda de um pai, mas o pai estiver à direita de seu pai, então ziguezague rotação direita esquerda é desempenhado.
Cenário 3: Se o nó estiver à direita do pai e o pai estiver à direita de seu pai, então zig zig rotação esquerda esquerda é desempenhado.
Cenário 4: Se o nó estiver à direita de um pai, mas o pai estiver à esquerda de seu pai, então rotação ziguezague direita-esquerda é desempenhado.
Agora, vamos entender as rotações acima com exemplos.
Para reorganizar a árvore, precisamos realizar algumas rotações. A seguir estão os tipos de rotações na árvore splay:
As rotações zig são usadas quando o item a ser pesquisado é um nó raiz ou filho de um nó raiz (ou seja, filho esquerdo ou direito).
A seguir estão os casos que podem existir na árvore splay durante a pesquisa:
Caso 1: Se o item de pesquisa for um nó raiz da árvore.
Caso 2: Se o item de pesquisa for filho do nó raiz, então os dois cenários estarão lá:
- Se a criança for esquerda, será realizada a rotação para a direita, conhecida como rotação em zig para a direita.
- Se a criança for direita, será realizada a rotação para a esquerda, conhecida como rotação zig para a esquerda.
Vejamos os dois cenários acima por meio de um exemplo.
Considere o exemplo abaixo:
No exemplo acima, temos que pesquisar 7 elementos na árvore. Seguiremos os passos abaixo:
Passo 1: Primeiro, comparamos 7 com um nó raiz. Como 7 é menor que 10, é filho esquerdo do nó raiz.
Passo 2: Assim que o elemento for encontrado, realizaremos o splaying. A rotação para a direita é realizada de forma que 7 se torne o nó raiz da árvore, conforme mostrado abaixo:
Vamos considerar outro exemplo.
No exemplo acima, temos que pesquisar 20 elementos na árvore. Seguiremos os passos abaixo:
Passo 1: Primeiro, comparamos 20 com um nó raiz. Como 20 é maior que o nó raiz, é filho direito do nó raiz.
Passo 2: Assim que o elemento for encontrado, realizaremos o splaying. A rotação para a esquerda é realizada de forma que o elemento 20 se torne o nó raiz da árvore.
Às vezes surge a situação quando o item a ser pesquisado é ter um dos pais e também um avô. Neste caso, temos que realizar quatro rotações para espalhar.
Vamos entender esse caso através de um exemplo.
Suponha que tenhamos que pesquisar 1 elemento na árvore, mostrado abaixo:
Passo 1: Primeiro, temos que realizar uma operação de pesquisa BST padrão para pesquisar o 1 elemento. Como 1 é menor que 10 e 7, estará à esquerda do nó 7. Portanto, o elemento 1 tem um pai, ou seja, 7, bem como um avô, ou seja, 10.
Passo 2: Nesta etapa, temos que realizar o splaying. Precisamos fazer do nó 1 um nó raiz com a ajuda de algumas rotações. Neste caso, não podemos simplesmente realizar uma rotação em zigue-zague; temos que implementar a rotação zig zig.
Para tornar o nó 1 um nó raiz, precisamos realizar duas rotações à direita conhecidas como rotações zig zig. Quando realizamos a rotação para a direita, o nó 10 se moverá para baixo e o nó 7 subirá, conforme mostrado na figura abaixo:
Novamente, realizaremos rotação zig para a direita, o nó 7 se moverá para baixo e o nó 1 subirá conforme mostrado abaixo:
Como observamos na figura acima, o nó 1 se tornou o nó raiz da árvore; portanto, a pesquisa está concluída.
Suponha que queiramos pesquisar 20 na árvore abaixo.
Para pesquisar 20, precisamos realizar duas rotações para a esquerda. A seguir estão as etapas necessárias para pesquisar o nó 20:
Passo 1: Primeiro, realizamos a operação de pesquisa padrão do BST. Como 20 é maior que 10 e 15, estará à direita do nó 15.
Passo 2: O segundo passo é realizar o splaying. Neste caso, seriam realizadas duas rotações à esquerda. Na primeira rotação, o nó 10 se moverá para baixo e o nó 15 se moverá para cima conforme mostrado abaixo:
Na segunda rotação para a esquerda, o nó 15 se moverá para baixo e o nó 20 se tornará o nó raiz da árvore, conforme mostrado abaixo:
Como observamos que são realizadas duas rotações para a esquerda; por isso é conhecido como rotação à esquerda em zig zig.
Até agora, lemos que tanto os pais quanto os avós estão em um relacionamento RR ou LL. Agora veremos o relacionamento RL ou LR entre os pais e os avós.
Vamos entender esse caso através de um exemplo.
Suponha que queiramos pesquisar 13 elementos na árvore mostrada abaixo:
Passo 1: Primeiro, realizamos a operação de pesquisa padrão do BST. Como 13 é maior que 10, mas menor que 15, o nó 13 será o filho esquerdo do nó 15.
Passo 2: Como o nó 13 está à esquerda do nó 15 e o nó 15 está à direita do nó 10, existe um relacionamento RL. Primeiro, realizamos a rotação para a direita no nó 15, e o 15 se moverá para baixo e o nó 13 subirá, conforme mostrado abaixo:
Ainda assim, o nó 13 não é o nó raiz e o 13 está à direita do nó raiz, portanto realizaremos a rotação para a esquerda conhecida como rotação zag. O nó 10 se moverá para baixo e 13 se tornará o nó raiz conforme mostrado abaixo:
Como podemos observar na árvore acima, o nó 13 se tornou o nó raiz; portanto, a pesquisa está concluída. Neste caso, realizamos primeiro a rotação em zigue-zague e depois a rotação em zag; então, é conhecido como rotação em zigue-zague.
Vamos entender esse caso através de um exemplo.
Suponha que queiramos pesquisar 9 elementos na árvore, mostrado abaixo:
Passo 1: Primeiro, realizamos a operação de pesquisa padrão do BST. Como 9 é menor que 10, mas maior que 7, será o filho certo do nó 7.
Passo 2: Como o nó 9 está à direita do nó 7 e o nó 7 está à esquerda do nó 10, existe o relacionamento LR. Primeiro, realizamos a rotação para a esquerda no nó 7. O nó 7 se moverá para baixo e o nó 9 se moverá para cima, conforme mostrado abaixo:
Ainda assim, o nó 9 não é um nó raiz e 9 está à esquerda do nó raiz, portanto realizaremos a rotação para a direita conhecida como rotação zig. Após realizar a rotação para a direita, o nó 9 se torna o nó raiz, conforme mostrado abaixo:
Como podemos observar na árvore acima que o nó 13 é um nó raiz; portanto, a pesquisa está concluída. Neste caso, primeiro realizamos a rotação zag (rotação para a esquerda) e depois a rotação zig (rotação para a direita), por isso é conhecida como rotação zag zig.
Vantagens da árvore Splay
- Na árvore splay, não precisamos armazenar informações extras. Por outro lado, nas árvores AVL, precisamos armazenar o fator de equilíbrio de cada nó que requer espaço extra, e as árvores Vermelho-Preto também precisam armazenar um bit extra de informação que denota a cor do nó, seja Vermelho ou Preto.
- É o tipo mais rápido de árvore de pesquisa binária para diversas aplicações práticas. É usado em Compiladores Windows NT e GCC .
- Ele fornece melhor desempenho, pois os nós acessados com frequência se moverão para mais perto do nó raiz, devido ao qual os elementos podem ser acessados rapidamente nas árvores splay. É utilizado na implementação do cache, pois os dados acessados recentemente são armazenados no cache para que não precisemos ir à memória para acessar os dados e leve menos tempo.
Desvantagem da árvore Splay
A principal desvantagem da árvore splay seria que as árvores não são estritamente balanceadas, ou seja, são aproximadamente balanceadas. Às vezes, as árvores de expansão são lineares, portanto, levará O(n) tempo de complexidade.
Operação de inserção na árvore Splay
No inserção operação, primeiro inserimos o elemento na árvore e depois executamos a operação de expansão no elemento inserido.
15, 10, 17, 7
Passo 1: Primeiro, inserimos o nó 15 na árvore. Após a inserção, precisamos realizar a expansão. Como 15 é um nó raiz, não precisamos realizar a expansão.
Passo 2: O próximo elemento é 10. Como 10 é menor que 15, o nó 10 será o filho esquerdo do nó 15, conforme mostrado abaixo:
Agora, realizamos espalhando . Para fazer 10 como nó raiz, realizaremos a rotação para a direita, conforme mostrado abaixo:
Etapa 3: O próximo elemento é 17. Como 17 é maior que 10 e 15, ele se tornará o filho direito do nó 15.
Agora, vamos realizar o splaying. Como 17 é ter um pai e também um avô, realizaremos rotações em zigue-zague.
Na figura acima, podemos observar que 17 passa a ser o nó raiz da árvore; portanto, a inserção está concluída.
Passo 4: O próximo elemento é 7. Como 7 é menor que 17, 15 e 10, o nó 7 será filho de 10.
Agora, temos que abrir a árvore. Como 7 tem pai e também avô, realizaremos duas rotações à direita, conforme mostrado abaixo:
Ainda assim, o nó 7 não é um nó raiz, é um filho esquerdo do nó raiz, ou seja, 17. Portanto, precisamos realizar mais uma rotação para a direita para tornar o nó 7 um nó raiz, conforme mostrado abaixo:
Algoritmo para operação de inserção
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
No algoritmo acima, T é a árvore en é o nó que queremos inserir. Criamos uma variável temporária que contém o endereço do nó raiz. Executaremos o loop while até que o valor de temp se torne NULL.
Assim que a inserção for concluída, a expansão será realizada
Algoritmo para operação de Splaying
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
Na implementação acima, x é o nó no qual a rotação é realizada, enquanto y é o filho esquerdo do nó x.
Implementação de left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Na implementação acima, x é o nó no qual a rotação é realizada e y é o filho direito do nó x.
Exclusão na árvore Splay
Como sabemos que as árvores splay são variantes da árvore de pesquisa binária, a operação de exclusão na árvore splay seria semelhante ao BST, mas a única diferença é que a operação de exclusão é seguida nas árvores splay pela operação splay.
Tipos de exclusões:
Existem dois tipos de exclusões nas árvores de expansão:
- Jogada de baixo para cima
- Abertura de cima para baixo
Jogada de baixo para cima
No espalhamento de baixo para cima, primeiro excluímos o elemento da árvore e depois realizamos o espalhamento no nó excluído.
Vamos entender a exclusão na árvore do Splay.
Suponha que queiramos excluir 12, 14 da árvore mostrada abaixo:
amisha patel
- Primeiro, simplesmente executamos a operação de exclusão padrão do BST para excluir 12 elementos. Como 12 é um nó folha, simplesmente excluímos o nó da árvore.
A exclusão ainda não foi concluída. Precisamos exibir o pai do nó excluído, ou seja, 10. Temos que executar Mostrar(10) na árvore. Como podemos observar na árvore acima que 10 está à direita do nó 7, e o nó 7 está à esquerda do nó 13. Então, primeiro, realizamos a rotação para a esquerda no nó 7 e depois realizamos a rotação para a direita no nó 13, conforme mostrado abaixo:
Ainda assim, o nó 10 não é um nó raiz; o nó 10 é o filho esquerdo do nó raiz. Portanto, precisamos realizar a rotação correta no nó raiz, ou seja, 14 para tornar o nó 10 um nó raiz, conforme mostrado abaixo:
- Agora, temos que deletar o elemento 14 da árvore, que é mostrado abaixo:
Como sabemos que não podemos simplesmente deletar o nó interno. Substituiremos o valor do nó usando antecessor em ordem ou sucessor em ordem . Suponha que usemos sucessor em ordem, no qual substituímos o valor pelo valor mais baixo que existe na subárvore direita. O valor mais baixo na subárvore direita do nó 14 é 15, então substituímos o valor 14 por 15. Como o nó 14 se torna o nó folha, podemos simplesmente excluí-lo conforme mostrado abaixo:
Ainda assim, a exclusão não foi concluída. Precisamos realizar mais uma operação, ou seja, expansão na qual precisamos tornar o pai do nó excluído o nó raiz. Antes da exclusão, o pai do nó 14 era o nó raiz, ou seja, 10, portanto, precisamos realizar qualquer expansão neste caso.
Abertura de cima para baixo
No splaying de cima para baixo, primeiro realizamos o splaying no qual a exclusão será realizada e, em seguida, excluímos o nó da árvore. Assim que o elemento for excluído, realizaremos a operação de junção.
Vamos entender o splaying de cima para baixo por meio de um exemplo.
Suponha que queiramos excluir 16 da árvore mostrada abaixo:
Passo 1: Na expansão de cima para baixo, primeiro realizamos a expansão no nó 16. O nó 16 tem pai e também avô. O nó 16 está à direita do seu pai e o nó pai também está à direita do seu pai, portanto esta é uma situação de zag zag. Neste caso, primeiro realizaremos a rotação para a esquerda no nó 13 e depois no nó 14 conforme mostrado abaixo:
O nó 16 ainda não é um nó raiz e é um filho direito do nó raiz, portanto, precisamos realizar rotação para a esquerda no nó 12 para tornar o nó 16 um nó raiz.
Assim que o nó 16 se tornar um nó raiz, excluiremos o nó 16 e obteremos duas árvores diferentes, ou seja, subárvore esquerda e subárvore direita, conforme mostrado abaixo:
Como sabemos que os valores da subárvore esquerda são sempre menores que os valores da subárvore direita. A raiz da subárvore esquerda é 12 e a raiz da subárvore direita é 17. O primeiro passo é encontrar o elemento máximo na subárvore esquerda. Na subárvore esquerda, o elemento máximo é 15 e então precisamos realizar a operação de expansão em 15.
Como podemos observar na árvore acima, o elemento 15 tem um pai e também um avô. Um nó está à direita de seu pai, e o nó pai também está à direita de seu pai, então precisamos realizar duas rotações para a esquerda para tornar o nó 15 um nó raiz, conforme mostrado abaixo:
Após realizar duas rotações na árvore, o nó 15 se torna o nó raiz. Como podemos ver, o filho direito de 15 é NULL, então anexamos o nó 17 à parte direita de 15 como mostrado abaixo, e esta operação é conhecida como juntar Operação.
Nota: Se o elemento não estiver presente na árvore de expansão, que deve ser excluída, a expansão será executada. A exibição seria realizada no último elemento acessado antes de atingir o NULL.
Algoritmo de operação de exclusão
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
No algoritmo acima, primeiro verificamos se a raiz é nula ou não; se a raiz for NULL significa que a árvore está vazia. Se a árvore não estiver vazia, realizaremos a operação de expansão no elemento que será excluído. Assim que a operação de distribuição for concluída, compararemos os dados raiz com o elemento que será excluído; se ambos não forem iguais significa que o elemento não está presente na árvore. Se forem iguais, podem ocorrer os seguintes casos:
Caso 1 : A esquerda da raiz é NULL, a direita da raiz se torna o nó raiz.
Caso 2 : Se existirem esquerda e direita, então exibimos o elemento máximo na subárvore esquerda. Quando a expansão for concluída, o elemento máximo se tornará a raiz da subárvore esquerda. A subárvore direita se tornaria o filho direito da raiz da subárvore esquerda.