Árvores Binárias de Pesquisa

As Árvores Binárias de Pesquisa (BST, do inglês Binary Search Trees), são estruturas de dados em forma de árvore (de grau 2), que armazenam dados em memória que permitem buscas, inserções e remoções eficientes. Os dados são armazenados de forma ordenada com relação a uma chave. As folhas de uma BST são elementos "nulos", que não armazenam chaves ou dados.

Os elementos de uma árvore binária de pesquisa possuem, normalmente, um registro, por exemplo, os dados de uma pessoa, incluindo endereço e telefone, e não apenas um valor. Além dos dados armazenados no registro, cada elemento é raiz de duas sub-árvores, uma árvore esquerda, e uma árvore direita, e estes nomes são normalmente utilizados na definição dos elementos. O Algoritmo 1 mostra uma definição de uma BST e dos seus elemetos.

Definição parcial de uma BST em Java

public class BST<K,V> {
    private class Node<K,V> {
        private K key;
        private V value;
        private Node<K,V> left;
        private Node<K,V> right;
    }

    private Node<K,V> root = null;
}

Uma árvore binária de pesquisa deve manter a propriedade que determina que todo elemento da árvore possui uma chave de valor maior ou igual a todas as chaves armazenadas na sub-árvore à esquerda do elemento, e menor que todas as chaves armazenadas na sub-árvore à direita do elemento (Figura 1).

Árvore Binária de Pesquisa Binary Search Tree

Como a árvore binária de pesquisa mantém os elementos ordenados, supondo uma BST cheia, durante a pesquisa por um elemento utilizando a chave de ordenação, ao comparar a chave de pesquisa com a chave armazenada na raiz da árvore, podemos inferir se o elemento desejado foi encontrado, ou se a chave se encontra na sub-árvore à esquerda (chave de pesquisa menor que a chave da raiz) ou à direita (chave de pesquisa maior que a chave da raiz). Considerando que o número de elementos à esquerda e à direita é o mesmo, a busca na árvore se assemelha a uma busca binária, um algoritmo com custo $O(\lg N)$, e este é o custo médio da procura em uma árvore binária de pesquisa (Algoritmo 2).

Pesquisa recursiva em uma BST

search(node, key):
    if node == null or node.key == key
        return node
    if key < node.key
        return search(node.left, key)
    else
        return search(node.right, key)

Ao criar uma árvore binária de pesquisa, estamos, na prática, criando uma ordenação para os dados, semelhante aos algoritmos de ordenação. Na inserção de um elemento em uma BST, devemos manter a propriedade de ordenação da BST, e para isso, todo novo elemento será inserido no lugar de uma folha, e a posição de inserção será determinada pela chave do elemento sendo inserido (Algoritmo 2). Como vimos, a busca tem um custo médio de $O(\lg N)$, que será o custo médio de inserção de cada elemento na BST. Agora, supondo um conjunto de N elementos, o custo média total para ordenar estes elementos, através da inserção na árvore binária de pesquisa é de $O(N\lg N)$, uma vez que executaremos a inserção $N$ vezes. Este custo médio aproxima-se dos algoritmos de ordenação eficientes.

Inserção recursiva em nós de uma BST

insert(node, key, value):
    if node == null
        return new Node(key, value)
    if key == node.key
        raise Error("Duplicate Key")
    else
        if key < node.key
            node.left = insert(node.left, key, value)
        else
            node.right = insert(node.right, key, value)
        return node

Em linguagens de programação orientadas a objetos, normalmente implementa-se a BST como uma estrutura que armazena nós, e os nós da árvore é que armazenam os dados. Para não quebrar o encapsulamento, os nós são, normalmente, estruturas acessadas apenas pela árvore, que e o código cliente não tem acesso. Nesse caso, o processo de inserção inicia na árvore (Algoritmo 3), e é então direcionado ao nó, onde é mais facilmente implementado de forma recursiva (Algoritmo 4).

Inserção em uma BST implementada com orientação a objetos

BST.insert(key, value):
   Node node = new Node(key, value)
   if this.root == null
       this.root = node
   else
       root.insert(node)

Inserção em um nó de uma BST implementada com orientação a objetos

