A exclusão de um nó de uma árvore AVL é semelhante à exclusão de uma árvore de pesquisa binária. A exclusão pode perturbar o fator de equilíbrio de uma árvore AVL e, portanto, a árvore precisa ser reequilibrada para manter a AVL. Para isso, precisamos realizar rotações. Os dois tipos de rotações são rotação L e rotação R. Aqui, discutiremos as rotações R. As rotações L são suas imagens espelhadas.
Se o nó a ser excluído estiver presente na subárvore esquerda do nó crítico, então a rotação L precisa ser aplicada, caso contrário, se o nó a ser excluído estiver presente na subárvore direita do nó crítico , a rotação R será aplicada.
Consideremos que A é o nó crítico e B é o nó raiz de sua subárvore esquerda. Se o nó X, presente na subárvore direita de A, for excluído, poderá haver três situações diferentes:
Rotação R0 (o nó B tem fator de equilíbrio 0)
Se o nó B tiver fator de equilíbrio 0 e o fator de equilíbrio do nó A for perturbado ao excluir o nó X, então a árvore será rebalanceada girando a árvore usando a rotação R0.
O nó crítico A é movido para a direita e o nó B torna-se a raiz da árvore com T1 como sua subárvore esquerda. As subárvores T2 e T3 tornam-se as subárvores esquerda e direita do nó A. O processo envolvido na rotação R0 é mostrado na imagem a seguir.
Exemplo:
Exclua o nó 30 da árvore AVL mostrada na imagem a seguir.
Solução
Neste caso, o nó B possui fator de equilíbrio 0, portanto a árvore será girada utilizando a rotação R0 conforme mostrado na imagem a seguir. O nó B(10) torna-se a raiz, enquanto o nó A é movido para a sua direita. O filho direito do nó B agora se tornará o filho esquerdo do nó A.
comprimento da string java
Rotação R1 (Nó B tem fator de equilíbrio 1)
A rotação R1 deve ser realizada se o fator de equilíbrio do nó B for 1. Na rotação R1, o nó crítico A é movido para a direita, tendo as subárvores T2 e T3 como filhos esquerdo e direito, respectivamente. T1 deve ser colocado como a subárvore esquerda do nó B.
O processo envolvido na rotação R1 é mostrado na imagem a seguir.
Exemplo
Exclua o nó 55 da árvore AVL mostrada na imagem a seguir.
Solução:
A exclusão de 55 da árvore AVL perturba o fator de equilíbrio do nó 50, ou seja, o nó A, que se torna o nó crítico. Esta é a condição de rotação R1 em que o nó A será movido para a sua direita (mostrado na imagem abaixo). A direita de B agora se tornou a esquerda de A (ou seja, 45).
O processo envolvido na solução é mostrado na imagem a seguir.
replicar em java
Rotação R-1 (Nó B tem fator de equilíbrio -1)
A rotação R-1 deve ser realizada se o nó B tiver fator de equilíbrio -1. Este caso é tratado da mesma forma que a rotação LR. Neste caso, o nó C, que é o filho direito do nó B, torna-se o nó raiz da árvore com B e A como filhos esquerdo e direito, respectivamente.
As subárvores T1, T2 tornam-se as subárvores esquerda e direita de B, enquanto T3, T4 tornam-se as subárvores esquerda e direita de A.
O processo envolvido na rotação R-1 é mostrado na imagem a seguir.
Exemplo
Exclua o nó 60 da árvore AVL mostrada na imagem a seguir.
Solução:
neste caso, o nó B possui fator de equilíbrio -1. A exclusão do nó 60 perturba o fator de equilíbrio do nó 50, portanto, ele precisa ser girado R-1. O nó C, ou seja, 45, torna-se a raiz da árvore com os nós B(40) e A(50) como filhos esquerdo e direito.
