AVL樹插入操作實現

為了提高二插排序樹的性能，規定樹中的每個節點的左子樹和右子樹高度差的絕對值不能大於1。為了滿足上面的要求需要在插入完成後對樹進行調整。下面介紹各個調整方式。

右單旋轉

---

如下圖所示，節點A的平衡因子(左子樹高度減右子樹高度)為1。由於在節點A的左孩子B的左子樹上插入了新節點，導致B的左子樹高度增加1，從而導致A的平衡因子為2，這時為了保持平衡需要對樹進行調整。

旋轉的方法就是將A的變為B的右子樹，將B的右子樹變為A的左子樹。

示例代碼：

private Node RRotate(Node node){

Node A= node;
Node B= node.LChild;

//旋轉
Node tmp = B.RChild;
B.RChild= A;
A.LChild= tmp;

//更新樹的高度
A.height = Math.max(height(A.LChild), height(A.RChild))+1;
B.height= Math.max(height(B.LChild), height(B.RChild))+1;
return B;
}

（每個節點我們維護了一個height的屬性來記錄樹的高度，每次旋轉完成後需要更新樹的高度。因為旋轉會導致書的根節點發生變化，所以每次旋轉完成後需要將新的根節點返回）

左單旋轉

---

左單旋轉整好與右單旋轉相反。右單旋轉是因為左子樹太高，而左單旋轉則是因為右子樹太高，需要降低其高度。

如圖所示節點B的右子樹高度增加1，導致節點A的平衡因子變為-2，所以需要進行左旋調整位置。

旋轉方法：將A變為B的左子樹，將B的左子樹變為A的右子樹

示例代碼：

private Node LRotate(Node node){
Node A= node;
Node B= node.RChild;

//旋轉
Node tmp = B.LChild;
B.LChild= A;
A.RChild= tmp;

//更新樹的高度
A.height = Math.max(height(A.LChild), height(A.RChild))+1;
B.height= Math.max(height(B.LChild), height(B.RChild))+1;

return B;
}

（每個節點我們維護了一個height的屬性來記錄樹的高度，每次旋轉完成後需要更新樹的高度。因為旋轉會導致書的根節點發生變化，所以每次旋轉完成後需要將新的根節點返回）

先左後右旋轉

---

上面的兩種情況處理比較簡單，因為插入的節點要麼是根節點左孩子的左子樹或者是根節點右孩子的右子樹。如果插入的節點在根節點左孩子的右子樹上，則需要先進行左旋然後進行右旋操作。

如圖所示，插入的節點在B節點右子樹上，這時需要對B節點進行左旋操作，然後對A節點進行右旋操作。

示例代碼：

private Node LRRotate(Node node){
//先進行左旋
LRotate(node.LChild);
//在進行右旋
return RRotate(node);
}

代碼中node節點就是圖中的A節點，先對A節點的左孩子B進行左旋操作，然後對A(node)節點進行右旋操作

先右旋後左旋

---

當插入的節點在根節點的右孩子的左子樹上，則需要進行先右旋後左旋操作。

示例代碼:

//先右後左旋轉
private Node RLRotate(Node node){
//再進行右旋轉
RRotate(node.RChild);
//再進行右旋
return LRotate(node);
}

插入操作

---

插入操作通過遞歸方式實現，在插入操作完成後需要對訪問路徑上的每個節點進行判斷來確定是否要旋轉。

public Node insert(Node node, int i){
//先將節點插入到樹中
if(node == null)
return new Node(i, 1, node);

//插入的值與當前節點值進行比較來確定插入的位置
if(i < node.val){
node.LChild= insert(node.LChild, i);//判斷是否進行調整
if(height(node.LChild) - height(node.RChild) == 2){
if(i < node.LChild.val)
//插入的節點在左孩子的左子樹上，則需要進行右旋
node = RRotate(node);
else
//插入的節點在左孩子的右子樹上，則需要先進行左旋後進行右旋
node = LRRotate(node);
}
}
else{
node.RChild= insert(node.RChild, i);
if(height(node.LChild) - height(node.RChild) == -2){
if(i > node.RChild.val)
node= LRotate(node);
else
node= RLRotate(node);
}
}
node.height= Math.max(height(node.LChild), height(node.RChild))+1;
return node;
}

//計算樹的高度,主要解決空樹高度的問題(空樹的高度為0)
    private int height(Node node){
        return node == null ? 0:node.height;
    }

判斷一棵樹是否是AVL樹

---

判斷時通過後續遍歷的方式來比較左右子樹的高度差

static boolean isBalance(Node node,Depth d){
if(node == null){
d.height=0;
return true;
}
Depth right=new Depth();
Depth left= new Depth();
if(isBalance(node.LChild,left)&&isBalance(node.RChild, right)){
if(Math.abs(left.height - right.height)<2){//絕對值小於等於1
//如果是平衡樹，才有必要算深度，然後看上級是不是平衡樹
d.height=(left.height>right.height?left.height:right.height)+1;
System.out.println("left="+left.height+" right="+right.height+" height"+d.height+" value="+node.val);
return true;
}
}
System.out.println("left="+left.height+" right="+right.height+" height"+d.height+" value="+node.val);
return false;
}

static class Depth{
int height;
}

完整代碼

package com.dy.xidian;

public class AVL {
    private Node root;
    static class Node{
        int val; //存儲數據
        int height; //權重
        Node LChild; //右孩子
        Node RChild; //左孩子
        
        public Node(int k, int _height){
            this.val = k;
            this. height = _height;
        }
    }
    
    private void initAVL(int[] arr){
        for(int i : arr)
            root = insert(root, i);
    }
    
    public AVL(int[] arr){
        initAVL(arr);
    }
    
    //右旋
    private Node RRotate(Node node){
        
        Node A = node;
        Node B = node.LChild;
        
        //旋轉
        Node tmp = B.RChild;
        B.RChild = A;
        A.LChild = tmp;
        
        //更新樹的高度
        A.height = Math.max(height(A.LChild), height(A.RChild))+1;
        B.height = Math.max(height(B.LChild), height(B.RChild))+1;
        return B;
    }
    
    //左旋
    private Node LRotate(Node node){
        Node A = node;
        Node B = node.RChild;
        
        //旋轉
        Node tmp = B.LChild;
        B.LChild = A;
        A.RChild = tmp;
        
        //更新樹的高度
        A.height = Math.max(height(A.LChild), height(A.RChild))+1;
        B.height = Math.max(height(B.LChild), height(B.RChild))+1;
        
        return B;
    }
    
    //先左後右旋轉
    private Node LRRotate(Node node){
        //先進行左旋
        LRotate(node.LChild);
        //在進行右旋
        return RRotate(node);
    }
    
    //先右後左旋轉
    private Node RLRotate(Node node){
        //再進行右旋轉
        RRotate(node.RChild);
        //再進行右旋
        return LRotate(node);
    }
    
    //計算樹的高度,主要解決空樹高度的問題(空樹的高度為0)
    private int height(Node node){
        return node == null ? 0:node.height;
    }
    
    public Node insert(Node node, int i){
        //先將節點插入到樹中
        if(node == null)
            return new Node(i, 1);
        
        //插入的值與當前節點值進行比較來確定插入的位置
        if(i < node.val){
            node.LChild = insert(node.LChild, i);
            //判斷是否進行調整
            if(height(node.LChild) - height(node.RChild) == 2){
                if(i < node.LChild.val)
                    //插入的節點在左孩子的左子樹上，則需要進行右旋
                    node = RRotate(node);
                else
                    //插入的節點在左孩子的右子樹上，則需要先進行左旋後進行右旋
                    node = LRRotate(node);
            }
        }
        else{
            node.RChild = insert(node.RChild, i);
            if(height(node.LChild) - height(node.RChild) == -2){
                if(i > node.RChild.val)
                    node = LRotate(node);
                else
                    node = RLRotate(node);
            }
        }
        node.height = Math.max(height(node.LChild), height(node.RChild))+1;
        return node;
    }
    
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
        AVL avl = new AVL(arr);
    }
}