Node.insert(node):
    if node.key < this.key:
       if node.left == null
           node.left = node
       else
           node.left.insert(node)
    else
       if node.right == null
           node.right = node
       else
           node.right.insert(node)

Um dos problemas apresentados por esse modelo simples de árvore binária de pesquisa é a não existência de um controle sobre a estrutura que a árvore toma durante a inserção de novos elementos. Note que os custos dos algoritmos vistos falam em caso médio, que ocorre em uma situação ideal, onde os dados são apresentados de forma mais ou menos aleatória. No entanto, existem situações onde os dados não são apresentados dessa forma, e a estrutura da árvore pode degenerar em uma [lista encadeada]. Nesse caso, a inserção de um elemento passa a ter custo $O(N)$ e a criação total da árvore se assemelha ao algoritmo de ordenação Insertion Sort, com custo $O(N^2)$. Estes são os custos dos algoritmos no pior caso, que ocorre quando os elementos são inseridos de forma ordenada (ou reversa) em relação à chave (Figura 2).

Árvore binária de pesquisa degenerada em uma Lista Encadeada BST Degenerada

A processo de remoção de um elemento de uma árvore binária de pesquisa deve garantir que a árvore continue válida. Ao excluir um elemento, três situações podem ocorrer. Se o elemento for uma folha, ou tiver apenas um filho, a exclusão é simples, simplesmente excluindo o elemento, ou substituindo-o pelo seu filho. O caso mais complexo ocorre quando o elemento excluído possui dois filhos. Nessa situação é necessário encontrar o elemento que sucede o elemento a ser removido (Algoritmo 6). Este elemento é o elemento que, caso os elementos estivessem em um vetor ordenado, seria o elemento posterior ao elemento a ser removido. De posse do elemento sucessor, é necessário copiar seus dados (chave, valor) para o elemento a ser removido, o que acaba removendo o conteúdo do elemento, e após a cópia excluir o elemento copiado, da árvore à direita do elemento (o sucessor é, obviamente, maior que o elemento a ser excluído) (Algoritmo 7). A segunda remoção, sempre será um dos casos simples.

Encontra o nó sucessor em uma BST.

find_successor(node):
    node = node.right
    while node.left != null
        node = node.left
    return node

Remove um nó em uma BST

delete(node, key):
    if node == null
        raise Error("Key not found")
    if key < node.key
        node.left = delete_node(node.left, key)
    else if key > node.key
        node.right = delete_node(node.right, key)
    else
        if node.left == null
            return node.right
        else if node.right == null
            return node.left
        else
            sucessor = find_sucessor(node)
            node.key = sucessor.key
            node.right = delete(node.right, sucessor.key)
    return node

O processo de remoção pode também ser executado utilizando o antecessor (Algoritmo 8), porém, nesse caso, a segunda remoção deve ser realizada na árvore à direita. Note que, se a árvore permitir chaves repetidas, utilizar o antecessor garante que a árvore binária de pesquisa nunca entre em um estado inválido, e por isso, este método é o preferido neste caso.

Encontra o nó antecessor em uma BST

find_predecessor(node):
    node = node.left
    while node.right != null
        node = node.right
    return node

Além das formas tradicionais de percorrer uma árvore, as árvores binárias de pesquisa apresentam uma forma em ordem, que embora possa ser utilizada em qualquer árvore de grau par, faz mais sentido em uma BST, pois enumera todos os elementos da árvore na ordem definida pela chave de ordenação.

Percorrer os elementos em ordem

in_order_walk(node):
    in_order_walk(node.left)
    visit(node)
    in_order_walk(node.right)

Devido a possibilidade de degeneração da BST ao ter seus dados inseridos, se estes forem inseridos de forma ordenada, um dos problemas encontrados é como recriar a árvore, no mesmo formato que estava antes. Se a árvore for persistida, a partir de um percurso em níveis (busca em largura) (Algoritmo 10), ao ser recriada, os elementos serão inseridos de forma que a árvore fique com a mesma configuração anterior.

Percurso em níveis

level_order_walk(node):
    q = Queue()
    q.push(node)
    while not q.is_empty()
        n = q.pop()
        visit(n)
        for child in n.children:
            q.push(child)

Aplicações das Árvores Binárias de Pesquisa

