AVL树节点的旋转导致节点消失

Question

我正在尝试在Java中编写AVL树，并且一直在这里停留两晚。当下面的代码运行时，肯定会发生旋转，但最终的结果，例如leftRotate，就是我正在丢失节点。

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); 
} 

如果我添加root = temp左，右旋转的方法，然后旋转和新的显示成功只发生在第一次去走一走，然后得到的东西都混了。

示例：插入4,5和6.旋转后，temp保留5作为其 “根”，其中4和6正确包含作为其左侧和右侧子项的键。但是，所有这些在方法结束后都会消失，我的树根的左右子节点现在都是空的。

我知道这是我很想念的东西，但是我无法把头围住它。

我也知道这不是我的addNode函数，因为当它完成添加所有节点时，不管结果树是二叉搜索树。只有在调用这些函数时才会开始丢失节点。任何帮助？

Answer 1

我认为是如何管理内存的问题，而不是使用新的AVLNode实现新的AVLNode并复制信息，因此您没有指向先前对象的指针。 发生什么事是，当你做AVLNode temp = node.left; temp是指向node.left的指针，因此如果返回temp，则所有更改和旋转都将完成到原始节点。