Introdução à árvore AVL na estrutura de dados
A árvore AVL na estrutura de dados refere-se à árvore Adelson, Velski e Landis. Esta é uma versão aprimorada da árvore de pesquisa binária. Ele possui todos os recursos da Árvore de Pesquisa Binária, mas difere apenas porque mantém uma diferença entre a altura da subárvore esquerda e da subárvore direita e também garante que seu valor seja <= 1 na Árvore, conhecido como Equilíbrio. Fator.
Balance Factor = height(left-subtree) − height(right-subtree)
Por exemplo: considere as seguintes árvores
No exemplo acima, a altura da subárvore direita = 2 e esquerda = 3, portanto, BF = 2 que é <= 1, portanto, a árvore é considerada equilibrada.
Por que precisamos de uma árvore AVL no DS?
Enquanto trabalhamos com a Árvore de pesquisa binária, encontramos um cenário em que os elementos estão em ordem classificada. Nesses casos, todos os elementos da matriz são organizados em um lado da raiz, isso leva a um aumento na complexidade do tempo de pesquisar um elemento em uma matriz e a complexidade se torna- O (n), ou seja, a pior complexidade da árvore . Para resolver esses problemas e diminuir o tempo de busca, as árvores AVL foram inventadas por Adelson, Velski & Landis.
Exemplo:
Na figura acima, a altura da subárvore esquerda = 3 foi a
Altura da subárvore direita = 0
Assim, o fator de equilíbrio = 3-0 = 3. Assim, a pesquisa de um elemento em uma árvore desse tipo tem O (n) de complexidade, semelhante à pesquisa linear. Para evitar que a árvore AVL de pesquisa complexa tenha sido introduzida, onde todos os nós da árvore precisam manter
fator de equilíbrio <= 1, caso contrário, várias técnicas de rotação devem ser executadas para equilibrar essa árvore.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Tipos de Rotações
Quando o fator de equilíbrio da árvore não satisfaz a condição <= 1, é necessário executar rotações para transformá-lo em uma árvore equilibrada.
Existem 4 tipos de rotações:
1. Rotação Esquerda: Se a adição de um nó à direita da árvore o fizer desequilibrar, nesse caso, a Rotação Esquerda precisará ser executada.
2. Rotação à Direita: Se a adição de um nó à esquerda da árvore faz com que o nó desequilibre, é necessário executar a Rotação à Direita. Em outras palavras, quando o número de nós aumenta no lado esquerdo, surge a necessidade de deslocar os elementos para o lado direito para equilibrá-lo, assim, é dito que é rotação direita.
3. Rotação Esquerda-Direita: Este tipo de rotação é uma combinação das 2 rotações acima explicadas. Esse tipo de rotação ocorre quando um elemento é adicionado à subárvore direita de uma árvore esquerda.
Nesse caso, primeiro, execute a rotação esquerda na subárvore seguida de uma rotação direita da árvore esquerda.
4. Rotação Direita-Esquerda: Este tipo de rotação também é composto por uma sequência acima de 2 rotações. Esse tipo de rotação é necessário quando um elemento é adicionado à esquerda da subárvore direita e a árvore fica desequilibrada. Nesse caso, primeiro executamos a rotação direita na subárvore direita e depois a rotação esquerda na árvore direita.
Operações na árvore AVL no DS
Abaixo de 3 operações que podem ser executadas na árvore AVL: -
1. Pesquisa
Esta operação é semelhante a executar uma pesquisa na Árvore de Pesquisa Binária. Os passos seguidos são os seguintes:
- Leia o elemento fornecido pelo usuário, diga x.
- Compare o elemento da raiz, se for o mesmo, em seguida, saia. Caso contrário, vá para a próxima etapa.
- Se x
Senão, vá para a criança certa e compare novamente.
Siga os processos B e C até encontrar o elemento e sair.
Esse processo tem complexidade O (log n).
Exemplo:
 | Considere esta árvore, onde precisamos realizar uma pesquisa pelo valor do nó 9. Primeiro, deixe x = 9, valor raiz (12)> x, em seguida, o valor deve estar na subárvore esquerda do elemento raiz. |
 | Agora x é comparado com o valor do nó 3 x> 3, portanto, devemos avançar em direção à subárvore direita. |
 | Agora x é comparado com o nó (9), onde 9 == 9 retorna verdadeiro. Assim, a pesquisa de elementos é concluída na árvore. |
2. Inserção
Ao inserir um elemento na árvore do AVL, precisamos encontrar o elemento específico da localização que precisa ser inserido e, em seguida, o elemento é anexado da mesma forma que uma inserção no BST, mas depois disso, é verificado se a árvore ainda está equilibrada ou não. isto é, o fator de equilíbrio de um nó é <= 1. E rotações específicas são realizadas conforme necessário.
A complexidade é O (log n).
Exemplo: considere a árvore abaixo,
 | Cada nó tem um fator de equilíbrio como 0, -1 ou 1, portanto, a árvore é equilibrada. Agora vamos o que acontece quando um nó com o valor 1 é inserido. A primeira árvore é percorrida para encontrar o local onde precisa ser inserida… 1 <2 é assim escrito como filho esquerdo do nó (2). |
 | Após a inserção, o nó (9) se torna desequilibrado com um fator de equilíbrio = 2. Agora, ele é submetido a rotação correta. |
 | Uma árvore se torna equilibrada após a rotação à direita e, assim, a operação de inserção é concluída com êxito. |
3. Exclusão
A exclusão de um elemento na árvore do AVL também inclui a pesquisa de um elemento na árvore e a exclusão dele. A operação de pesquisa é igual à BST e, após localizar o elemento a ser excluído, o elemento é removido da árvore e os elementos são ajustados para torná-lo BST novamente. Após a verificação desses elementos, o fator de equilíbrio é 0, -1 ou 1 e, portanto, são realizadas rotações adequadas para torná-lo equilibrado.
Complexidade se O (log n).
 | Considere a árvore fornecida, cujos fatores de equilíbrio são 0, -1 ou 1. Agora vamos excluir um nó com o valor 16. A primeira árvore é percorrida para encontrar o nó com o valor 16 igual a um algoritmo de pesquisa. |
 | O nó 16 será substituído pelo antecessor inorder deste nó, que é o maior elemento da subárvore esquerda, ou seja, 12 A árvore ficou desequilibrada, portanto, a rotação LL precisa ser executada. |
 | Agora cada nó ficou equilibrado. |
Conclusão - Árvore AVL na estrutura de dados
A árvore AVL é descendente da Árvore de Pesquisa Binária, mas supera sua desvantagem de aumentar a complexidade no caso de os elementos serem classificados. Ele monitora o fator de equilíbrio da árvore como 0 ou 1 ou -1. Caso a árvore se torne desequilibrada, são executadas técnicas de rotação correspondentes para equilibrar a árvore.
Artigos recomendados
Este é um guia para a árvore AVL na estrutura de dados. Aqui discutimos a árvore Introdução, Operações na árvore AVL no DS e Tipos de rotações. Você também pode consultar nossos outros artigos relacionados para saber mais:
- Elementos jQuery
- O que é ciência de dados
- Tipos de árvores na estrutura de dados
- Tipos de dados C #