Árvore binária de busca

Instruções

Insira e busque números em uma árvore binária.

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

Digamos que temos o array [1, 3, 4, 5] e adicionamos 2 a ele, de modo que ele vira [1, 3, 4, 5, 2]. Agora precisamos ordenar o array inteiro de novo! Podemos melhorar isso percebendo que só precisamos abrir espaço para o novo item [1, nil, 3, 4, 5] e então inserir o item no espaço que abrimos. Mas isso ainda exige deslocar muitos elementos uma posição para baixo.

As árvores binárias de busca, porém, conseguem operar sobre dados ordenados de forma muito mais eficiente.

Uma árvore binária de busca é formada por uma série de nós conectados. 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, por sua vez, têm outros nós abaixo deles, dizemos que as variáveis left e right apontam para subárvores. Todos os dados na subárvore da esquerda são menores ou iguais ao dado do nó atual, e todos os dados na subárvore da direita são maiores que o dado do nó atual.

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

      4
     /
    2

Se depois adicionássemos 6, ela ficaria assim:

      4
     / \
    2   6

Se depois adicionássemos 3, ela ficaria assim

       4
     /   \
    2     6
     \
      3

E se depois adicionássemos 1, 5 e 7, ela ficaria assim

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

Créditos

As imagens foram criadas por habere-et-dispertire usando 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) é desafiador, porque essas linguagens são projetadas para evitar alterar os dados depois de criados. Essa imutabilidade significa que, em vez de atualizar um nó da árvore diretamente, é preciso criar uma nova versão da árvore sempre que você a modificar.

Para mostrar por que isso acontece, imagine uma estrutura simples de árvore binária em que cada nó tem um filho à esquerda e um à direita. Digamos que comecemos com uma árvore pequena assim:

       1
      / \
     2   3

Agora, suponha que queiramos adicionar um novo nó 4 como filho à esquerda do nó 2. Em uma linguagem puramente funcional (como Cairo ou Haskell), a memória é imutável, então não podemos simplesmente adicionar o nó 4 diretamente ao 2. Em vez disso, temos que criar uma nova versão de cada nó ao longo do caminho da raiz até o nó modificado, porque cada nó nesse caminho agora aponta para uma subárvore nova ou modificada.

Veja como esse processo ficaria:

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

   • Crie uma nova versão do nó 2, que agora tem 4 como filho à esquerda.

       2'
      / 
     4   
   

2. Atualize o nó raiz:

   • Como o nó 1 originalmente apontava para o 2 antigo, 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

Essa nova árvore (1') ainda se parece com a original, mas com um caminho atualizado. O ponto principal é que tivemos que recriar cada nó ao longo do caminho (1 até 2) para preservar a imutabilidade, já que nós existentes não podem ser modificados no lugar. A árvore original continua existindo (por exemplo, para todas as referências à sua raiz original 1), enquanto essa nova árvore representa o estado modificado.

Em árvores grandes, essa abordagem pode ficar cara, pois cada nova modificação exige recriar um caminho de nós da raiz até o nó atualizado, mesmo que só uma pequena parte da árvore realmente mude.