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!!
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.
posted 6 years ago
Thank you Steve!! I'll see if can fix that.
posted 6 years ago
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.
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.
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.
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: