Please enable JavaScript.

Coggle requires JavaScript to display documents.

M9 (AVL) - Coggle Diagram

- - - - A árvore está agora equilibrada.
        
        Uma rotação à esquerda é realizada tornando B o novo nó raiz da subárvore. A torna-se a subárvore esquerda de sua subárvore direita B.
        
        O nó A ainda está desbalanceado por causa da subárvore direita de sua subárvore direita e requer uma rotação à esquerda.
        
        Primeiro, realizamos a rotação à direita ao longo do nó C, tornando C a subárvore direita de sua própria subárvore esquerda B. Agora, B se torna a subárvore direita de A.
        
        Um nó foi inserido na subárvore esquerda da subárvore direita. Isso torna A, um nó desequilibrado com fator de equilíbrio 2.
    - - Um nó foi inserido na subárvore direita da subárvore esquerda. Isso torna C um nó desbalanceado. Esses cenários fazem com que a árvore AVL execute a rotação esquerda-direita.
        
        Primeiro realizamos a rotação à esquerda na subárvore esquerda de C. Isso torna A, a subárvore esquerda de B.
        
        A árvore está agora equilibrada.
        
        Vamos agora rodar a árvore para a direita, tornando B o novo nó raiz desta subárvore. C agora se torna a subárvore direita de sua própria subárvore esquerda.
        
        O nó C ainda está desequilibrado, mas agora é por causa da subárvore esquerda da subárvore esquerda.
  - - - Como a arvore é balanceada, a pesquisa é O(LogN)
    - - O algoritmo de inserção garante o balanceamento da arvore
      - A altura entre o nó da direita e esquerda nunca é maior que 1, sempre é 0 ou -1