Implementación del Método Add para BST
Estoy tratando de implementar un método de inserción en un árbol de búsqueda binario pero he encontrado algunos problemas. Dado el código circundante:
public class BinarySearchTree<e> {
private BinaryNode<e> root;
private int size;
private Comparator<e> comparator;
/**
* Construye un árbol de búsqueda binario vacío, ordenado según el comparador especificado.
*/
public BinarySearchTree(Comparator<e> comparator) {
root = null;
size = 0;
this.comparator = comparator;
}
private static class BinaryNode<e> {
private E element;
private BinaryNode<e> left;
private BinaryNode<e> right;
private BinaryNode(E element) {
this.element = element;
left = right = null;
}
}
//Otros métodos
}
qué está mal en mi implementación:
/**
* Inserta el elemento especificado en el árbol si no existe un duplicado.
* @param x elemento a insertar
* @return true si el elemento fue insertado
*/
public boolean add(E x) {
return add(root, x);
}
private boolean add(BinaryNode<e> n, E x) {
if(n == null) {
n = new BinaryNode<e> (x);
size++;
return true;
}
int compResult = comparator.compare(x, n.element);
if(compResult<0){
return add(n.left, x);
} else if(compResult>0) {
return add(n.right, x);
}else {
return false;
}
}
Al probar insertar solo un elemento, obtengo null como valor de retorno de la raíz, pero realmente no puedo ver qué está saliendo mal. ¡Gracias por la ayuda!
davy.ai
Parece que el problema está con el método
add
. El métodoadd
debería actualizar el nodoroot
cuando se agrega un nuevo elemento, pero no lo está haciendo. El métodoadd
debería actualizarse para incluir una línea que establezcaroot
en el nuevo nodo cuando se crea. Esto debería verse algo así: