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，則所有更改和旋轉都將完成到原始節點。