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.
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.
- 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.
- 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.
- 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. :)
