Árvore AVL

Árvores AVL

Na estrutura de dados existe uma tipo de arvore de busca binaria que se destaca por seu método de balanceamento onde está baseado na diferença máxima entre o nível de nós, que não pode ultrapassar uma unidade.

Uma árvore binaria de busca é uma estrutura de dados que permite o acesso de dados tempo O(log ₂ n) baseada em nós (ou nodos), onde todos os nós da subárvore esquerda possui um valor menor que o nó raiz, e os valores maiores estão na subárvore direita a raiz. Então vamos a um exemplo de árvore binaria:

           

·      Nós - são todos os itens guardados na árvore

·      Raiz - é o nó do topo da árvore

·      Filhos - são os nós que vem depois dos outros nós

·      Pais - são os nós que vem antes dos outros nós

·      Folhas - são os nós que não têm filhos; são os últimos nós da árvore

Porém pode ocorrer da ordem inserção na árvore causar a degeneração da mesma, que nada mais é que a diferença entre a altura da subárvore (esquerda ou direita) ser muito alta:

Uma das formas de garantir o balanceamento e consequentemente a eficiência da árvore  binaria de busca é utilizar a forma Árvore AVL. Árvore AVL em homenagem aos matemáticos russos (Adelson- Velskii e Landism).

Uma árvore AVL é uma árvore binária de pesquisa onde a diferença em altura entre as subárvores esquerda e direita é no máximo 1 (positivo ou negativo).

A essa diferença chamamos de “fator de balanceamento” de n → FB (n). Essa informação deverá constar em cada nó de uma árvore AVL balanceada.

Assim, podemos definir o fator de balanceamento como:

FB ( nodo p ) = altura ( subárvoreDireita p ) - altura ( subárvoreEsquerda p )

O fator de uma folha é sempre 0 (zero).

Para uma árvore ser AVL os fatores de balanço devem ser necessariamente -1, 0, ou 1. Tal balanço é atingido graças a operação de rotação(direita, esquerda, dupla esquerda ou dupla direita). Uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".

Rotação-dupla:

Definir rotação:

private NodoAvl equilibrarAVL(NodoAvl avl) {

        if (avl != null) {

            int a, b;

            avl.dir = equilibrarAVL(avl.dir);

            avl.esq = equilibrarAVL(avl.esq);

            a = ArvoreAvl.alturaAVL(avl.dir);

            b = ArvoreAvl.alturaAVL(avl.esq);

            if (a - b == 2) {

                if (valorDir(avl.dir)) {

                    avl = ArvoreAvl.rotacaoDireitaAVL(avl);

                } else {

                    avl = ArvoreAvl.rotacaoDuplaDireitaAVL(avl);

                }

            } else if (a - b == - 2) {

                if (valorEsq(avl.esq)) {

                    avl = ArvoreAvl.rotacaoEsquerdaAVL(avl);

                } else {

                    avl = ArvoreAvl.rotacaoDuplaEsquerdaAVL(avl);

                }

            }

            a = ArvoreAvl.alturaAVL(avl.dir);

            b = ArvoreAvl.alturaAVL(avl.esq);

            avl.altura = ArvoreAvl.maxAVL(a, b) + 1;

        }

        return avl;

    }

Rotações:

    /**

     * Rotacao Simples Esquerda

     *

     * @param nodo

     * @return

     */

    private static NodoAvl rotacaoEsquerdaAVL(NodoAvl nodo) {

        NodoAvl nodoIn = nodo.esq;

        int a, b;

        nodo.esq = nodoIn.dir;

        nodoIn.dir = nodo;

        a = ArvoreAvl.alturaAVL(nodo.esq);

        b = ArvoreAvl.alturaAVL(nodo.dir);

        nodo.altura = ArvoreAvl.maxAVL(a, b) + 1;

        a = ArvoreAvl.alturaAVL(nodoIn.esq);

        b = nodo.altura;

        nodoIn.altura = ArvoreAvl.maxAVL(a, b) + 1;

        return (nodoIn);

    }

    /**

     * Rotacao Simples Direita

     *

     * @param nodo

     * @return

     */

    private static NodoAvl rotacaoDireitaAVL(NodoAvl nodo) {

        NodoAvl nodoIn = nodo.dir;

        int a, b;

        nodo.dir = nodoIn.esq;

        nodoIn.esq = nodo;

        a = ArvoreAvl.alturaAVL(nodo.esq);

        b = ArvoreAvl.alturaAVL(nodo.dir);

        nodo.altura = ArvoreAvl.maxAVL(a, b) + 1;

        a = ArvoreAvl.alturaAVL(nodoIn.dir);

        b = nodo.altura;

        nodoIn.altura = ArvoreAvl.maxAVL(a, b) + 1;

        return (nodoIn);

    }

    /**

     * Rotacao Dupla Esquerda

     *

     * @param nodo

     * @return

     */

    private static NodoAvl rotacaoDuplaEsquerdaAVL(NodoAvl nodo) {

        nodo.esq = ArvoreAvl.rotacaoDireitaAVL(nodo.esq);

        return (ArvoreAvl.rotacaoEsquerdaAVL(nodo));

    }

    /**

     * Rotacao Dupla Direita

     *

     * @param nodo

     * @return

     */

    private static NodoAvl rotacaoDuplaDireitaAVL(NodoAvl nodo) {

        nodo.dir = ArvoreAvl.rotacaoEsquerdaAVL(nodo.dir);

        return (ArvoreAvl.rotacaoDireitaAVL(nodo));

    }