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