Árvore binária de pesquisa

Instruções

Insere e procura números numa árvore binária.

Quando precisamos de representar dados ordenados, um array não é uma boa estrutura de dados.

Digamos que temos o array [1, 3, 4, 5] e lhe acrescentamos o 2, passando a ser [1, 3, 4, 5, 2]. Agora temos de voltar a ordenar o array todo! Podemos melhorar isto se percebermos que só precisamos de arranjar espaço para o novo item [1, nil, 3, 4, 5] e depois colocar o item no espaço que arranjámos. Mas isto continua a obrigar-nos a deslocar muitos elementos uma posição.

As árvores de pesquisa binária, no entanto, conseguem operar sobre dados ordenados de forma muito mais eficiente.

Uma árvore de pesquisa binária é composta por uma série de nós ligados entre si. Cada nó contém um dado (por exemplo, o número 3), uma variável chamada left e uma variável chamada right. As variáveis left e right apontam para nil ou para outros nós. Como esses outros nós têm, por sua vez, outros nós por baixo deles, dizemos que as variáveis left e right apontam para subárvores. Todos os dados na subárvore esquerda são menores ou iguais aos dados do nó atual, e todos os dados na subárvore direita são maiores do que os dados do nó atual.

Por exemplo, se tivéssemos um nó com o dado 4 e acrescentássemos o dado 2, a nossa árvore ficaria assim:

      4
     /
    2

Se acrescentássemos depois o 6, ficaria assim:

      4
     / \
    2   6

Se depois acrescentássemos o 3, ficaria assim

       4
     /   \
    2     6
     \
      3

E se depois acrescentássemos o 1, o 5 e o 7, ficaria assim

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

Créditos

As imagens foram criadas por habere-et-dispertire com PGF/TikZ de Till Tantau.

Implementação

Implementar uma estrutura de árvore eficiente e modificável em Cairo (ou em qualquer linguagem puramente funcional com memória imutável) é um desafio, porque estas linguagens foram concebidas para evitar alterar os dados depois de serem criados. Essa imutabilidade significa que, em vez de atualizares um nó da árvore diretamente, tens de criar uma nova versão da árvore sempre que a modificas.

Para mostrar porque é que isto acontece, imagina uma estrutura de árvore binária simples, em que cada nó tem um filho esquerdo e um filho direito. Digamos que começamos com uma árvore pequena como esta:

       1
      / \
     2   3

Agora, suponhamos que queremos adicionar um novo nó 4 como filho esquerdo do nó 2. Numa linguagem puramente funcional (como em Cairo ou Haskell), a memória é imutável, por isso não podemos simplesmente adicionar o nó 4 diretamente ao 2. Em vez disso, temos de criar uma nova versão de cada nó ao longo do caminho da raiz até ao nó modificado, porque cada nó ao longo desse caminho passa a apontar para uma subárvore nova ou modificada.

Eis como seria o processo:

1. Adicionar o nó 4 ao nó 2:

   • Cria uma nova versão do nó 2, que agora tem 4 como filho esquerdo.

       2'
      / 
     4   
   

2. Atualizar o nó raiz:

   • Como o nó 1 apontava originalmente para o antigo 2, criamos uma nova versão do nó raiz 1', que agora aponta para o nó atualizado 2' à esquerda e mantém o nó 3 à direita.

       1'
      / \
     2'  3
   

Assim, a árvore resultante fica:

       1'
      / \
     2'  3
    /
   4

Esta nova árvore (1') continua a assemelhar-se à original, mas com um caminho atualizado. O ponto essencial é que tivemos de recriar cada nó ao longo do caminho (1 a 2) para preservar a imutabilidade, já que os nós existentes não podem ser modificados no próprio local. A árvore original continua a existir (por exemplo, para todas as referências à sua raiz original 1), enquanto esta nova árvore representa o estado modificado.

Em árvores grandes, esta abordagem pode tornar-se dispendiosa, pois cada nova modificação obriga a recriar um caminho de nós desde a raiz até ao nó atualizado, mesmo que apenas uma pequena parte da árvore seja realmente alterada.