用於Java的AVL樹

Question

我不知道我是否正確地做這件事，因爲這是我第一次用節點編碼。但是，到目前爲止，這是我的代碼，如果有人可以查看它並幫助我瞭解我是否做錯了什麼。另外我的插入/刪除方法讓我很難。教授給了我們這個僞代碼，但我似乎無法理解如何將它解釋爲Java代碼，因爲我從來沒有做過這種類型的代碼。主要是因爲有一條if語句來檢查高度，看看樹是否平衡，我將如何實現高度？提示或任何幫助非常感謝，我一直堅持這一段時間。謝謝！

我也不認爲我做了我的構造函數正確，我不確定它。插入/刪除的返回可以忽略，它只是放在那裏以確保其餘的代碼將被編譯。

public class AvlNode{ 

    public static void main(String[]args){ 

    } 
    //constructor 
    public class AvlTreeNode{ 
     private int num; 
     private AvlTreeNode left; 
     private AvlTreeNode right; 

     public AvlTreeNode left(){ 
      return this.left; 
     } 

     public AvlTreeNode right(){ 
      return this.right; 
     } 

     public int value(){ 
      return this.num; 
     } 
    } 
    //method to find the number specified on the node 
    public AvlTreeNode find(AvlTreeNode t, int x){ 
     if(t == null){ 
      return null; 
     } 
     if(t.value() == x){ 
      return t; 
     } 
     else if(x < t.value()){ 
      return find(t.left(), x); 
     } 
     else{ 
      return find(t.right(), x); 
     } 
    } 
    //method to insert a new node and number to a tree 
    public AvlTreeNode insert(AvlTreeNode t, int x){ 
     if(t == null){ 
      t = new AvlTreeNode(x, null, null); 
      return t; 
     } 
     if(x < t.value()){ 
      t.left = insert(t.left(), x); 
     } 
     return t; 
    } 
    //method to remove a node and number from the tree 
    public AvlTreeNode remove(AvlTreeNode t, int x){ 
     return t; 
    } 
    //Inorder traversal method, should print out numbers in ascending order if correct 
    public void inOrder(AvlTreeNode t){ 
     if(t != null){ 
      inOrder(t.left()); 
      System.out.print(t.value() + " "); 
      inOrder(t.right()); 
     } 
    } 
    //single rotation of nodes to balance tree, rotating leftwards 
    public static AvlTreeNode singleRotateWithLeft(AvlTreeNode k1){ 
     AvlTreeNode k2 = k1.left; 
     k1.left = k2.right; 
     k2.right = k1; 
     return k2; 
    } 
    //single rotation of nodes to balance tree, rotating rightwards 
    public static AvlTreeNode singleRotateWithRight(AvlTreeNode k2){ 
     AvlTreeNode k1 = k2.right; 
     k2.right = k1.left; 
     k1.left = k2; 
     return k1; 
    } 
    //double rotation of nodes towards the left 
    public static AvlTreeNode doubleRotateWithLeft(AvlTreeNode k3){ 
     k3.left = doubleRotateWithRight(k3.left); 
     return doubleRotateWithLeft(k3); 
    } 
    //double rotation of nodes towards the right 
    public static AvlTreeNode doubleRotateWithRight(AvlTreeNode k2){ 
     k2.right = doubleRotateWithLeft(k2.right); 
     return doubleRotateWithRight(k2); 
    } 
} 

Answer 1

關於構造函數：我認爲這是錯誤的，是你錯，你用它來描述一個AvlTreeNode用於構造內部類的東西。很有可能，你不需要寫一個明確的構造函數，因爲默認的（空的）函數會爲你做。

樹的構建可以看作是將其所有節點插入到空樹中。

關於高度，您應該可以查看樹的高度作爲每個AvlTreeNode的屬性（因此，在num旁邊，您需要一個height變量）。接下來的事情是實現插入和移除，以便使用正確的局部變換/旋轉，並且插入節點及其子節點的高度可以適當增加或減少。

編輯：我現在看到你的代碼使用了帶三個參數的構造函數。你可以使用這個示例代碼中的構造函數。

//inner class for the node 
public class AvlTreeNode{ 
    private int num; 
    private int height; 

    private AvlTreeNode left; 
    private AvlTreeNode right; 

    //this is the constructor! 
    public AvlTreeNode(int value, AvlTreeNode left, AvlTreeNode right){ 
     this.num = value; 
     this.left = left; 
     this.right = right; 
     this.height = 1; 

     if (left != null && left.height() >= height){ 
      height = left.height() + 1; 
     } 
     if (right != null && right.height() >= height){ 
      height = right.height() + 1; 
     } 
    } 

    public AvlTreeNode left(){ 
     return this.left; 
    } 

    public AvlTreeNode right(){ 
     return this.right; 
    } 

    public int value(){ 
     return this.num; 
    } 

    public int height(){ 
     return height; 
    } 
}