Árvore AVL

Este método calcula o índice de balanceamento para um nó arbitrário. Este cálculo é feito através da diferença entre esquerda e direita, onde esquerda é a "altura" da sub-árvore esquerda do nó, e direita é a "altura" da sub-árvore direita do nó.

Uma sub-árvore não-nula já contabiliza a soma de uma unidade no valor da altura daquela sub-árvore. Todavia, caso aquela sub-árvore seja nula, sua "altura" será zero.

Este valor de "altura" é, portanto, não exatamente a altura da sub-árvore em si, mas sim a quantidade máxima de passos para que o nó atual chegue ao nó-folha mais baixo.

template<typename T>
int AVLTree<T>::_balance_index(const AVLTree::node_t *node) const
{
    if(!node) return 0;

    int left_idx =
        (!node->left) ? 0 : (1 + _height(node->left));
    int right_idx =
        (!node->right) ? 0 : (1 + _height(node->right));

    return left_idx - right_idx;
}

Uma rotação à esquerda é realizada em um certo nó a, trocando-o pela sua sub-árvore da direita b. O nó a em questão, por conseguinte, torna-se o filho esquerdo do nó b que tomou seu lugar.

A sub-árvore esquerda do nó b torna-se a sub-árvore direita do nó a.

template<typename T>
void AVLTree<T>::_lrot(AVLTree::node_t*& root)
{
    AVLTree::node_t *b = root->right->left;
    root->right->left = root;
    root = root->right;
    root->left->right = b;
}

Uma rotação à direita é realizada em um certo nó a, trocando-o pela sua sub-árvore da esquerda b. O nó a em questão, por conseguinte, torna-se o filho direito do nó b que tomou seu lugar.

A sub-árvore direita do nó b torna-se a sub-árvore esquerda do nó a.

template<typename T>
void AVLTree<T>::_rrot(AVLTree::node_t*& root)
{
    AVLTree::node_t *b = root->left->right;
    root->left->right = root;
    root = root->left;
    root->right->left = b;
}

Uma rotação dupla à direita constitui-se de rotacionar um certo nó a em duas etapas. Na primeira etapa, realizamos uma rotação à esquerda no filho esquerdo de a; em seguida, rotacionamos a à direita.

template<typename T>
void AVLTree<T>::_rrot_dbl(AVLTree::node_t*& root)
{
    _lrot(root->left);
    _rrot(root);
}

Uma rotação dupla à esquerda constitui-se de rotacionar um certo nó a em duas etapas. Na primeira etapa, realizamos uma rotação no filho direito de a; em seguida, rotacionamos a à direita.

template<typename T>
void AVLTree<T>::_lrot_dbl(AVLTree::node_t*& root)
{
    _rrot(root->right);
    _lrot(root);
}

A função de balanceamento a seguir realiza, efetivamente, o balanceamento de uma sub-árvore cuja raiz seja passada por parâmetro.

O balanceamento ocorrerá se o valor absoluto do coeficiente de balanceamento da árvore for igual a 2. Caso um valor diferente deste for encontrado, o balanceamento ocorrerá.

Esta é primariamente uma função de despacho de rotações em um nó de coeficiente com valor absoluto igual a 2.

Quando o nó problemático tem um coeficiente igual a +2, então:

• Caso o filho esquerdo do nó possua coeficiente -1, realizaremos uma rotação dupla à direita.
• Caso contrário, realizaremos uma rotação simples à direita.

Quando o nó problemático tem um coeficiente igual a -2, então:

• Caso o filho direito do nó possua coeficiente +1, realizaremos uma rotação dupla à esquerda.
• Caso contrário, realizaremos uma rotação simples à esquerda.

Por convenção, ignoramos nós nulos. Isso será útil durante a remoção.

template<typename T>
void AVLTree<T>::_balance(AVLTree::node_t*& node)
{
    if(!node) return;
    int coef = _balance_index(node);
    if(std::abs(coef) == 2) {
        if(coef == 2) {
            if(_balance_index(node->left) == -1)
                _rrot_dbl(node);
            else _rrot(node);
        } else if(coef == -2) {
            if(_balance_index(node->right) == 1)
                _lrot_dbl(node);
            else _lrot(node);
        }
    }
}

Imprimir um nó em ordem envolve imprimir recursivamente a sub-árvore de seu filho esquerdo, imprimir seu próprio valor, e imprimir recursivamente a sub-árvore de seu filho direito.

Como árvores binárias realizam inserções e remoções mantendo a hierarquia dos elementos, a impressão em ordem, para este exemplo, imprime os elementos da árvore em ordem crescente.

template<typename T>
void AVLTree<T>::_print_inorder(const AVLTree::node_t *node) const
{
    if(!node) return;
    _print_inorder(node->left);
    std::cout << node->info << ' ';
    _print_inorder(node->right);
}

Imprimir um nó em pré-ordem envolve imprimir primeiramente o valor do nó, e então imprimir recursivamente a sub-árvore dos filhos esquerdo e direito deste nó, respectivamente.

template<typename T>
void AVLTree<T>::_print_preorder(const AVLTree::node_t *node) const
{
    if(!node) return;
    std::cout << node->info << ' ';
    _print_inorder(node->left);
    _print_inorder(node->right);
}

Imprimir um nó em pós-ordem envolve, primeiramente, imprimir em recursão a sub-árvore dos filhos direito e esquerdo, e então imprimir o valor do nó atual.

template<typename T>
void AVLTree<T>::_print_postorder(const AVLTree::node_t *node) const
{
    if(!node) return;
    _print_inorder(node->left);
    _print_inorder(node->right);
    std::cout << node->info << ' ';
}

Impressão por nível envolve imprimir, em sequência, todos os nós existentes na árvore, em um formato linear. Note que esta impressão em nível não deixa explícito o relacionamento entre os nós impressos.

Para realizar esta impressão, utilizamos uma fila (std::queue) de ponteiros para nós. À medida que nós são retirados do início da fila, suas informações são impressas. Em seguida, os ponteiros para os filhos esquerdo e direito deste nó, respectivamente, são enfileirados, a não ser que sejam nulos. A impressão acaba quando não há mais nós na fila.

template<typename T>
void AVLTree<T>::_print_bylevel(const AVLTree::node_t *node) const
{
    if(!node) return;
    std::queue<const AVLTree::node_t*> nodes;
    nodes.push(node);

    while(!nodes.empty()) {
        const AVLTree::node_t *front = nodes.front();
        nodes.pop();
        if(front) {
            nodes.push(front->left);
            nodes.push(front->right);
            std::cout << front->info << ' ';
        }
    }
}

A impressão triangular é muito similar à impressão por nível, todavia utilizamos duas filas (std::queue) para realizar a impressão.

A ideia é que, ao invés de enfileirarmos os ponteiros dos nós-filhos em uma única fila, enfileiramo-nos em uma fila de "próximo nível". Quando a fila atual esvazia, quebramos uma linha na impressão, e trazemos todos os elementos da fila de "próximo nível" para a fila padrão.

Também realizamos a impressão conveniente de ponteiros nulos. Com esta prática, passa a ser extremamente simples o ato de tomar uma saída triangular e desenhar uma árvore binária apropriada em papel.

template<typename T>
void AVLTree<T>::_print_triangle(const AVLTree::node_t *node) const
{
    if(!node) return;
    std::queue<const AVLTree::node_t*> curr;
    std::queue<const AVLTree::node_t*> next;

    curr.push(node);

    while(!curr.empty()) {
        const AVLTree::node_t *front = curr.front();
        curr.pop();
        if(!front)
            std::cout << '*';
        else {
            next.push(front->left);
            next.push(front->right);
            std::cout << front->info;
        }

        std::cout << ' ';
        if(curr.empty() && !next.empty()) {
            std::swap(curr, next);
            std::cout << std::endl;
        }
    }
}

Tomemos a impressão triangular a seguir:

28 
22 35 
20 25 32 39 
13 * * * * 33 * 51 
* * * * * * 

Sabendo que estamos tratando de uma árvore binária, podemos deduzir os relacionamentos:

• 28 é pai de 22 e 35;
• 22 é pai de 20 e 25;
• 35 é pai de 32 e 39;
• 20 é pai de 13 e *;
• 25 é pai de * e * (portanto, um nó folha);
• 32 é pai de * e 33;
• 39 é pai de * e 51;
• 13 é pai de * e * (portanto, um nó folha);
• 33 é pai de * e * (portanto, um nó folha);
• 51 é pai de * e * (portanto, um nó folha).

Assim, teremos a árvore AVL conforme desenhado a seguir.

Insere uma certa informação na árvore. Retorna um valor booleano indicando o status da inserção de tal informação.

template<typename T>
bool AVLTree<T>::insert(T info)
{
    return _insert(info, _root);
}

Imprime a árvore por inteiro, de acordo com o estilo de impressão fornecido, segundo a enumeração demonstrada na Seção No description for this link.

Caso o programador opte por não informar o estilo de impressão, uma impressão em ordem será feita por padrão.

template<typename T>
void AVLTree<T>::print(TreePrintStyle style) const
{
    switch(style) {
    case TREEPRINT_INORDER:
        _print_inorder(_root);
        break;
    case TREEPRINT_PREORDER:
        _print_preorder(_root);
        break;
    case TREEPRINT_POSTORDER:
        _print_postorder(_root);
        break;
    case TREEPRINT_LEVEL:
        _print_bylevel(_root);
        break;
    case TREEPRINT_TRIANGLE:
        _print_triangle(_root);
        break;
    default: std::cout << "Unimplemented"; break;
    }
    std::cout << std::endl;
}

Limpa todos os elementos da árvore.

Este método atribui apropriadamente o valor de nulidade à raiz da árvore, ao contrário do destrutor, pois pode ser invocado antes da inserção de mais elementos.

template<typename T>
void AVLTree<T>::clear(void)
{
    _clear(_root);
    _root = nullptr;
}

Pesquisa por um elemento na árvore, que será passado por valor para este método.

Retorna um valor booleano representando a existência do elemento na árvore.

template<typename T>
bool AVLTree<T>::search(const T info) const
{
    return _search(_root, info);
}

Remove um elemento na árvore, que será passado por valor para este método.

Retorna um valor booleano representando o status de remoção do elemento na árvore.

template<typename T>
bool AVLTree<T>::remove(const T info)
{
    return _remove(_root, info);
}