Árvores Binárias de Pesquisa são estrutura muito eficientes para armazenamento e recuperação de dados, principalmente quando a árvore criada é uma árvore balanceada, e nesse caso, o custo de inserção, remoção e procura dos elementos se aproxima do caso médio $O(\lg N)$. Entre os principais uso estão a ordenação de dados, filas de prioridades, e a utilização como estrutura de armazenamento para arrays associativos ou conjuntos.

Para garantir essa eficiência, a árvore precisa estar balanceada, garantia que o modelo de BST apresentado aqui não possui, no entanto existem modelos de árvores binárias de pesquisa auto-balanceáveis, que garantem uma árvore próxima da ideal. Entre estes modelos encontramos as àrvores AVL e a Árvore Rubro-Negra, esta segunda muito utilizada por ter uma menor variação de eficiência nas operações.

Rotação de Árvores Binárias

A rotação de árvores binárias é uma operação da matemática discreta, que altera a estrutura da árvore, mantendo a ordem dos elementos. A rotação da árvore move um nó para cima na árvore e outro nó para baixo, e é, nomalmente, utilizada para diminuir a altura de sub-árvores maiores, enquanto aumenta o tamanho de sub-árvores menores, fazendo com que a árvore fique com um balanceamento melhor, melhorando assim a eficiência de algoritmos cujo custo é relacionado a altura da árvore. Embora seja uma operação aplicável a qualquer árvore binária, é muito utilizada em alguns modelos de árvores binárias de pesquisa para evitar a degeneração da árovre em uma lista encadeada, criando árvores auto-organizáveis.

Podemos rotacionar uma árvore binária para a direita ou para a esquerda, e aqui, considera-se a direção de rotação da árvore o lado da árvore que terá sua altura aumentada (Figura 3).

Rotação de Árvore Binária Rotação de árvore binária

Duas características importantes que devem ser destacadas são a invariância com relação a ordem dos elementos, e a reversibilidade das rotações. A rotação da árvore não altera a ordenação dos elementos, portanto, o percurso em ordem dos elementos, retorna o mesmo resultado, mesmo após a execução da rotação. Uma árvore rotacionada à direita, e após a rotação ser rotacionada (na nova raiz) à esquerda terá a mesma estrutura que apresentava antes das duas rotações.

Utilizando o exemplo da Figura 3, para executar a rotação à direita da àrvore com raiz em Q, e pivot para rotação em P, basta que o nó P passe a ser o nó pai do nó Q, para que se execute a rotação, no entanto, o nó B, que era um nó com chave maior que o nó P deve ser reposicionado para manter válida a propriedade das árvores binárias de pesquisa (chaves menores à esquerda, chaves maiores à direita), e por isso deve ser associado ao lado esquerdo da árvore, agora com raiz em P. Como B possuía uma chave menor que Q, pois estava a sua esquerda, pode ser associado como filho à esquerda de Q, uma vez que este não tem mais um filho à esquerda (que era P).

O algoritmo de rotação de árvores binárias possui custo constante ($O(1)$) e pode ser implementado como uma série de atribuições (Algoritmo 11). Nesta implementação (rotação à direita), a nova raiz da árvore é retornada ao chamador, o qual deve atualizar a sua referência para a sub-árvore.

Rotação de uma BST à direita

rotate_right(root):
    pivot = root.left
    root.left = pivot.right
    pivot.right = root
    return pivot

Aplicando o algoritmo de rotação à direita no nó raiz da árvore apresentada na Figura 1, obteremos a árvore da Figura 4, que apresenta um estrutura mais balanceada.

Árvore Binária de Pesquisa balanceada por rotação Árvore binária de pesquisa balanceada

A operação de rotação à esquerda (Algoritmo 12) é muito semelhante, porém invertem-se os lados em todo o algoritmo.

Rotação de uma BST à esquerda.

rotate_left(root):
    pivot = root.right
    root.right = pivot.left
    pivot.left = root
    return pivot

A principal aplicação da rotação de árvores é no balanceamento de árvores binárias de pesquisa, onde esta técnica é aplicada automaticamente para manter o equilíbrio da árvore, como na árvore AVL e na Árvore Rubro-Negra.