Á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 depois colocar o item no espaço que abrimos. Mas isso ainda exige que movamos muitos elementos uma posição.

As árvores binárias de busca, no entanto, 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 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, 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