Árvores AVL

Adelson-Velskii e Landis em 1962 apresentaram uma árvore de busca binária que é balanceada com respeito a altura das sub-árvores. Uma característica importante deste tipo de árvore é que uma busca é realizada em O(lg(n)) se a árvore possui n nós. Na verdade pode ser mostrado que:

onde hb(n) é a altura da árvore AVL.

Definição: Uma árvore binária vazia é sempre balanceada por altura. Se T não é vazia e TL e TR são suas sub-árvores da esquerda e direita, então T é balanceada por altura se:

    1. TL e TR são balanceadas por altura;
    2. |hL e hR| ±1, onde hL e hR são as alturas de TL e TR respectivamente. A definição de árvore binária balanceada por altura requer que toda sub-árvore seja balanceada por altura.

    A definição de árvore binária balanceada por altura requer que toda sub-árvore seja balanceada por altura.

    Definição: O fator de balanço de um nó X em uma árvore binária é definido como sendo hL - hR, onde e são as alturas das sub-árvores da esquerda e direita de X. Para qualquer nó X em uma árvore AVL o fator de balanço é -1, 0 ou 1.

    Estrutura de um nó da Árvore

    typedef struct no_AVL AVL;

    struct no_AVL {
          int info;
          int fb; // fator de balanceamento
          AVL *pai;
          AVL *esq;
          AVL *dir;
    };

     


    Subsections