CODEWITHSUNDEEP
javatreenodes
user8659414
user8659414

Reputation: 23

Rotation of AVL Tree nodes results in nodes disappearing

I'm attempting to write an AVL tree in Java and have been stuck on this for two nights. When the following code is run, a rotation certainly happens, but the end result of say, for example, leftRotate, is that I am losing nodes.

public AVLNode leftRotate(AVLNode node){ //receives the grandparent node
    AVLNode temp = node.right;
    node.right = temp.left;
    temp.left = node;

    return temp;    
}

public AVLNode rightRotate(AVLNode node){
    AVLNode temp = node.left;
    node.left = temp.right;
    temp.right = node;

    return temp;
}

public AVLNode rightLeftRotate(AVLNode node){
    node.right = rightRotate(node.right);
    return leftRotate(node);
}

public AVLNode leftRightRotate(AVLNode node){
    node.left = leftRotate(node.left);
    return rightRotate(node);
}

If I add root = temp to the left and right rotate methods, then the rotation and new display occurs successfully only for the first go around, and then things get all mixed up.

Example: Inserting 4, 5 and then 6. After the rotation, temp holds 5 as its "root", with 4 and 6 correctly contained as the keys of its left and right children. However, all of this goes away after the method ends, and the left and right children of my tree's root are now null.

I know it's something small that I'm missing, but I can't wrap my head around it.

I also know it's not my addNode function because when it has finished adding all the nodes, the resulting tree is a binary search tree regardless. It's only when calling these functions that I start losing nodes. Any help?

Upvotes: 2

Views: 632

Answers (1)

Jacobo de la Rosa
Jacobo de la Rosa

Reputation: 91

I think is a problem of how the memory is managed, instead of AVLNode temp = node.left; or AVLNode temp = node.left; instanciate a new AVLNode and copy the information, so you dont have a pointer to the previous object. What is happening is that when you do AVLNode temp = node.left; temp is a pointer to the node.left, so if you return temp, all the changes and rotations are done to the original node.

Upvotes: 0

Related Questions