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
JavaBot3w 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
dan1st3w ago
We can't help you without the relevant code or and you telling us what exactly happens
john
johnOP3w ago
SourceBin
AVLTree.java
Instantly share your code with the world.
john
johnOP3w 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
dan1st3w 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
john
johnOP3w ago
doesnt that do the updateHeight() method itself it is a recursive call there for the node parent
Lithor
Lithor3w 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
dan1st3w 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?
john
johnOP3w ago
I changed it and added a update height after each insert
dan1st
dan1st3w ago
Does that change anything?
Lithor
Lithor3w 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.
john
johnOP3w ago
I did it so Tried to debug but I dont see the problem again
dan1st
dan1st3w ago
Does that mean it worked or does it mean it didn't work?
john
johnOP3w ago
no it didn't work
john
johnOP3w ago
see for ex
No description
dan1st
dan1st3w ago
Can you try the previous part and show e what the debugger shows you at the updateHeights(n) call?
john
johnOP3w ago
No description
john
johnOP3w ago
you mean so?
dan1st
dan1st3w 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)
john
johnOP3w ago
updateHeights(n.parent) if I do that I get a stackoverflow at updateHeights
john
johnOP3w ago
No description
dan1st
dan1st3w 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
john
johnOP3w ago
actually z is b
dan1st
dan1st3w ago
normally it could be anything
john
johnOP3w ago
I mean after rotation at the beginning yes
dan1st
dan1st3w ago
for example where I marked it, it's y
No description
dan1st
dan1st3w 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
john
johnOP3w ago
yeah I see
dan1st
dan1st3w 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
john
johnOP3w 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
dan1st3w ago
there is literally
dan1st
dan1st3w ago
that part can overwrite z.parent
No description
dan1st
dan1st3w ago
so you need that code and move it before it
No description
john
johnOP3w ago
now its a bit better I think some tree test works and some not
dan1st
dan1st3w 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)?
john
johnOP3w 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:
No description
dan1st
dan1st3w ago
print the whole tree after every insertion and check whether everything matches your expection which you get when drawing it by hand
john
johnOP3w ago
I should be again something in the restructure method I guess
Lithor
Lithor3w 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.
john
johnOP3w ago
i just changed the code position there is this what you meant
dan1st
dan1st3w ago
. yes, that's fine but first you need to find out which insert causes the issue by doing this
john
johnOP3w ago
insertNode(12); causes the mistake
dan1st
dan1st3w ago
What's the tree before, what you expect it to be after the operation and what is it actually after the operation?
john
johnOP3w ago
assertEquals(root.left.right.key, 12, strError); it should be root.left.right as the test says
dan1st
dan1st3w 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
john
johnOP3w ago
ok. I am trying that
john
johnOP3w 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);
No description
john
johnOP3w ago
this is what I expect after adding node 12
No description
john
johnOP3w ago
and here node 12 fails to be left-right node
No description
dan1st
dan1st3w ago
Did you check whether it's actually that tree? and what is the exact actual tree?
john
johnOP3w 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
dan1st3w ago
so node 8 is there twice?
john
johnOP3w ago
yeah 8 twice and 18 doesnt appear
dan1st
dan1st3w ago
Is 18 in the tree before inserting 12?
john
johnOP3w 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
dan1st3w ago
and 16 is gone as well there Can you show the actual tree before restructuring?
john
johnOP3w ago
No description
dan1st
dan1st3w ago
Why that? How does it get to that from there?
john
johnOP3w ago
so here i did just the binary search tree thats wrong
dan1st
dan1st3w ago
btw here you aren't updating g.t0.parent, g.t1.parent, g.t2.parent and g.t3.parent
No description
dan1st
dan1st3w ago
idk why it would look like that Is this intentional? If so, why?
john
johnOP3w ago
I tried to follow this structure
No description
dan1st
dan1st3w ago
yes ik but you still need to update t0.parent etc (you can also use the setRight and setLeft methods for these things)
john
johnOP3w 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
dan1st3w ago
nice
john
johnOP3w ago
yeah, thanks. Now my next challenge is remove
JavaBot
JavaBot3w 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.
john
johnOP3w 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
dan1st3w ago
Does removing the element give you the right tree (ignoring the heights)?
john
johnOP3w 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
dan1st3w ago
you have updateHeights(restructureNodeOnRemove); you might also need updateHeights(restructureNodeOnRemove); that doesn't match the output from before
john
johnOP3w ago
I didnt get that what did you mean here?
dan1st
dan1st3w ago
my fault you have that in your code
john
johnOP3w ago
yes
dan1st
dan1st3w 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
john
johnOP3w ago
yeah but i think again the updateHeights make the update for all the tree
dan1st
dan1st3w 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
john
johnOP3w ago
you mean so
No description
john
johnOP3w ago
I did that but no success
john
johnOP3w ago
these are the jUnit tests I have
No description
john
johnOP3w 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
dan1st3w ago
if make sure that the parent is not null and only update the heights in that case
JavaBot
JavaBot3w ago
See this StackOverflow post for NullPointerExceptions and how to solve them.
Lithor
Lithor3w 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.
john
johnOP3w ago
yeah sure makes sense did it so but again there appears the height problem but now after more assertEquals then before
JavaBot
JavaBot3w 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 IntelliJDebugging in Eclipse
dan1st
dan1st3w ago
check it step by step, compare your expectations to what actually happens
john
johnOP3w ago
Ok I am trying that
Lithor
Lithor3w 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.
john
johnOP3w ago
I did it so and seems to work the height test but I am having the last problem now
john
johnOP3w ago
No description
john
johnOP3w ago
this is what I get after many operation it happens a problem
JavaBot
JavaBot3w 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.
john
johnOP3w 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!
No description
No description
No description
john
johnOP3w ago
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
john
johnOP3w 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
dan1st3w ago
what exactly are you removing there? 14?
john
johnOP3w ago
yeah 14
dan1st
dan1st3w 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?
john
johnOP3w ago
Ok I am trying that
john
johnOP3w ago
No description
dan1st
dan1st3w ago
then I assume it is calling restructure here with x=19, y=15, z=13?
No description
john
johnOP3w ago
I think so but what does this mean for us
dan1st
dan1st3w 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?
john
johnOP3w 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
john
johnOP3w ago
No description
john
johnOP3w ago
but this happened to be a error if I do multiple operations
john
johnOP3w ago
SourceBin
TestCase
Instantly share your code with the world.
john
johnOP3w ago
this is the testcase I fail
JavaBot
JavaBot3w 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
dan1st3w 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
JavaBot3w 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.
Want results from more Discord servers?
Add your server