Árvore AVL

Um dos problemas das BSTs são que elas pode ficar desbalanceadas, no pior caso, degeneradas. A árvore AVL busca remover esse problema rebalanceado a árvore sem perder as propriedades de uma BST.

Definição AVL Uma árvore AVL (Adelson-Velsky e Landis) é uma árvore binária de busca (BST) que é balanceada, ou seja, a altura de cada nó difere em no máximo uma unidade entre suas subárvores esquerda e direita. Isso garante que operações como inserção, remoção e busca sejam eficientes, com uma complexidade de tempo de O(log n).

Fator de Balanceamento

Definição Fator de Balanceamento O fator de balanceamento (fb) de um nó é a diferença entre as alturas de suas subárvores esquerda e direita. Um nó com fator de balanceamento de -1, 0 ou +1 é considerado balanceado. Para calcular o fator, basta fazer a diferença entre a quantidade de níveis da subárvore esquerda e a quantidade de níveis da subárvore direta. O fator de balanceamento das folhas é sempre zero.

Significado Os valores do fb nos dizem o estado de balanceamento de um nó:

fb = 0: A subárvore esquerda e a subárvore direita têm a mesma altura. O nó está perfeitamente balanceado. fb = +1: A subárvore esquerda é uma aresta mais alta que a subárvore direita. O nó está balanceado, mas com uma leve inclinação para a esquerda. fb = -1: A subárvore direita é uma aresta mais alta que a subárvore esquerda. O nó está balanceado, mas com uma leve inclinação para a direita. Em qualquer outro caso, será necessário um rebalanceamento.

Exemplo Neste exemplo, cada nó, além da chave, possui o fator de balanceamento. Onde não há indicação significa que o fb é zero. Como todos os nós estão com fator de balanceamento dentro do limite permitido ([-1,1]), esta árvore é AVL.

flowchart TB
    A(("12")) --- B(("08"))
    A --- C(("18"))
    B --- D(("05"))
    B --- E(("11"))
    C --- F(("17"))
    C --- I1((" "))
    D --- G(("04"))
    D --- I2((" "))

A:::BL
B:::BL
C:::BL
D:::BL
E:::WT
F:::WT
G:::WT

style I1 stroke:none,fill:transparent
style I2 stroke:none,fill:transparent
linkStyle 5 stroke:none,fill:none
linkStyle 7 stroke:none,fill:none
classDef WT fill:#FFFFFF
classDef BL fill:#BBDEFB

Neste caso, temos o nó com chave 8 desbalanceado. Além dele, a raiz também está desbalanceada. Por essa razão, a árvore ilustrada não é AVL.

flowchart TB
    A(("12")) --- B(("08"))
    A --- C(("18"))
    B --- D(("05"))
    B --- E(("11"))
    C --- F(("17"))
    C --- I1((" "))
    D --- G(("04"))
    D --- H(("07"))
    G --- I(("02"))
    G --- I2((" "))
    

A:::RE
B:::RE
C:::BL
D:::BL
E:::WT
F:::WT
G:::BL
H:::WT
I:::WT

style I1 stroke:none,fill:transparent
style I2 stroke:none,fill:transparent
linkStyle 5 stroke:none,fill:none
linkStyle 9 stroke:none,fill:none
classDef WT fill:#FFFFFF
classDef BL fill:#BBDEFB
classDef RE fill:#FFCDD2

Rotações

Rotação Para manter o balanceamento, a árvore AVL realiza operações de rotação. Elas são necessárias após inserções ou remoções para redistribuir os nós e garantir que o balanceamento seja preservado.

Rotação Inserção/Remoção: Após esta operação, a árvore AVL verifica o fator de balanceamento dos nós afetados. Rotação: Se um nó tiver um fator de balanceamento fora do intervalo aceitável (-1 a 1), uma rotação é realizada para restabelecer o balanceamento. Atualização: A altura e o fator de balanceamento de todos os nós afetados pela rotação são atualizados.

Tipos de Rotações As rotações podem ser divididas em simples ou duplas, além da direção esquerda ou direita. Como fb é a diferença entra as alturas das subárvores esquerda e direita, se

fb > 1: deve-se rotacionar para a direita; fb < 1: deve-se rotacionar para a esquerda; Sobre se a rotação é simples ou dupla, é necessário verificar o sinal do fb do filho.

