Á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, que passa a ser [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 depois colocar 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 é composta 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 aos dados do nó atual, e todos os dados na subárvore da direita são maiores que os dados 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, ficaria assim:

      4
     / \
    2   6

Se depois adicionássemos 3, ficaria assim

       4
     /   \
    2     6
     \
      3

E se depois adicionássemos 1, 5 e 7, 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.