Árvore Binária de Busca - Método para inserção (java)

No post anterior expliquei alguns dos principais conceitos sobre as Árvores Binárias de Busca, e também mostrei como realizar a busca por um elemento. Neste post vamos ver como pode ser feita a inserção de novos nós.

O método inserir (insert)

A inserção de um novo nó pressupõe a busca pelo local no qual devemos colocá-lo. Sendo assim, o método insert deve se parecer bastante com o método search. A seguir colocarei a minha implementação, que dividi em duas partes, e em seguida explicarei melhor cada uma delas.

public void insert(int newKey){
  if(this.root == null){
   this.root = new Node(newKey);
   this.root.parent = null;
  }
  else
   insertHelper(this.root, newKey);   
}

O método insert descrito acima é bastante simples, recebe apenas a chave a ser inserida como parâmetro e retorna void (não retorna nada). Na verdade este método só cobre o caso da árvore vazia, ou seja, o nó raiz(root) é nulo. Caso a árvore não esteja vazia, ele chamará um método auxiliar para realizar a inserção, passando a chave a ser inserida e o nó raiz da árvore.

Segue o código do método auxiliar.

private void insertHelper(Node node, int newKey){
  if(newKey < node.key){
   if(node.left == null){
    node.left = new Node(newKey);
    node.left.parent = node;
   }
   else
    insertHelper(node.left, newKey);
  }
  else if(newKey > node.key){
   if(node.right == null){
    node.right = new Node(newKey);
    node.right.parent = node;
   }
   else
    insertHelper(node.right, newKey);
  }
  else
   return;
}

Note que existe um "private" na assinatura do método insertHelper, este modificador de acesso é usado para garantir que nenhum objeto fora da classe BST possa utilizar insertHelper. Assim temos a segurança de que ninguém pode inserir novos nós em nossa árvore utilizando o método insertHelper. É importante observar que o método insert, porém, é público, pois ele recebe apenas a chave que vai ser inserida e não pode inserir essa chave em outra árvore que não seja a árvore que o invocou. InsertHelper, por outro lado, poderia receber um nó de qualquer árvore como atributo!

Temos uma chave a ser inserida e um nó, já sabemos como funciona uma ABB, então vamos separar a explicação do algoritmo por casos.

1. A nova chave (newKey) é menor do que a chave presente no nó:
• Como newKey é menor do que node.key, temos que seguir pela subárvore à esquerda.
• Então verificamos se node.left é nulo.
• Se node.left é nulo, sabemos que newKey deve ser o filho esquerdo de node (linhas 4,5).
• O próximo comando informa que node é o pai (parent) de node.left (nó recém criado).
• Se node.left não for nulo, significa que node já tem filho esquerdo, então temos que analisá-lo. Isto será feito chamando novamente o método insertHelper, passando como parâmetro newKey e o filho esquerdo de node.
2. A nova chave (newKey) é maior do que a chave presente no nó:
• Como newKey é maior do que node.key, temos que seguir pela subárvore à direita.
• Então verificamos se node.right é nulo.
• Se node.right é nulo, sabemos que newKey deve ser o filho direito de node (linhas 12,13).
• O próximo comando informa que node é o pai (parent) de node.right (nó recém criado).
• Se node.right não for nulo, significa que node já tem filho direito, então temos que analisá-lo. Isto será feito chamando novamente o método insertHelper, passando como parâmetro newKey e o filho direito de node.
3. Nenhum dos casos anteriores foi verdadeiro:
• Se atingirmos o else, obviamente, encontramos um nó com chave igual a newKey.
• Visto que a chave já está presente na árvore, podemos simplesmente retornar.

O próximo post será sobre algoritmos para percorrimento em árvores!

Qualquer crítica ou sugestão, por favor, postem nos comentários. Assim posso melhorar o texto. :)