Java Community | Help. Code. Learn.•7d ago

AVL trees

I have a error in a Java AVL tree implementation. I'm not finding the error, its should be something about restructuring of the tree. Any help would be appreciated.

112 Replies

JavaBot•7d 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.

dan1st•6d ago

We can't help you without the relevant code or and you telling us what exactly happens

johnOP•6d ago

https://sourceb.in/IJ2oH6ZJjI

SourceBin

AVLTree.java

Instantly share your code with the world.

johnOP•6d ago

This is my full code of the java class. The problem is that the code actually runs but I dont get the expected output. The tree doesnt updates the heights as I can see Root of the tree: key:5, value: 5.0->0 Left key:2, value: 2.0->0 Right key:18, value: 18.0, ->0 key:8, value: 8.0->0 key:14, value: 14.0->0 as you can see for inserts: main.insertNode(5);main.insertNode(18); main.insertNode(2); main.insertNode(8); main.insertNode(14); I get a tree that is not balanced and also the heights are not updated Can the error be at insert method, or is in the updateHeight method @dan1st sorry for the ping! But I am really confused about my work as I am standing many hours and I can't see my mistake. Any help appreciated! I should notice also that I am a beginner and maybe some mistakes for me are a but hard to see

dan1st•6d ago

Do you know what a debugger is? In your insertNode method, you are calling updateHeights(n) after inserting the node somewhere but that only updates the height of the root node you need to update the heights of the relevant children first For example you could call updateHeight() on the parent when calling setLeft() and setRight() ad when restructuring, you also need to continue updating the heights of the parents if you change a node, you need to update the height of that node and all its (transitive) parents

johnOP•6d ago

doesnt that do the updateHeight() method itself it is a recursive call there for the node parent

john•6d ago

if (current.height != oldHeight && current.parent != null) {
            updateHeights(current.parent);
}

if (current.height != oldHeight && current.parent != null) {
            updateHeights(current.parent);
}

This message has been formatted automatically. You can disable this using /preferences.

dan1st•6d ago

ah right I didn't see that . Can you step through the insertNode method with a debugger until you reach the updateHeights(n) call and check what happens there?

johnOP•6d ago

I changed it and added a update height after each insert

dan1st•6d ago

Does that change anything?

john•6d ago

public boolean insertNode(int key, float value) throws IllegalArgumentException {
        if(value < 0  || findByKey(key) != -1f) {
            //returning false if node has a key that already exists or value is < 0
            return false;
        }
        AVLNode newNode;
        if (root == null){
                root = new AVLNode(key, value);
                updateHeights(root);
                size++;
                return true;
        }else {
            AVLNode current = root;
            while (true) {
                    int cmp = Integer.compare(current.key, key);
                    if (cmp == 0)
                        return false;
                    else if (cmp < 0) {
                        if (current.right != null)
                            current = current.right;
                        else {
                            newNode = new AVLNode(key, value);
                            setRight(current,newNode);
                            updateHeights(newNode);
                            size++;
                            break;
                        }
                    } else {
                        if (current.left != null)
                            current = current.left;
                        else {
                            newNode = new AVLNode(key, value);
                            setLeft(current, newNode);                 updateHeights(newNode);
                            size++;
                            break;
                        }}}}
        AVLNode n = newNode;

        while (n != null) {
            AVLNode x = n;
            if (x.parent != null && x.parent.parent != null && !isBalanced(x.parent.parent)) {
                AVLNode z = x.parent.parent;
                AVLNode y = x.parent;
                restructure(x, y, z);
                updateHeights(n);
            }else {
                n = n.parent;
            }
        }
        return true;
    }

public boolean insertNode(int key, float value) throws IllegalArgumentException {
        if(value < 0  || findByKey(key) != -1f) {
            //returning false if node has a key that already exists or value is < 0
            return false;
        }
        AVLNode newNode;
        if (root == null){
                root = new AVLNode(key, value);
                updateHeights(root);
                size++;
                return true;
        }else {
            AVLNode current = root;
            while (true) {
                    int cmp = Integer.compare(current.key, key);
                    if (cmp == 0)
                        return false;
                    else if (cmp < 0) {
                        if (current.right != null)
                            current = current.right;
                        else {
                            newNode = new AVLNode(key, value);
                            setRight(current,newNode);
                            updateHeights(newNode);
                            size++;
                            break;
                        }
                    } else {
                        if (current.left != null)
                            current = current.left;
                        else {
                            newNode = new AVLNode(key, value);
                            setLeft(current, newNode);                 updateHeights(newNode);
                            size++;
                            break;
                        }}}}
        AVLNode n = newNode;

        while (n != null) {
            AVLNode x = n;
            if (x.parent != null && x.parent.parent != null && !isBalanced(x.parent.parent)) {
                AVLNode z = x.parent.parent;
                AVLNode y = x.parent;
                restructure(x, y, z);
                updateHeights(n);
            }else {
                n = n.parent;
            }
        }
        return true;
    }

