Java Community | Help. Code. Learn.•2mo ago

Error in remove Node method in Java

public boolean removeNode(int key) throws Exception {
            AVLNode parent = null; AVLNode current = root; AVLNode newSubRoot = null;
            while (current != null) {
                int cmp = Integer.compare(current.key, key);
                if (cmp == 0) {
                    if (parent == null) {
                        root = removeBST(current);
                        if (root != null)
                            root.parent = null;
                    } else if (parent.left == current) {
                        newSubRoot = removeBST(current);
                        setLeft(parent, newSubRoot);
                    } else if (parent.right == current) {
                        newSubRoot = removeBST(current);
                        setRight(parent, newSubRoot);
                    } else throw new Exception();
                    if (restructureNodeOnRemove != null) {
                        updateHeights(restructureNodeOnRemove);
                        while (restructureNodeOnRemove != null) {
                            if (!isBalanced(restructureNodeOnRemove)) {
                                AVLNode z = restructureNodeOnRemove;
                                AVLNode y = (z.left != null && (z.right == null || z.left.height >= z.right.height)) ? z.left : z.right;
                                AVLNode x = (y.left != null && (y.right == null || y.left.height >= y.right.height)) ? y.left : y.right;
                                restructure(x, y, z);}
                            restructureNodeOnRemove = restructureNodeOnRemove.parent;
                            if(restructureNodeOnRemove!=null){updateHeights(restructureNodeOnRemove);
                            }}}
                    size--;
                    return true;
                }else{
 parent = current;
                    if(cmp > 0){
current = current.left;
                    }else{
current = current.right;
                    }}}
            return false;}

public boolean removeNode(int key) throws Exception {
            AVLNode parent = null; AVLNode current = root; AVLNode newSubRoot = null;
            while (current != null) {
                int cmp = Integer.compare(current.key, key);
                if (cmp == 0) {
                    if (parent == null) {
                        root = removeBST(current);
                        if (root != null)
                            root.parent = null;
                    } else if (parent.left == current) {
                        newSubRoot = removeBST(current);
                        setLeft(parent, newSubRoot);
                    } else if (parent.right == current) {
                        newSubRoot = removeBST(current);
                        setRight(parent, newSubRoot);
                    } else throw new Exception();
                    if (restructureNodeOnRemove != null) {
                        updateHeights(restructureNodeOnRemove);
                        while (restructureNodeOnRemove != null) {
                            if (!isBalanced(restructureNodeOnRemove)) {
                                AVLNode z = restructureNodeOnRemove;
                                AVLNode y = (z.left != null && (z.right == null || z.left.height >= z.right.height)) ? z.left : z.right;
                                AVLNode x = (y.left != null && (y.right == null || y.left.height >= y.right.height)) ? y.left : y.right;
                                restructure(x, y, z);}
                            restructureNodeOnRemove = restructureNodeOnRemove.parent;
                            if(restructureNodeOnRemove!=null){updateHeights(restructureNodeOnRemove);
                            }}}
                    size--;
                    return true;
                }else{
 parent = current;
                    if(cmp > 0){
current = current.left;
                    }else{
current = current.right;
                    }}}
            return false;}

3 Replies

JavaBot•2mo ago

⌛ This post has been reserved for your question.

Hey @john! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically marked as dormant after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

johnOP•2mo ago

Hallo, believe in this method I have a error

AVLNode y = (z.left != null && (z.right == null || z.left.height >= z.right.height)) ? z.left : z.right;
AVLNode x = (y.left != null && (y.right == null || y.left.height >= y.right.height)) ? y.left : y.right;

do this two lines correspond to: Put y on child of z with greatest height Put x on child of y with greatest height If both heights are the same, decide for the single-rotation case! Or I am doing it wrong? the method is responsible for removing a node in AVL tree, methods removeBST() do the remove in binary search tree, restructure does the linking and rotation, and updateHeight, just recusively updates the heights of each node Help would be appreciated The method works in most of the time, but in certain combinations of tree strucutre, gives an unbalanced tree as output This is an example My code fails only in edge cases

JavaBot•2mo ago

💤 Post marked as dormant

This post has been inactive for over 300 minutes, thus, it has been archived. If your question was not answered yet, feel free to re-open this post or create a new one. In case your post is not getting any attention, you can try to use /help ping. Warning: abusing this will result in moderative actions taken against you.

💤 Post marked as dormant

This post has been inactive for over 300 minutes, thus, it has been archived. If your question was not answered yet, feel free to re-open this post or create a new one. In case your post is not getting any attention, you can try to use /help ping. Warning: abusing this will result in moderative actions taken against you.

Gaming

Programming

Error in remove Node method in Java