Rotações Simples

Rotação à Direita Considere que \(fb(B) > 1\). Além disso, \(fb(A) \geq 0\).

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(" ")
        D(" ")
        E(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(" ")
        D1(" ")
        E1(" ")
  end

    B --- A
    B --- C
    A --- D
    A --- E

    A1 --- D1
    A1 --- B1
    B1 --- E1
    B1 --- C1

   s1 ---> s2

A:::WT
B:::WT
A1:::WT
B1:::WT

C@{ shape: tri}
D@{ shape: tri}
E@{ shape: tri}
C1@{ shape: tri}
D1@{ shape: tri}
E1@{ shape: tri}
style C fill:#2962FF,stroke:none
style D fill:#00C853,stroke:none
style E fill:#D50000,stroke:none    
style C1 fill:#2962FF,stroke:none
style D1 fill:#00C853,stroke:none
style E1 fill:#D50000,stroke:none    
classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent

Exemplo Claramente, o nó C está desbalanceado com um fator igual a +2. É necessário que seja realizada uma rotação para a direita. Desse modo, o nó B funciona como um pivô.

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        I1(" ")
        I2(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(("C"))
  end

    C --- B
    C --- I1
    B --- A
    B --- I2

    B1 --- A1
    B1 --- C1

   s1 ---> s2

A:::WT
B:::WT
C:::WT
A1:::WT
B1:::WT
C1:::WT

classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent
style I1 stroke:none,fill:transparent
style I2 stroke:none,fill:transparent
linkStyle 1 stroke:none,fill:none    
linkStyle 3 stroke:none,fill:none

Claramente, o nó A está desbalanceado com um fator igual a +2. É necessário que seja realizada uma rotação para a direita. Como A deve se tornar filho da direita de B, devemos realocar D como filho da esquerda de A.

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        D(("D"))
        I1(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(("C"))
        D1(("D"))
        I2(" ")
  end

    D --- B
    D --- I1
    B --- A
    B --- C

    B1 --- A1
    B1 --- D1
    D1 --- C1
    D1 --- I2

   s1 ---> s2

A:::WT
B:::WT
C:::WT
D:::WT
A1:::WT
B1:::WT
C1:::WT
D1:::WT
classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent
style I1 stroke:none,fill:transparent
style I2 stroke:none,fill:transparent
linkStyle 1 stroke:none,fill:none    
linkStyle 7 stroke:none,fill:none

Rotação à Esquerda A rotação à esquerda é dual à direta.

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(" ")
        D(" ")
        E(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(" ")
        D1(" ")
        E1(" ")
  end

    A --- D
    A --- B
    B --- E
    B --- C

    B1 --- A1
    B1 --- C1
    A1 --- D1
    A1 --- E1

   s1 ---> s2

A:::WT
B:::WT
A1:::WT
B1:::WT

C@{ shape: tri}
D@{ shape: tri}
E@{ shape: tri}
C1@{ shape: tri}
D1@{ shape: tri}
E1@{ shape: tri}
style C fill:#2962FF,stroke:none
style D fill:#00C853,stroke:none
style E fill:#D50000,stroke:none    
style C1 fill:#2962FF,stroke:none
style D1 fill:#00C853,stroke:none
style E1 fill:#D50000,stroke:none    
classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent

Exemplo Qual nó está desbalanceado? Qual rotação deve ser aplicada? Qual a árvore resultante dessa operação?

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        D(("D"))
        E(("E"))
        F(("F"))
        I1(" ")
  end


    B --- A
    B --- D
    D --- C
    D --- E
    E --- I1
    E --- F


A:::WT
B:::WT
C:::WT
D:::WT
E:::WT
F:::WT
classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style I1 stroke:none,fill:transparent
linkStyle 4 stroke:none,fill:none

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        D(("D"))
        E(("E"))
        F(("F"))
        I1(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(("C"))
        D1(("D"))
        E1(("E"))
        F1(("F"))
        I2(" ")
  end

    B --- A
    B --- D
    D --- C
    D --- E
    E --- I1
    E --- F
    
    D1 --- B1
    D1 --- E1
    B1 --- A1
    B1 --- C1
    E1 --- I2
    E1 --- F1

    s1 ---> s2

A:::WT
B:::WT
C:::WT
D:::WT
E:::WT
F:::WT
A1:::WT
B1:::WT
C1:::WT
D1:::WT
E1:::WT
F1:::WT
classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent
style I1 stroke:none,fill:transparent
style I2 stroke:none,fill:transparent
linkStyle 4 stroke:none,fill:none    
linkStyle 10 stroke:none,fill:none

Nota Você irá perceber que, teoricamente, só precisamos de uma rotação. Primeiro, porque as rotações à esquerda e direita são espelhadas. Segundo, como você notará, as rotações duplas pode ser divididas em simples.

Uma rotação dupla à esquerda, por exemplo, não significa duas rotações à esquerda, mas uma para a direita na subárvore seguida de uma para a esquerda. Todavia, para diminuir o número de operações, podemos fazer tudo em um passo só.

Rotações Duplas

Rotação à Direita Em dois passos. Rotação para a esquerda em B, depois para a direita em A.

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        verde(" ")
        vermelho(" ")
        azul(" ")
        amarelo(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(("C"))
        verde1(" ")
        vermelho1(" ")
        azul1(" ")
        amarelo1(" ")
  end

 subgraph s3[" "]
        A2(("A"))
        B2(("B"))
        C2(("C"))
        verde2(" ")
        vermelho2(" ")
        azul2(" ")
        amarelo2(" ")
  end

    C --- A
    C --- amarelo
    A --- verde
    A --- B
    B --- vermelho
    B --- azul

    C1 --- B1
    C1 --- amarelo1
    B1 --- A1
    B1 --- azul1
    A1 --- verde1
    A1 --- vermelho1

    B2 --- A2
    B2 --- C2
    A2 --- verde2
    A2 --- vermelho2
    C2 --- azul2
    C2 --- amarelo2
  

   s1 ---> s2
   s2 ---> s3

A:::WT
B:::WT
C:::WT
A1:::WT
B1:::WT
C1:::WT
A2:::WT
B2:::WT
C2:::WT

verde@{ shape: tri}
vermelho@{ shape: tri}
azul@{ shape: tri}
amarelo@{ shape: tri}
verde1@{ shape: tri}
vermelho1@{ shape: tri}
azul1@{ shape: tri}
amarelo1@{ shape: tri}
verde2@{ shape: tri}
vermelho2@{ shape: tri}
azul2@{ shape: tri}
amarelo2@{ shape: tri}

style verde fill:#00C853,stroke:none
style vermelho fill:#D50000,stroke:none    
style azul fill:#2962FF,stroke:none
style amarelo fill:#FFD600,stroke:none

style verde1 fill:#00C853,stroke:none
style vermelho1 fill:#D50000,stroke:none    
style azul1 fill:#2962FF,stroke:none
style amarelo1 fill:#FFD600,stroke:none

style verde2 fill:#00C853,stroke:none
style vermelho2 fill:#D50000,stroke:none    
style azul2 fill:#2962FF,stroke:none
style amarelo2 fill:#FFD600,stroke:none

classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent       
style s3 stroke:none,fill:transparent

Em um único passo. Considere \(fb(A) > 1\) e \(fb(B) < 0\).

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        verde(" ")
        vermelho(" ")
        azul(" ")
        amarelo(" ")
  end

 subgraph s3[" "]
        A2(("A"))
        B2(("B"))
        C2(("C"))
        verde2(" ")
        vermelho2(" ")
        azul2(" ")
        amarelo2(" ")
  end

    C --- A
    C --- amarelo
    A --- verde
    A --- B
    B --- vermelho
    B --- azul

    B2 --- A2
    B2 --- C2
    A2 --- verde2
    A2 --- vermelho2
    C2 --- azul2
    C2 --- amarelo2
  

   s1 ---> s3

A:::WT
B:::WT
C:::WT
A2:::WT
B2:::WT
C2:::WT

verde@{ shape: tri}
vermelho@{ shape: tri}
azul@{ shape: tri}
amarelo@{ shape: tri}
verde2@{ shape: tri}
vermelho2@{ shape: tri}
azul2@{ shape: tri}
amarelo2@{ shape: tri}

style verde fill:#00C853,stroke:none
style vermelho fill:#D50000,stroke:none    
style azul fill:#2962FF,stroke:none
style amarelo fill:#FFD600,stroke:none

style verde2 fill:#00C853,stroke:none
style vermelho2 fill:#D50000,stroke:none    
style azul2 fill:#2962FF,stroke:none
style amarelo2 fill:#FFD600,stroke:none

classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s3 stroke:none,fill:transparent

Rotação à Esquerda Em dois passos. Rotação para a direita em B, depois para a esquerda em A.

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        verde(" ")
        vermelho(" ")
        azul(" ")
        amarelo(" ")
  end

 subgraph s2[" "]
        A1(("A"))
        B1(("B"))
        C1(("C"))
        verde1(" ")
        vermelho1(" ")
        azul1(" ")
        amarelo1(" ")
  end

 subgraph s3[" "]
        A2(("A"))
        B2(("B"))
        C2(("C"))
        verde2(" ")
        vermelho2(" ")
        azul2(" ")
        amarelo2(" ")
  end

    A --- verde
    A --- C
    C --- B
    C --- amarelo
    B --- vermelho
    B --- azul

    A1 --- verde1
    A1 --- B1
    B1 --- vermelho1
    B1 --- C1
    C1 --- azul1
    C1 --- amarelo1

    B2 --- A2
    B2 --- C2
    A2 --- verde2
    A2 --- vermelho2
    C2 --- azul2
    C2 --- amarelo2
  

   s1 ---> s2
   s2 ---> s3

A:::WT
B:::WT
C:::WT
A1:::WT
B1:::WT
C1:::WT
A2:::WT
B2:::WT
C2:::WT

verde@{ shape: tri}
vermelho@{ shape: tri}
azul@{ shape: tri}
amarelo@{ shape: tri}
verde1@{ shape: tri}
vermelho1@{ shape: tri}
azul1@{ shape: tri}
amarelo1@{ shape: tri}
verde2@{ shape: tri}
vermelho2@{ shape: tri}
azul2@{ shape: tri}
amarelo2@{ shape: tri}

style verde fill:#00C853,stroke:none
style vermelho fill:#D50000,stroke:none    
style azul fill:#2962FF,stroke:none
style amarelo fill:#FFD600,stroke:none

style verde1 fill:#00C853,stroke:none
style vermelho1 fill:#D50000,stroke:none    
style azul1 fill:#2962FF,stroke:none
style amarelo1 fill:#FFD600,stroke:none

style verde2 fill:#00C853,stroke:none
style vermelho2 fill:#D50000,stroke:none    
style azul2 fill:#2962FF,stroke:none
style amarelo2 fill:#FFD600,stroke:none

classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent       
style s3 stroke:none,fill:transparent

Em um único passo. Considere \(fb(A) < -1\) e \(fb(B) > 0\)

flowchart LR
 subgraph s1[" "]
        A(("A"))
        B(("B"))
        C(("C"))
        verde(" ")
        vermelho(" ")
        azul(" ")
        amarelo(" ")
  end


 subgraph s3[" "]
        A2(("A"))
        B2(("B"))
        C2(("C"))
        verde2(" ")
        vermelho2(" ")
        azul2(" ")
        amarelo2(" ")
  end

    A --- verde
    A --- C
    C --- B
    C --- amarelo
    B --- vermelho
    B --- azul

    B2 --- A2
    B2 --- C2
    A2 --- verde2
    A2 --- vermelho2
    C2 --- azul2
    C2 --- amarelo2
  

   s1 ---> s3

A:::WT
B:::WT
C:::WT
A2:::WT
B2:::WT
C2:::WT

verde@{ shape: tri}
vermelho@{ shape: tri}
azul@{ shape: tri}
amarelo@{ shape: tri}
verde2@{ shape: tri}
vermelho2@{ shape: tri}
azul2@{ shape: tri}
amarelo2@{ shape: tri}

style verde fill:#00C853,stroke:none
style vermelho fill:#D50000,stroke:none    
style azul fill:#2962FF,stroke:none
style amarelo fill:#FFD600,stroke:none

style verde2 fill:#00C853,stroke:none
style vermelho2 fill:#D50000,stroke:none    
style azul2 fill:#2962FF,stroke:none
style amarelo2 fill:#FFD600,stroke:none

classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s3 stroke:none,fill:transparent

Nesta aula, estudamos a estrutura de dados árvore AVL:

✅ definimos essa estrutura baseada em BST;

✅ definimos o fator de balanceamento de um nó;

✅ estudamos as rotações: simples e dupla

Na próxima aula, iremos abordar as operações de inserção, busca e remoção em AVL e como as rotações são aplicadas nessas operações.

# Qual problema das BSTs a árvore AVL busca resolver ? > Considere o pior caso discutido no texto. 1. [ ] O alto custo de inserção em média 1. [ ] A impossibilidade de remoção de nós 1. [x] O desbalanceamento que pode levar à degeneração 1. [ ] A ausência de funções de comparação # Definição de Árvore AVL > Baseie-se na definição formal apresentada. 1. [ ] Uma árvore binária completa 1. [ ] Uma árvore binária sem ordenação 1. [x] Uma BST balanceada com diferença de altura máxima de 1 1. [ ] Uma árvore com fator de balanceamento sempre zero # Como é definido o fator de balanceamento de um nó? 1. [ ] Soma das alturas das subárvores 1. [x] Diferença entre as alturas da subárvore esquerda e direita 1. [ ] Altura total da árvore 1. [ ] Número de filhos do nó # Quando um nó é considerado balanceado? - [x] fb = -1 - [x] fb = 0 - [x] fb = +1 - [ ] fb = +2 # Fator de balanceamento das folhas > Considere a definição apresentada. 1. [ ] Sempre +1 1. [ ] Sempre -1 1. [x] Sempre 0 1. [ ] Depende da altura da árvore # Interpretação de fb = +1 > Analise o significado do fator. 1. [ ] A subárvore direita é mais alta 1. [x] A subárvore esquerda é uma aresta mais alta 1. [ ] O nó está desbalanceado 1. [ ] O nó precisa de rotação dupla # Em qual situação uma rotação é necessária? 1. [ ] Sempre após uma inserção 1. [ ] Sempre após uma remoção 1. [x] Quando o fator de balanceamento sai do intervalo [-1, 1] 1. [ ] Quando o nó é folha # Qual a finalidade das rotações? - [x] Restaurar o balanceamento da árvore - [x] Preservar as propriedades de uma BST - [ ] Eliminar a necessidade de comparações - [ ] Reduzir o número de nós da árvore # Segundo o texto, a rotação à esquerda é: 1. [ ] Independente da rotação à direita 1. [ ] Aplicada quando fb > 1 1. [x] Dual (espelhada) da rotação à direita 1. [ ] Exclusiva para rotações duplas # Como pode ser interpretada uma rotação dupla? 1. [ ] Duas rotações na mesma direção 1. [x] Uma combinação de rotações simples em direções opostas 1. [ ] Uma rotação aplicada apenas na raiz 1. [ ] Uma rotação sem atualização de fatores # O que deve ser atualizado após uma rotação? - [x] Altura dos nós afetados - [x] Fator de balanceamento dos nós afetados - [ ] As chaves armazenadas - [ ] A ordem de comparação das chaves # Ordem lógica após inserção ou remoção. 1. Verificação do fator de balanceamento 2. Identificação do tipo de desbalanceamento 3. Aplicação da rotação adequada 4. Atualização das alturas e fatores # Principal vantagem da AVL sobre a BST > Conforme discutido na conclusão. 1. [ ] Menor uso de memória 1. [x] Garantia de altura logarítmica 1. [ ] Eliminação de rotações 1. [ ] Inserções mais simples # Custo adicional das AVL > Qual o trade-off apresentado? 1. [ ] Maior tempo de busca 1. [ ] Maior uso de chaves 1. [x] Mais computações devido às rotações 1. [ ] Menor eficiência em média

A árvore AVL é uma estrutura otimizada além da BST. Ela supera a possibilidade de degeneração da árvore efetuando operações de rotação. Embora essas rotações exijam mais computações, o ganho com o rebalanceamento é maior, principalmente para buscas.

No nosso próximo estudo, iremos abordar a aplicação das rotações durante as inserções e remoções de nós na árvore.

De volta ao topo