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