Á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.

Imaginemos que temos o array [1, 3, 4, 5] e lhe acrescentamos o 2, passando ele 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 elemento [1, nil, 3, 4, 5] e de o colocar no espaço que criámos. Mas mesmo assim continuamos a ter de deslocar muitos elementos uma posição para baixo.

As árvores binárias de pesquisa, no entanto, conseguem trabalhar com dados ordenados de forma muito mais eficiente.

Uma árvore binária de pesquisa consiste numa 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 da subárvore esquerda são menores ou iguais aos dados do nó atual, e todos os dados da subárvore direita são maiores do que os dados do nó atual.

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

  4
 /
2

Se depois acrescentássemos 6, ficaria assim:

  4
 / \
2   6

Se depois acrescentássemos 3, ficaria assim

   4
 /   \
2     6
 \
  3

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

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