This message has been formatted automatically. You can disable this using /preferences.

johnOP•6d ago

I did it so Tried to debug but I dont see the problem again

dan1st•6d ago

Does that mean it worked or does it mean it didn't work?

johnOP•6d ago

no it didn't work

johnOP•6d ago

see for ex

dan1st•6d ago

Can you try the previous part and show e what the debugger shows you at the updateHeights(n) call?

johnOP•6d ago

you mean so?

dan1st•6d ago

ohhhhh so the new height of the inerted node will always be 0 because the new node has no children (and it is 0 at the beginning) so the if (current.height != oldHeight && current.parent != null) { is false because urrent.height == oldHeight try changing the updateHeights(n) to updateHeights(n.parent) (but it should work with the old code as well)

johnOP•6d ago

updateHeights(n.parent) if I do that I get a stackoverflow at updateHeights

johnOP•6d ago

dan1st•6d ago

I think you might have a node that is its own parent somewhere Can you check that in the debugger? I think the issue is in the restructure you do g.a.parent = g.b; and g.c.parent = g.b; That can overwrite z.parent, right? because a or c could be z

johnOP•6d ago

actually z is b

dan1st•6d ago

normally it could be anything

johnOP•6d ago

I mean after rotation at the beginning yes

dan1st•6d ago

for example where I marked it, it's y

dan1st•6d ago

yes but the rotation isn't finished there z still refers to the old z Java doesn't magically set z to the new parent

johnOP•6d ago

yeah I see

dan1st•6d ago

z stays the old parent so these can overwrite z.parent and then you do g.b.parent = z.parent; later whereas you lost the information what z.parent actually was you could just move the g.b.parent = z.parent; up before the other statements

johnOP•6d ago

No no wait I am messing things up. The getComponents method is pre-done and its right I have nothing to do with it There is no mistake there

dan1st•6d ago

there is literally

dan1st•6d ago

that part can overwrite z.parent

dan1st•6d ago

so you need that code and move it before it

johnOP•6d ago

now its a bit better I think some tree test works and some not

dan1st•6d ago

I can't tell you with that information give me a minimal reproducible example What exactly happens (not just the output but I need to know what exactly happens)?

johnOP•6d ago

insertNode(5); insertNode(18); insertNode(2); insertNode(8); insertNode(14); insertNode(16); insertNode(13); insertNode(3); insertNode(12); if I do these inserts. I get an error:

dan1st•6d ago

print the whole tree after every insertion and check whether everything matches your expection which you get when drawing it by hand

johnOP•6d ago

I should be again something in the restructure method I guess

john•6d ago

public void restructure(AVLNode x, AVLNode y, AVLNode z){
        NodeGroup g = getComponents(x,y,z);
        //Getting a NodeGroup object g that for x,y,z returns a,b,c node and subtrees t0,t1,t2 and t3
        g.b.left = g.a;
        g.b.right = g.c;

        g.a.left = g.t0;
        g.a.right = g.t1;

        g.c.left = g.t2;
        g.c.right = g.t3;

        if (z.parent != null) {
            if (z.parent.left == z) {
                z.parent.left = g.b;
            } else {
                z.parent.right = g.b;
            }
        } else {
            root = g.b;
        }
        g.b.parent = z.parent;

        g.a.parent = g.b;
        g.c.parent = g.b;



        updateHeights(g.a);
        updateHeights(g.c);
        updateHeights(g.b);
    }

public void restructure(AVLNode x, AVLNode y, AVLNode z){
        NodeGroup g = getComponents(x,y,z);
        //Getting a NodeGroup object g that for x,y,z returns a,b,c node and subtrees t0,t1,t2 and t3
        g.b.left = g.a;
        g.b.right = g.c;

        g.a.left = g.t0;
        g.a.right = g.t1;

        g.c.left = g.t2;
        g.c.right = g.t3;

        if (z.parent != null) {
            if (z.parent.left == z) {
                z.parent.left = g.b;
            } else {
                z.parent.right = g.b;
            }
        } else {
            root = g.b;
        }
        g.b.parent = z.parent;

        g.a.parent = g.b;
        g.c.parent = g.b;



        updateHeights(g.a);
        updateHeights(g.c);
        updateHeights(g.b);
    }

This message has been formatted automatically. You can disable this using /preferences.

johnOP•6d ago

i just changed the code position there is this what you meant

dan1st•6d ago

. yes, that's fine but first you need to find out which insert causes the issue by doing this

johnOP•6d ago

insertNode(12); causes the mistake

dan1st•6d ago

What's the tree before, what you expect it to be after the operation and what is it actually after the operation?

johnOP•6d ago

assertEquals(root.left.right.key, 12, strError); it should be root.left.right as the test says

dan1st•6d ago

. I don't want to see the asserts I want to see the full trees the one you have before (that matches your expectation as you said), the one you expect after inserting it and the one you actually get after inserting it

johnOP•6d ago

ok. I am trying that

johnOP•6d ago

so this is the state until inserts work: insertNode(5); insertNode(18); insertNode(2); insertNode(8); insertNode(14); insertNode(16); insertNode(13); insertNode(3);

johnOP•6d ago

this is what I expect after adding node 12

johnOP•6d ago

and here node 12 fails to be left-right node

dan1st•6d ago

Did you check whether it's actually that tree? and what is the exact actual tree?

johnOP•6d ago

Node key: 14 -> Height: 3 -> Level: 0 -> Position: Root Node key: 5 -> Height: 2 -> Level: 1 -> Position: Left Node key: 2 -> Height: 1 -> Level: 2 -> Position: Left Node key: 3 -> Height: 0 -> Level: 3 -> Position: Right Node key: 8 -> Height: 0 -> Level: 2 -> Position: Right Node key: 12 -> Height: 1 -> Level: 1 -> Position: Right Node key: 8 -> Height: 0 -> Level: 2 -> Position: Left Node key: 13 -> Height: 0 -> Level: 2 -> Position: Right this is what I get here the heights are -1 from that of the image but thats no problem

dan1st•6d ago

so node 8 is there twice?

johnOP•6d ago

yeah 8 twice and 18 doesnt appear

dan1st•6d ago

Is 18 in the tree before inserting 12?

johnOP•6d ago

Node key: 14 -> Height: 3 -> Level: 0 -> Position: Root Node key: 5 -> Height: 2 -> Level: 1 -> Position: Left Node key: 2 -> Height: 1 -> Level: 2 -> Position: Left Node key: 3 -> Height: 0 -> Level: 3 -> Position: Right Node key: 8 -> Height: 1 -> Level: 2 -> Position: Right Node key: 13 -> Height: 0 -> Level: 3 -> Position: Right Node key: 18 -> Height: 1 -> Level: 1 -> Position: Right Node key: 16 -> Height: 0 -> Level: 2 -> Position: Left yes

dan1st•6d ago

and 16 is gone as well there Can you show the actual tree before restructuring?

johnOP•6d ago

dan1st•6d ago

Why that? How does it get to that from there?

johnOP•6d ago

so here i did just the binary search tree thats wrong

dan1st•6d ago

btw here you aren't updating g.t0.parent, g.t1.parent, g.t2.parent and g.t3.parent

dan1st•6d ago

idk why it would look like that Is this intentional? If so, why?

johnOP•6d ago

I tried to follow this structure

dan1st•6d ago

yes ik but you still need to update t0.parent etc (you can also use the setRight and setLeft methods for these things)

johnOP•6d ago

setLeft(g.a,g.t0); setRight(g.a,g.t1); setLeft(g.c,g.t2); setRight(g.c,g.t3); did it so and inserts now work

dan1st•6d ago

nice

johnOP•6d ago

yeah, thanks. Now my next challenge is remove

JavaBot•6d ago

If you are finished with your post, please close it. If you are not, please ignore this message. Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.

johnOP•6d ago

Could you help me once more(last time). I don’t want to annoy you just I really try but I don’t know how to correct it. Insert seems to work very good now but I have a last problem with remove, it works but I get this problem: org.opentest4j.AssertionFailedError: .getTreeHeight() is wrong after removing node with key 14 from the following AVL tree:
5
/ \
2 14
/ \ / \
1 3 12 18
/ / \ / \
0 8 13 16 21

==> Expected :3 Actual :2 So this means the height is not updated correctly evertime, mostly yes. My updated code is this:https://srcb.in/5bIW3NbSjM If you can give it a look would be great. Thanks and sorry, I know its not your work to do this.

SourceBin

AVLTree2.java

Instantly share your code with the world.

dan1st•6d ago

Does removing the element give you the right tree (ignoring the heights)?

johnOP•6d ago

I think the problem is the height Tree before remove:
13
/ \
8 16
/ \ \
2 10 19
/ \ \
1 6 12

Tree after remove:
10
/ \
8 13
/ / \
2 12 16
/ \
1 6

==> Expected :true Actual :false this is a example where the error happens

dan1st•6d ago

you have updateHeights(restructureNodeOnRemove); you might also need updateHeights(restructureNodeOnRemove); that doesn't match the output from before

johnOP•6d ago

I didnt get that what did you mean here?

dan1st•6d ago

my fault you have that in your code

johnOP•6d ago

yes

dan1st•6d ago

you might also need updateHeights(restructureNodeOnRemove.parent); I forgot the .parent there because removeBST might give you the child node of the removed node

johnOP•6d ago

yeah but i think again the updateHeights make the update for all the tree

dan1st•6d ago

only if updateHeights actually changes the heights it stops as soon as there is no change and in that case, the children of that don't change so the height of that node doesn't change - but its parent node changed so you need to update the height of the parent

johnOP•6d ago

you mean so

johnOP•6d ago

I did that but no success

johnOP•6d ago

these are the jUnit tests I have

johnOP•6d ago

after I added the (...parent) thing I get org.opentest4j.AssertionFailedError: .removeNode() raised an exception: java.lang.NullPointerException: Cannot read field "height" because "current" is null But it seems a bit better now

dan1st•6d ago

if make sure that the parent is not null and only update the heights in that case

JavaBot•6d ago

See this StackOverflow post for NullPointerExceptions and how to solve them.

john•6d ago

updateHeights(restructureNodeOnRemove);

                        if(restructureNodeOnRemove.parent!=null){
                            updateHeights(restructureNodeOnRemove.parent);
                        }

                        if(restructureNodeOnRemove.parent!=null){
                            updateHeights(restructureNodeOnRemove.parent);
                        }

This message has been formatted automatically. You can disable this using /preferences.

johnOP•6d ago

yeah sure makes sense did it so but again there appears the height problem but now after more assertEquals then before

JavaBot•6d ago

It looks like you are having issues with debugging or issues that can be solved using a debugger. Check out this article on dev.java to see how debugging works and how to use a debugger. This Stack Overflow question and its answers also explain debugging in general. These links describe how to use the debugger in some IDEs: • Debugging in IntelliJ • Debugging in Eclipse

dan1st•6d ago

check it step by step, compare your expectations to what actually happens

johnOP•6d ago

Ok I am trying that

john•6d ago

if (restructureNodeOnRemove != null) {
                        //update heights
                        updateHeights(restructureNodeOnRemove);
                        while (restructureNodeOnRemove != null) {
                            //restructure until tree is balanced
                            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);
                            }
                        }

                    }

if (restructureNodeOnRemove != null) {
                        //update heights
                        updateHeights(restructureNodeOnRemove);
                        while (restructureNodeOnRemove != null) {
                            //restructure until tree is balanced
                            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);
                            }
                        }

                    }

This message has been formatted automatically. You can disable this using /preferences.

johnOP•6d ago

I did it so and seems to work the height test but I am having the last problem now

johnOP•6d ago

this is what I get after many operation it happens a problem

JavaBot•6d 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.

johnOP•5d ago

Sorry for bothering again. There is still something I wanted help. In the first image is the tree, then after removing it I get a tree in a form that is unbalanced. There happens a rotations but its false. If anyone can help please!

johnOP•5d ago

My last code version is this: https://www.codebin.cc/code/cm3k0wp8h0001mn02y3rjx0pk:FZ1YFBWCeDFGwnYDrToE75RpD14Z8iU8nMq1UMw4Jn8U

Codebin Paste - AVLTree

Codebin Paste: Description: // Language: java Last Edited: 11/16/2024, 10:26:46 AM Expires: 11/17/2024, 10:26:08 AM

johnOP•5d ago

sorry this is my last problem here. If you can give it a look please. Thanks @dan1st sorry for the ping, but I'm hopeless. If you can check please. Its a remove error there and as you can see from the images, first the before tree, than the expected result and as a output the tree that happened. Sorry again. As a link is the actual code

