es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • ¿Qué está mal con mi método insert() en mi implementación de Árbol de Búsqueda Binaria?

¿Qué está mal con mi método insert() en mi implementación de Árbol de Búsqueda Binaria?

15 Jun, 2023 Programación

Intenté crear un método recursivo para insertar un elemento en mi árbol de búsqueda binario; sin embargo, no puedo encontrar el error en mi código (sospecho que tiene algo que ver con las referencias).

public class BST<E extends Comparable<E>> {

    private class BSTNode implements Comparable<BSTNode> {

        public E data;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(E data) {
            this.data = data;
        }

        @Override
        public int compareTo(BSTNode o) {
            return this.data.compareTo(o.data);
        }
    }

    public BSTNode root;

    public void insert(E data) {
        insertRec(root, new BSTNode(data));
    }

    private void insertRec(BSTNode current, BSTNode newNode) {
        if (current == null) {
            current = newNode;
            return;
        }
        if (current.compareTo(newNode) > 0) {
            insertRec(current.right, newNode);
        }
        else if (current.compareTo(newNode) < 0) {
            insertRec(current.left, newNode);
        }
    }
}
Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    El problema con el método insertRec en este código es que las asignaciones realizadas a current no actualizan la referencia al nodo padre fuera del método. Cuando current se establece en null o en newNode, solo cambia la referencia de parámetro dentro del alcance del método, no la referencia mantenida por el nodo padre o cualquier otra referencia a él.

    Para solucionar este problema, el método insertRec debe devolver el nodo actualizado después de la llamada recursiva, para que el nodo padre pueda actualizar su referencia a ese nodo. El método actualizado insertRec podría verse así:

    private BSTNode insertRec(BSTNode current, BSTNode newNode) {
    if (current == null) {
        return newNode;
    }
    if (current.compareTo(newNode) > 0) {
        current.right = insertRec(current.right, newNode);
    } else if (current.compareTo(newNode) < 0) {
        current.left = insertRec(current.left, newNode);
    }
    return current;
}

    En este método actualizado, la referencia del nodo padre se actualiza con el valor devuelto después de cada llamada recursiva. El nodo de inicio se devuelve cuando no es necesario realizar más cambios.

Comments are closed.