• Post Reply Bookmark Topic Watch Topic
  • New Topic

AVL Tree Help please  RSS feed

 
Maria Macalino
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone,

I am trying to write code for an AVLTree in java. So far I have done my preOrder, inOrder, levelOrder, postOrder, add, removeMin, removeMax, isEmpty, size, and iniatilaized my tree. I have code for my remove target method but when I run it, it seems to loop infinitely. Can someone look over my code and tell me what it is I'm doing wrong. Thank you all for your time!!








 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The first point in the infinite loop is in the replacement() method. You have this loop:

You loop continuously on current.getLeft() != null. If that test isn't true the first time then it will never be true because you don't change current and you don't change the value stored in current's left node.

You do the same sort of thing at a later point in the remove() method.
 
Maria Macalino
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Steve!! I'll see if can fix that.
 
Maria Macalino
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Could you recommend a way to stop this loop from infinitely looping? should I set current back to parent and traverse right? I see why it's looping thanks to your explanation, but I can't think of a way to fix this. Sorry I am not a very good programmer and I have not programmed in java in a while so these problems are extremely difficult for me to visualize and therefore fix.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Answer me this: why do you have that loop in your code? What is it supposed to do?
 
Maria Macalino
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I just figured it out!

current.getLeft(); should be current = current.getLeft();

Thank you!
 
Maria Macalino
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The last thing I'm struggling with is how to implement a balance factor for each node in the tree.

Should I create a height method that returns height and use that along with levelTraversal method to somehow store the balance factor (Right subtree - Left subtree) at each node as it traverses?
 
Mohamed Sanaulla
Bartender
Posts: 3185
34
Google App Engine Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maria Macalino wrote:The last thing I'm struggling with is how to implement a balance factor for each node in the tree.

Should I create a height method that returns height and use that along with levelTraversal method to somehow store the balance factor (Right subtree - Left subtree) at each node as it traverses?


Either you store the balance factor for each node- which means this has to be calculated each time a new node is inserted in its sub tree.
OR
You let the balance factor be calculated each time it is requested for- You would use the height of left sub tree and height of the right sub tree from that node.

Any of the approaches would do.
 
Maria Macalino
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks I think I'm going to create a getHeight method and add it on to the nodes as I traverse but I might also try adding it during the add method.

I was actually having issues with my remove method again and also my removeMin. My remove method isn't looping infinitely anymore but when I run my code it highlights the while loop and I can't figure out what to fix.
My removeMax method seems to be working fine but my removeMin seems to remove every left child or more than it should.

everything else is the same except for the AVLTree.java file:






 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!