delete node in a binary search tree

Question

delete node in a binary search tree

Navigation

#1 by (2 votes)

1

I'm trying to make a method that removes a node from a binary search tree recursively but the code I have leaves everything as exactly the same.

public void borrar (Node nodo, int n){ // recibe el nodo raiz
   if (nodo == null){ // si el nodo es null no hace nada mas
     return;
    }
   else if (nodo.data==n){ // se mira si el dato del nodo es el que se quiere borrar
      if (nodo.left == null && nodo.right == null){ // si el nodo es una hoja simplemente se elimina
         nodo = null;
         return;
        }
      else if (nodo.left != null && nodo.right == null){// si el nodo solo tiene un hijo izquierdo el nodo se hace igual a ese hijo izquierdo
         nodo = nodo.left;                             
         return;
        }
      else if (nodo.left == null && nodo.right != null){// si el nodo solo tiene un hijo derecho el nodo se hace igual a ese hijo derecho
         nodo = nodo.right;
         return;
        }
      else { // si el nodo tiene dos hijos, como el ultimo elemento de la raiz izquierda siempre es menor al primer de la raiz derecha
         Node a = nodo.right; // el nodo pasa a ser la raiz izq y se pone esa raiz derecha como hija der de ese mismo nodo
         nodo = nodo.left;
         Node aux = nodo;
         while (true){
             if (nodo.right!=null){
                aux = a.right;
                }
             else {
                aux.right = a;
                break;
                }
            }
            return;
        }
    }

   if (n<nodo.data){ // recursion si el numero buscado es menor al que esta en el nodo actual se invoca a si mismo con el hijo izq
     borrar (nodo.left,n);
    }
   else { 
     borrar (nodo.right,n);// en cambio si es mayor o igual se invoca a si mismo con el hijo der 
    }
}

java

asked by Eduard Damiam 11.10.2017 в 03:34

source

1 answer

Save HTML tags on sql server and read them Google Font does not work in external CSS

score 2 · Accepted Answer

The problem is that you do not delete the node. By putting the variable to null you are simply losing the reference to the node to be deleted, but the node is still in the tree: imagine that you have a node-type variable that is the root of a tree with two children:

Nodo raiz= ...; //dos hijos

If I create a new variable that points to the root:

Nodo aux=raiz;

I have two references (variables) pointing to the same object.

If now I put null any of them:

raiz=null;

The tree will continue to exist in the other. Therefore, if you want to delete a node, what you have to do is delete all the references so that the garbage reolector gets rid of that node. Imagine that we want to remove the left node, what you have to do is:

//Hemos pasado el nodo árbol a nuestro método como el parámetro "nodo"
if (nodo.left!=null && nodo.left.data==n) { // encontramos el elemento a borrar
  Nodo aux=nodo.left;
  // código para recolocar los nodos hijos del que vamos a borrar...
  //supongamos que tiene un único hijo:
  nodo.left=aux.left;
  return; //salimos, el nodo original ya no está en el árbol y aux será borrada al salir del método
}