資料結構與演算法：AVL Tree

這次圖片較多，進入前請三思。

AVL Tree 是一種Binary search tree實做方式，大部分的實做方式與BST一樣，差異在於AVL tree在過程中會透過計算並調整樹的結構來讓樹維持平衡，而不會導致BST過度傾斜(不平衡）。

要做到這點，需要透過幾項資訊來做到，分別是計算節點高度(height)、計算Balance factor與理解什麼是高度平衡樹

1. 節點(Node)的高度(height)

Height of node: Length of the longest path from it to the leaf

height = max( leftChildHeight, rightChildHeight) + 1

子節點為 null 時，高度視為 -1，其餘就是左右子節點中，最大的高度 + 1即為當前節點高度。

如下圖，標註了各個節點的高度

2. Balance Factor of T, BF(T)

For node T in a binary search tree is defined to be HL-HR, where HL and HR respectively, are the heights of the left and right subtree of T.

簡單來說就是計算出節點 T的左右子節點高度後相減，即為balance factor

balance factor有以下特性：

BF(T) < -1：右邊subtree比較重，需要將一些右邊節點往左邊調整

-1 <= BF(T) <= 1：表示平衡，暫時不用調整

BF(T) > 1：左邊subtree比較重，需要將一些左邊節點往右邊調整

如下圖，可以計算各個節點上的BF

3. 高度平衡：

hight-balanced：

Empty tree is height-balance

If T is a nonempty binary tree with TL and TR as left and right subtrees respectively, T is hight-balanced iff

TL and TR are height-balanced

Math.abs( HL - HR) <= 1 where HL and HR are the height of TL and TR respectively.

這是AVL tree最主要的目的，簡單來說，要判斷一個二元樹是否平衡的方式，就是計算 root 左右節點的高度，得到高度後相減，如果得到的結果 < -1或 > 1，則表示這棵樹有某一側比較重，處於不平衡的狀態，需要調整來讓樹繼續維持平衡。

下面這張圖標為綠色的節點，或是 subtree，表示為balance，標為紅色的部分表示不平衡，需要做調整。

Rebalancing

在遇到不平衡情況時，需要調整數的節點，這邊稱為Rotation，Rotation有個很重要的目的， rotation 前與後的樹，整個 tree的 in-order traversal 相同 。

首先說明兩種 rotation：

1. Left Rotation

讓樹往左邊做 rotate來達到balance，參考下圖，簡單步驟如下：

對 A做 left rotation：將B的左節點設為 A 的右節點後，再將A設為 B的左節點，所以可以注意圖上有顏色的 null如何變化。同時 in-order的結果還是一樣不變。

2. Right Rotation

讓樹往右邊做 rotate來達到balance，參考下圖，簡單步驟如下：

對A做right rotation：將B的右節點設為 A 的左節點後，再將A設為 B的右節點，所以可以注意圖上有顏色的 null如何變化。同時 in-order的結果還是一樣不變。

選擇用何種方式做 rotation，判斷準則為

BF >1，表示左邊較重，需要做 right rotation

BF<-1，表示右邊較重，需要做 left rotation

旋轉類型總共分為四種，雖然有四種，但都是 left rotation與 right rotation的變化組合，並且遵照上面提到的方式選擇做rotation：

1. LL型：C被新增到 A 左節點的左節點，並且遵照上面提到的方式選擇做rotation

調整方式：對 A做 right rotation即可

調整完後，來看調整前後樹的 in-order traversal：

調整前： C -> B -> A

調整後： C -> B -> A

2. LR型：C被新增到 A 左節點的右節點

調整方式：先對 B做 left rotation，會變成 LL型，接著再做一次 right rotation即可

先做left rotation：

再對A做 right rotation：

調整完後，來看調整前後樹的 in-order traversal：

調整前： B -> C -> A

調整後： B -> C -> A

3. RR型：C被新增到 A 的右節點的右節點

調整方式：對 A做 left rotation即可

調整完後，來看調整前後樹的 in-order traversal：

調整前： A -> B ->C

調整後： A -> B -> C

4. RL型：C被新增到 A 右節點的左節點

調整方式：對 B做 right rotation後，再對 A 做 left rotation

對 B做 right rotation：

再對 A做 lelft rotation：

調整完後，來看調整前後樹的 in-order traversal：

調整前： A -> C ->B

調整後： A -> C -> B

所以最一開始那張沒有平衡的圖(假設紫色的節點是剛新增上去的新節點)，在新增節點後造成左邊 subtree過重，所以需要對 root做 right rotation，這張圖的情況可以判斷為 LL型，如前面提到LL型定義：新增的紫色節點在root 的左節點的左節點，故只要做一次 right rotation即可：

做了 right rotation後

時間複雜度

功能	Average	Worst
Search	O(LogN)	O(LogN)
Insert	O(LogN)	O(LogN)
Delete	O(LogN)	O(LogN)

Node height & Balance factor implementation

節點高度： max(左子結點高度, 右子節點高度) +1

Balance factor：左子結點高度 - 右子節點高度

    private int getNodeHeight(TreeNode node){
        if(node == null)
            return -1;
        return node.getHeight();
    }

    /**
     * Calculate balance factor of the node
     * @param node
     * @return
     */
    private int getBalanceFactor(TreeNode node){
        if(node == null)
            return 0;

        return getNodeHeight(node.getLeftNode()) - getNodeHeight(node.getRightNode());

    }

Rotation implementation

主要在於root節點與左或右節點交換位置，但是重點還是交換後必須維持 tree inorder的一致。

   /**
     * Doing right rotation on specified subtree
     * @param node
     * @return new root of subtree
     */
    private TreeNode rightRotation(TreeNode node){
        System.out.println("Perform right rotation on node:" + node.getData());
        // nodes relate to right rotation
        TreeNode leftChild = node.getLeftNode();
        TreeNode tempNode = leftChild.getRightNode();

        // update node reference
        node.setLeftNode(tempNode);
        leftChild.setRightNode(node);

        // update node height, child must update height first
        updateNodeHeight(node);
        updateNodeHeight(leftChild);
        
        return leftChild;
    }

    /**
     * Doing left rotation on specified subtree
     * @param node
     * @return new root of subtree
     */
    private TreeNode leftRotation(TreeNode node){
        System.out.println("Perform left rotation on node:" + node.getData());
        // nodes relate to right rotation
        TreeNode rightChild =node.getRightNode();
        TreeNode tempNode = rightChild.getLeftNode();

        // update node reference
        node.setRightNode(tempNode);
        rightChild.setLeftNode(node);

        // update node height, child must update height first
        updateNodeHeight(node);
        updateNodeHeight(rightChild);

        return rightChild;
    }

Insert implementation

新增的邏輯與 BST相同，差異在於新增完一個節點後，都要重新計算節點高度與 BF來確定是否平衡，所以關鍵的程式在 updateTreeBalance程式內，如果沒有平衡，則需要對樹做rotation。

updateTreeBalance流程大概如下：

計算 BF

如果bf <-1，表示右邊子節點過重，需要對樹做left rotation；相反的如果 bf >1，則表示左邊子節點過重，要做right rotation。如果介於 -1 <= bf <= 1，則毋須動作。

右邊過重時，檢查屬於 RR 或RL型來決定作哪種rotation

左邊過重時，檢查屬於LL或LR型來決定作哪種rotation

rotation完畢後，需要更新node高度

回傳最新的subtree root

    private TreeNode insertElement(T data, TreeNode currentNode){

        if(currentNode == null)
            return new TreeNode(data);

        if(currentNode.getData().compareTo(data) <= -1)
            currentNode.setRightNode(this.insertElement(data, currentNode.getRightNode()));
        else
            currentNode.setLeftNode(this.insertElement(data, currentNode.getLeftNode()));

        // update node height and balance after inserting the node
        updateNodeHeight(currentNode);
        currentNode = updateTreeBalance(currentNode);

        return currentNode;
    }

    /**
     * Update the height data of the node
     * @param node
     */
    private void updateNodeHeight(TreeNode node){
        if(node == null)
            return;
        node.setHeight( Math.max(getNodeHeight(node.getLeftNode()), getNodeHeight(node.getRightNode())) +1);
    }

   /**
     * Checking and updating the tree balance starting from the node
     * @param node the root of subtree to be checked
     * @return new root node of the subtree
     */
    private TreeNode updateTreeBalance(TreeNode node){

        int bf = getBalanceFactor(node);
        if(bf >1){
          	// 檢查左側還是右側的樹看哪邊比較重，右邊比較重，則為LR，左邊比較重則是LL
            if( getBalanceFactor(node.getLeftNode())== 1 ){
                // LL type
                return rightRotation(node);
            }else {
                // LR type
                node.setLeftNode(leftRotation(node.getLeftNode()));
                return rightRotation(node);
            }
        }else if(bf < -1){
            // 檢查左側還是右側的樹看哪邊比較重，右邊比較重，則為RR，左邊比較重則是RL
            if(getBalanceFactor(node.getRightNode()) == -1 ){
                // RR type
                return leftRotation(node);
            }else{
                // RL type
                node.setRightNode(rightRotation(node.getRightNode()));
                return leftRotation(node);
            }
        }

        return node;

    }

Delete implementation

刪除的邏輯與 BST相同，差異同樣在於刪除後，需要重新計算節點高度與BF，並且適時做 rotation來讓樹平衡。

    private TreeNode deleteElement(T data, TreeNode node){
        if(node == null)
            return null;
        
        if(node.getData().compareTo(data) <0){
            node.setRightNode(deleteElement(data, node.getRightNode()));
        }else if(node.getData().compareTo(data) >0){
            node.setLeftNode(deleteElement(data,node.getLeftNode()));
        }else{
            // case 1: target data is a leaf node
            if(node.getLeftNode() == null && node.getRightNode() == null)
                return null;
            // case 2: target data only has right child
            else if(node.getLeftNode() ==null)
                return node.getRightNode();
            // case 3: target data only has left child
            else if(node.getRightNode() == null)
                return node.getLeftNode();
            // case 4: target data has left and right child
            else{
                // find the node which has the max value on the left subtree
                TreeNode leftMaxValueTreeNode = findMaxValueNode(node.getLeftNode());

                // swap the data
                Comparable tempData = node.getData();
                node.setData(leftMaxValueTreeNode.getData());
                leftMaxValueTreeNode.setData(tempData);

                // delete the data
                node.setLeftNode(deleteElement(data, node.getLeftNode()));
            }
        }
        // update tree height
        updateNodeHeight(node);

        // update tree balance
        return updateTreeBalance(node);
        
    }

測試

這邊簡單針對insert與delete做一個測試

public class App {
    public static void main(String[] args) {
        Tree<String> tree = new AvlTree<>();
        tree.insertElement("APR");
        tree.insertElement("AUG");
        tree.insertElement("DEC");
        tree.insertElement("FEB");
        tree.insertElement("JAN");
        tree.insertElement("JULY");
        tree.insertElement("JUNE");
        tree.insertElement("MAR");
        tree.insertElement("MAY");
        tree.insertElement("NOV");
        tree.insertElement("OCT");
        tree.insertElement("SEPT");
        tree.traverse();
        tree.deleteElement("APR");
        tree.deleteElement("JAN");
        tree.deleteElement("FEB");
        tree.traverse();
    }
}

輸出結果，可以觀察到過程中的rotation操作：

Perform left rotation on node:APR
Perform left rotation on node:DEC
Perform left rotation on node:AUG
Perform left rotation on node:JAN
Perform left rotation on node:JUNE
Perform left rotation on node:JULY
Perform left rotation on node:MAY
Perform left rotation on node:FEB
Traversing the tree:
 -> APR
 -> AUG
 -> DEC
 -> FEB
 -> JAN
 -> JULY
 -> JUNE
 -> MAR
 -> MAY
 -> NOV
 -> OCT
 -> SEPT
Traversing the tree:
 -> AUG
 -> DEC
 -> JULY
 -> JUNE
 -> MAR
 -> MAY
 -> NOV
 -> OCT
 -> SEPT

這邊針對部分的新增流程再做一個記錄，主要用於觀察 tree rotation方式，可以對應到上面rotation輸出記錄：

前三個新增，APR 節點出現右邊子節點過重，且屬於RR型，需要對APR做 left rotation：