binary search tree - Java implementation of BST delete node -
i'm trying make method delete node in bst , not working..i'm using node class made myself.. tried debugging didnt on addressing error in code.
appreciate on how make work.
public boolean delete(node z) { if (z == null) return false; node x,y; if( z.getleft() == null || z.getright()== null) y = z; else { y = (node) successor(z); } if (y.getleft() != null) x = y.getleft(); else x = y.getright(); if(x != null) x.setparent(y.getparent()); if(y.getparent() == null) { this.node=x; } else if (y == y.getparent().getleft()) { y.getparent().setleft(x); } else y.getparent().setright(x); if(y==z) z.setkey(y.getkey()); return true; } public node treeminimum(node x) { while (x.getleft() != null) x = x.getleft(); return x; } public node successor(node node) { node x = node; if (x.getright() != null) return treeminimum(x.getright()); node y = x.getparent(); while (y != null && x == y.getright()) { x = y; y = y.getparent(); } return y; }
// here complete solution public void delete(final integer data) { root = delete(root, data); } public node<oinfo> delete(node<oinfo> node, final integer data) { if (node == null) { return null; } int cmp = data.compareto(new integer(node.getdata().data)); if (cmp < 0) { node.setleft(delete(node.getleft(), data)); } else if (cmp > 0) { node.setright(delete(node.getright(), data)); } else { boolean isroot = false; if (root == node) { isroot = true; } if (node.getleft() == null) { return node.getright(); } if (node.getright() == null) { return node.getleft(); } node<oinfo> t = node; node = findminimum(t.getright()); node.setright(deletemin(t.getright())); node.setleft(t.getleft()); if (isroot) { root = node; } } return node; } private node<oinfo> deletemin(node<oinfo> node) { if (node.getleft() == null) { return node.getright(); } node.setleft(deletemin(node.getleft())); return node; } private node<oinfo> findminimum(node<oinfo> node) { if (node == null) { throw new illegalargumentexception("null value of node provided."); } if (node.getleft() == null) { return node; } else { return findminimum(node.getleft()); } }
Comments
Post a Comment