dan1st•5d ago

what exactly are you removing there? 14?

johnOP•5d ago

yeah 14

dan1st•5d ago

Can you draw/print the tree after the removeBST call but before the restructure operations? and then print it after each restructure operation for comparison?

johnOP•5d ago

Ok I am trying that

johnOP•5d ago

dan1st•5d ago

then I assume it is calling restructure here with x=19, y=15, z=13?

johnOP•5d ago

I think so but what does this mean for us

dan1st•5d ago

check it with a debugger? And what is the tree after that restructure call? Does it call restructure again? If so, with what parameters?

johnOP•5d ago

public class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        // Insert nodes
        int[] nodesToInsert = {12,5,14,3,9,13,17,0,4,11,19};
        for (int key : nodesToInsert) {
            tree.insertNode(key, 0); // Using 0 as the value for simplicity
        }

        int[] nodesToRemove = {14};
        for (int key : nodesToRemove) {
            tree.removeNode(key); // Using 0 as the value for simplicity
        }


        // Display the tree
        StringBuilder treeDisplay = display(tree);
        System.out.println(treeDisplay);
    }

    public static StringBuilder display(AVLTree tree) {
        final int height = 5, width = 64;

        int len = width * height * 2 + 2;
        StringBuilder sb = new StringBuilder(len);

        for (int i = 1; i <= len; i++)
            sb.append(i < len - 2 && i % width == 0 ? "\n" : ' ');

        displayR(sb, width / 2, 1, width / 4, width, tree.getTreeRoot(), " ");
        return sb;
    }

    private static void displayR(StringBuilder sb, int c, int r, int d, int w, AVLNode n,
                                 String edge) {
        if (n != null) {
            if (n != n.left)
                displayR(sb, c - d, r + 2, d / 2, w, n.left, " /");

            String s = String.valueOf(n.key);
            int idx1 = r * w + c - (s.length() + 1) / 2;
            int idx2 = idx1 + s.length();
            int idx3 = idx1 - w;
            if (idx2 < sb.length())
                sb.replace(idx1, idx2, s).replace(idx3, idx3 + 2, edge);

            if (n != n.right)
                displayR(sb, c + d, r + 2, d / 2, w, n.right, "\\ ");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        // Insert nodes
        int[] nodesToInsert = {12,5,14,3,9,13,17,0,4,11,19};
        for (int key : nodesToInsert) {
            tree.insertNode(key, 0); // Using 0 as the value for simplicity
        }

        int[] nodesToRemove = {14};
        for (int key : nodesToRemove) {
            tree.removeNode(key); // Using 0 as the value for simplicity
        }


        // Display the tree
        StringBuilder treeDisplay = display(tree);
        System.out.println(treeDisplay);
    }

    public static StringBuilder display(AVLTree tree) {
        final int height = 5, width = 64;

        int len = width * height * 2 + 2;
        StringBuilder sb = new StringBuilder(len);

        for (int i = 1; i <= len; i++)
            sb.append(i < len - 2 && i % width == 0 ? "\n" : ' ');

        displayR(sb, width / 2, 1, width / 4, width, tree.getTreeRoot(), " ");
        return sb;
    }

    private static void displayR(StringBuilder sb, int c, int r, int d, int w, AVLNode n,
                                 String edge) {
        if (n != null) {
            if (n != n.left)
                displayR(sb, c - d, r + 2, d / 2, w, n.left, " /");

            String s = String.valueOf(n.key);
            int idx1 = r * w + c - (s.length() + 1) / 2;
            int idx2 = idx1 + s.length();
            int idx3 = idx1 - w;
            if (idx2 < sb.length())
                sb.replace(idx1, idx2, s).replace(idx3, idx3 + 2, edge);

            if (n != n.right)
                displayR(sb, c + d, r + 2, d / 2, w, n.right, "\\ ");
        }
    }
}

I wrote this and I get the expected tree and not a false one

johnOP•5d ago

but this happened to be a error if I do multiple operations

johnOP•5d ago

https://sourceb.in/ZqYmWWYgc4

SourceBin

TestCase

Instantly share your code with the world.

johnOP•5d ago

this is the testcase I fail

JavaBot•5d 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.

dan1st•5d ago

yeah but I am not just interested in the test case but what exactly happens in the removal function like can you display the tree as well as x/y/z before each restructure operation? then do exactly the same operations as the test case?

JavaBot•5d 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.

Gaming

Programming

AVL trees