Tried to implement a method to remove a vertex from a binary tree. The problem is that when I want to remove the root of the tree it is not deleted, tell me where the error is.

private static Node delete(Node n, int x) { if(n == null) return n; if (x > nx) nr = delete(nr, x); else if (x < nx) nl = delete(nl, x); else if (nr != null && nl != null) { nx = nrminimum().x; nr = delete(nr, nrx); } else { if (nr != null) n = nr; else n = nl; } return n; } public void remove(int x){ delete(this, x); }
  • one
    Node.remove is useless in this form. Suppose you only have a root vertex with a value of 5, you call корень.remove(5) , the method calls delete(this, 5) , which honestly returns null ( корень.l ), which is not used at all. You can create a class Tree , which will have a root field, and a method remove(int x) { root = delete(root, x); } remove(int x) { root = delete(root, x); } . - zRrr
  • remove works when I take a non-root, when I take a root, the debugger shows all the rules, but in the very answer I get the same link - Youlfey
  • @Artem, if the question is no longer relevant for you, then select the answer that you think was the most comprehensive (check mark to the left of the answer) and then the question can be considered closed. would reveal the essence of your question. - diofloyk

2 answers 2

In the book "Algorithms construction and analysis" Thomas Kormen. An algorithm for removing a node from a binary search tree is analyzed.

The deletion procedure is divided into two subroutines, which are pseudocode. First: enter image description here

And the second:

enter image description here

Where T is the link to your tree, z is the link to the node you want to delete. I guess, knowing this algorithm, it’s easy for you to write its implementation.

    Need string

     nr = delete(nr, nrx);

    replaced by

     nr = delete(nr, nx);

    because otherwise you delete not the desired, but the node on the right.