AVL-高度平衡二元搜尋樹

關於AVL樹的介紹，其實與我共筆的作者已經介紹過基本的四種型態，本文將著重於各種旋轉的實作，關於基本介紹請參考：AVL高度平衡二元搜尋樹介紹。

AVL樹的加入與平衡

基本上，AVL樹的加入先以BST(二元搜尋樹)的方式加入，關於BST的介紹與實作請參考：樹－二元搜尋樹之介紹與範例。加入之後，重新計算BF(平衡因子)，當大於2時，則需要進行旋轉，共有四種旋轉方式：LL、RR、LR、RL。在介紹各種型態的旋轉方式之前，我們先來討論如何計算BF。

BF計算

BF的計算方式是左子樹的高度 - 右子樹的高度，即是該節點的BF(備註:高度即是深度)。而高度的計算我是利用遞迴(堆疊)計算，由樹根開始堆疊至底部，再由底部向上計算高度。

    public int height(node node) {

        if (node != null) {
            //當傳入的節點之左右子樹為空時
            if (node.rlink == null && node.llink == null) {
                return 1;
            } else {
                return 1 + (height(node.llink) > height(node.rlink) ? height(node.llink) : height(node.rlink));
            }
            //分別堆疊計算左右子樹高，回傳較大者  
        }
        return 0;

    }

BF的計算則是先計算左右子點高度，再相減即可。

    public void bf(node node) {

        if (node != null) {
            //利用後序走訪計算BF

            bf(node.llink);
            bf(node.rlink);
            System.out.printf("NODE LLINK HEI:%d    NODE RLINK HEI:%d   ", height(node.llink), height(node.rlink));
            node.bf = height(node.llink) - height(node.rlink);
            System.out.printf("BF %d\n", node.bf);
        }

    }

尋找需調整的節點

實作上如何確認哪個節點要調整，如下:

    public node find_pivot() {

        current = root;
        pivot = null;
        while (current != null) {
            if (current.bf > 1 || current.bf < -1) {//當節點的BF絕對值大於1時，紀錄該點
                pivot = current;
                if (pivot != root) {
                    pivot_prev = prev;
                }
                //如果不是ROOT，需要追蹤前一個節點，為何需要追蹤請隨便舉例一種簡單的旋轉方式即可
                System.out.printf("PIVOT FIND:%d\n", current.data);
            }
            if (current.bf > 0) {//BF=左-右，大於代表左邊要調整，小於代表左邊要調整
                prev = current;
                current = current.llink;
            } else if (current.bf < 0) {
                prev = current;
                current = current.rlink;
            } else {//當上面情況都不是，代表平衡，讓current隨意向下直到為null結束迴圈
                current = current.llink;
            }
        }
        return pivot;
    }

尋找的方式是從樹根開始找，若BF的值為正數，代表左子點的BF較大，就向左找。若為負數，則向右找。

當該節點的BF絕對值大於1時，則紀錄該節點，並記錄該節點的父節點。如果pivot為null，代表平衡。

旋轉條件

若有一加入的新節點為N，若一距離N最近且平衡因子為+-2的父節點P存在，則四種調整方式的適用時機如下 ：

1. LL：當加入的節點N在節點P的左邊的左邊

2.RR：當加入的節點N在節點P的右邊的右邊

3.LR：當加入的節點N在節點P的左邊的右邊

4.RL：當加入的節點N在節點P的右邊的左邊

調整只需找鄰近的2節點即可。

LL型

LL代表左子樹過重，以下圖為例：

明顯看到在加入20之後，節點50的BF為2，且節點20加入在左方，符合LL型態，其旋轉方式如下：

pivot是與加入節點最近且BF為+-2的節點，pivot_next是要調整的鄰近節點，temp則是要放到右邊的節點

經由下列步驟旋轉

pivot_next.rlink=pivot

pivot.llink=temp

就能調整完成，如下圖所示:

    public void LL() {
        node pivot_next, temp;
        pivot_next = pivot.llink;
        temp = pivot_next.rlink;
        pivot_next.rlink = pivot;
        pivot.llink = temp;
        if (pivot == root) {
            root = pivot_next;
        } else {//判斷pivot是父節點的左還是右子點

            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = pivot_next;
            } else {
                pivot_prev.rlink = pivot_next;
            }

        }
    }

RR型

RR剛好對稱於LL，右子樹過重

加入80之後，50節點的BF為-2，右子樹明顯過重，經過旋轉過後:

關於RR的演算法，就是將LL的演算法左右顛倒即可，不再贅述，請參考程式碼

    public void RR() {
        node temp, pivot_next;
        pivot_next = pivot.rlink;
        temp = pivot_next.llink;
        pivot_next.llink = pivot;
        pivot.rlink = temp;
        if (pivot == root) {
            root = pivot;
        } else {
            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = pivot_next;
            } else {
                pivot_prev.rlink = pivot_next;
            }
        }
    }

LR型

如下圖:

加入42之後，節點50的BF為2，不符合AVL樹定義，調整方式是將45往上提，再將小於45的節點40放在45的左邊，50放在右邊。演算法如下:

pivot.llink=temp.rlink ( 將TEMP的右節點放到右邊)

pivot_next.rlink=temp.llink (將TEMP的左節點放到左邊)

temp.llink=pivot_next

temp.rlink=pivot

    public void LR() {
        node temp, pivot_next;
        pivot_next = pivot.llink;
        temp = pivot_next.rlink;
        pivot.llink = temp.rlink;//將TEMP的右節點放到右邊(就是PIVOT的左鏈結)
        pivot_next.rlink = temp.llink;//將TEMP的左節點放到左邊(就是PIVOTNEXY的右連結)
        temp.rlink = pivot;   //PIVOT_NEXT一定小於PIVOT
        temp.llink = pivot_next;
        if (pivot == root) {
            root = temp;
        } else {
            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = temp;
            } else {
                pivot_prev.rlink = temp;
            }
        }
    }

RL型

RL型與LR型對稱，演算法方面直接左右顛倒即可，直接舉例:

明顯看出50節點的BF為-2，故需旋轉，方法是將55向上提，左邊放較小的50，右邊放較大的60

旋轉後

    public void RL() {
        node temp, pivot_next;
        pivot_next = pivot.rlink;
        temp = pivot_next.llink;
        pivot.rlink = temp.llink;
        pivot_next.llink = temp.rlink;
        temp.rlink = pivot_next;//PIVOT_NEXT一定大於PIVOT
        temp.llink = pivot;
        if (pivot == root) {
            root = temp;
        } else {
            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = temp;
            } else {
                pivot_prev.rlink = temp;
            }
        }

    }

判別型態

介紹完上述四種型態後，實作上如何判別型態呢，如下:

    public int find_type() {
        int op = 0;
        current = pivot;
        for (int i = 0; i < 2; i++) {
            if (current.bf > 0) { //左子樹較高
                current = current.llink;
                if (op == 0) {
                    op += 10;
                } else {
                    op++;
                }
            } else if (current.bf < 0) { //右子樹較高
                current = current.rlink;
                if (op == 0) {
                    op += 20;
                } else {
                    op += 2;
                }
                //11:LL，22:RR，12:LR、22:RR
            }
        }
        return op;
    }

當發現pivot時，代表需要調整。我們從要調整的節點向下尋找鄰近的兩個節點就好，就能判斷型別。

先判斷左子點還是右子點較高，哪邊高就向哪邊尋找，當取完兩個節點後，就可以得知其型別。回傳部分，十位數代表第一個是左還右，個位數則紀錄第二個是左還右。

AVL樹的刪除

AVL樹的刪除與BST相同，不再贅述，請參考該篇文章。依照BST的規則刪除完成後，只要重新計算BF，再判斷是否符合AVL樹的規則並調整即可。請直接參考程式碼

    public void del() {
        int del = input.nextInt();
        node rel=null, rer = null, parent = null;
        node delnode = search(del);
        if (delnode == null) {
            System.out.println("Data not find.");
        } else {
            if (delnode.rlink == null && delnode.llink == null)//刪除樹葉節點
            {
                if (delnode == root) {
                    root = null;
                } else {
                    current = root;
                    while (current != null && current.data != delnode.data) {
                        if (current.rlink.data == delnode.data) {
                            parent = current;
                        }
                        else if (current.llink.data == delnode.data) {
                            parent = current;
                        }
                        if (current.data > delnode.data) {
                            current = current.llink;
                        }
                        else if (current.data < delnode.data) {
                            current = current.rlink;
                        }

                    }
                    if (parent.llink.data == delnode.data) {
                        parent.llink = null;
                    } else {
                        parent.rlink = null;
                    }
                    delnode = null;
                    System.out.println("DEL");
                }
            } else {
                //找尋替代節點-右最小
                current = delnode.rlink;
                while (current != null && current.llink != null) {
                    current = current.llink;
                }
                rer = current;
                //尋找右節點
                if (rer == null) {
                    current = delnode.llink;
                    while (current != null && current.rlink != null) {
                        current = current.rlink;
                    }
                    rel = current;
                }
                //尋找RE父節點
                current = root;
                if (rer != null) {
                    System.out.println(rer.data);
                    int i=0;
                    while (current != null && current.data != rer.data) {
                        i++;
                        if (current.rlink.data == rer.data) {
                            System.out.print("parent Find");
                            parent = current;
                        }else if (current.llink.data == rer.data) {
                            parent = current;
                        }
                        if (current.data > rer.data) {
                            System.out.printf("L %d \n",i);
                            current = current.llink;
                        }else if (current.data < rer.data) {
                            System.out.printf("R %d\n",i);
                            current = current.rlink;
                        }

                    }
                    if(rer.data>parent.data)
                        parent.rlink = rer.rlink;
                    else
                        parent.llink=rer.rlink;
                    delnode.data = rer.data;
                    rer = null;

                } else if (rel != null) {
                    while (current != null && current.data != rel.data) {
                        if (current.llink.data == rel.data) {
                            parent = current;
                        }
                        else if (current.rlink.data == rel.data) {
                            parent = current;
                        }
                        if (current.data > rel.data) {
                            current = current.llink;
                        }
                        else if (current.data < rel.data) {
                            current = current.rlink;
                        }

                    }
                    if(parent.data>rel.data)
                        parent.llink = rel.llink;
                    else
                        parent.rlink=rel.llink;
                    delnode.data = rel.data;
                    rel = null;
                    

                }
                
                System.out.println("DEL");

            }
            bf(root);
            int op = 0;
            pivot = find_pivot();
            if (pivot != null) {
                op = find_type();
                switch (op) {
                    case 11: //LL
                        LL();
                        break;
                    case 12://LR
                        LR();
                        break;
                    case 21://RL
                        RL();
                        break;
                    case 22://RR
                        RR();
                        break;
                }
            }

        }
    }

其他

AVL樹的走訪與搜尋都與BST相同，這裡就不再贅述。

完整程式碼

import java.util.Scanner;

class node {

    int data;
    int bf;
    node llink, rlink;

}

public class avl {

    node ptr, root, current, prev, pivot, pivot_prev;
    Scanner input = new Scanner(System.in);

    public void insert() {

        System.out.println("Input data:");
        int data = input.nextInt();
        if (search(data) == null) {

            node ptr = new node();
            ptr.data = data;
            if (root == null) {
                root = ptr;
                root.bf = 0;
                System.out.println("Data Insert!!!(ROOT)");
            } else if (root != null) {

                current = root;
                while (current != null) {
                    prev = current;
                    if (ptr.data > current.data) {
                        current = current.rlink;
                    } else if (ptr.data < current.data) {
                        current = current.llink;
                    }
                }
                if (ptr.data > prev.data) {
                    prev.rlink = ptr;
                } else if (ptr.data < prev.data) {
                    prev.llink = ptr;
                }
                System.out.println("Data Insert!!!");
                bf(root);//每次插入都重新計算BF
                pivot = find_pivot();//尋找不平衡
                System.out.printf("RETURN PIVOT  %d\n", pivot != null ? pivot.data : 0);
                if (pivot != null) {
                    int op = find_type();
                    switch (op) {

                        case 11: //LL
                            LL();
                            break;
                        case 12://LR
                            LR();
                            break;
                        case 21://RL
                            RL();
                            break;
                        case 22://RR
                            RR();
                            break;

                    }

                }
            }

        } else if (search(data) != null) {
            System.out.println("Data 重複");
        }

    }

    public void del() {
        int del = input.nextInt();
        node rel=null, rer = null, parent = null;
        node delnode = search(del);
        if (delnode == null) {
            System.out.println("Data not find.");
        } else {
            if (delnode.rlink == null && delnode.llink == null)//刪除樹葉節點
            {
                if (delnode == root) {
                    root = null;
                } else {
                    current = root;
                    while (current != null && current.data != delnode.data) {
                        if (current.rlink.data == delnode.data) {
                            parent = current;
                        }
                        else if (current.llink.data == delnode.data) {
                            parent = current;
                        }
                        if (current.data > delnode.data) {
                            current = current.llink;
                        }
                        else if (current.data < delnode.data) {
                            current = current.rlink;
                        }

                    }
                    if (parent.llink.data == delnode.data) {
                        parent.llink = null;
                    } else {
                        parent.rlink = null;
                    }
                    delnode = null;
                    System.out.println("DEL");
                }
            } else {
                //找尋替代節點-右最小
                current = delnode.rlink;
                while (current != null && current.llink != null) {
                    current = current.llink;
                }
                rer = current;
                //尋找右節點
                if (rer == null) {
                    current = delnode.llink;
                    while (current != null && current.rlink != null) {
                        current = current.rlink;
                    }
                    rel = current;
                }
                //尋找RE父節點
                current = root;
                if (rer != null) {
                    System.out.println(rer.data);
                    int i=0;
                    while (current != null && current.data != rer.data) {
                        i++;
                        if (current.rlink.data == rer.data) {
                            System.out.print("parent Find");
                            parent = current;
                        }else if (current.llink.data == rer.data) {
                            parent = current;
                        }
                        if (current.data > rer.data) {
                            System.out.printf("L %d \n",i);
                            current = current.llink;
                        }else if (current.data < rer.data) {
                            System.out.printf("R %d\n",i);
                            current = current.rlink;
                        }

                    }
                    if(rer.data>parent.data)
                        parent.rlink = rer.rlink;
                    else
                        parent.llink=rer.rlink;
                    delnode.data = rer.data;
                    rer = null;

                } else if (rel != null) {
                    while (current != null && current.data != rel.data) {
                        if (current.llink.data == rel.data) {
                            parent = current;
                        }
                        else if (current.rlink.data == rel.data) {
                            parent = current;
                        }
                        if (current.data > rel.data) {
                            current = current.llink;
                        }
                        else if (current.data < rel.data) {
                            current = current.rlink;
                        }

                    }
                    if(parent.data>rel.data)
                        parent.llink = rel.llink;
                    else
                        parent.rlink=rel.llink;
                    delnode.data = rel.data;
                    rel = null;
                    

                }
                
                System.out.println("DEL");

            }
            bf(root);
            int op = 0;
            pivot = find_pivot();
            if (pivot != null) {
                op = find_type();
                switch (op) {
                    case 11: //LL
                        LL();
                        break;
                    case 12://LR
                        LR();
                        break;
                    case 21://RL
                        RL();
                        break;
                    case 22://RR
                        RR();
                        break;
                }
            }

        }
    }

    public void LL() {
        node pivot_next, temp;
        pivot_next = pivot.llink;
        temp = pivot_next.rlink;
        pivot_next.rlink = pivot;
        pivot.llink = temp;
        if (pivot == root) {
            root = pivot_next;
        } else {//判斷pivot是父節點的左還是右子點

            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = pivot_next;
            } else {
                pivot_prev.rlink = pivot_next;
            }

        }
    }

    public void RR() {
        node temp, pivot_next;
        pivot_next = pivot.rlink;
        temp = pivot_next.llink;
        pivot_next.llink = pivot;
        pivot.rlink = temp;
        if (pivot == root) {
            root = pivot;
        } else {
            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = pivot_next;
            } else {
                pivot_prev.rlink = pivot_next;
            }
        }
    }

    public void LR() {
        node temp, pivot_next;
        pivot_next = pivot.llink;
        temp = pivot_next.rlink;
        pivot.llink = temp.rlink;//將TEMP的右節點放到右邊(就是PIVOT的左鏈結)
        pivot_next.rlink = temp.llink;//將TEMP的左節點放到左邊(就是PIVOTNEXY的右連結)
        temp.rlink = pivot;   //PIVOT_NEXT一定小於PIVOT
        temp.llink = pivot_next;
        if (pivot == root) {
            root = temp;
        } else {
            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = temp;
            } else {
                pivot_prev.rlink = temp;
            }
        }
    }

    public void RL() {
        node temp, pivot_next;
        pivot_next = pivot.rlink;
        temp = pivot_next.llink;
        pivot.rlink = temp.llink;
        pivot_next.llink = temp.rlink;
        temp.rlink = pivot_next;//PIVOT_NEXT一定大於PIVOT
        temp.llink = pivot;
        if (pivot == root) {
            root = temp;
        } else {
            if (pivot_prev.llink == pivot) {
                pivot_prev.llink = temp;
            } else {
                pivot_prev.rlink = temp;
            }
        }

    }

    public int find_type() {
        int op = 0;
        current = pivot;
        for (int i = 0; i < 2; i++) {
            if (current.bf > 0) { //左子樹較高
                current = current.llink;
                if (op == 0) {
                    op += 10;
                } else {
                    op++;
                }
            } else if (current.bf < 0) { //右子樹較高
                current = current.rlink;
                if (op == 0) {
                    op += 20;
                } else {
                    op += 2;
                }
                //11:LL，22:RR，12:LR、22:RR
            }
        }
        return op;
    }

    public node find_pivot() {

        current = root;
        pivot = null;
        while (current != null) {
            if (current.bf > 1 || current.bf < -1) {//當節點的BF絕對值大於1時，紀錄該點
                pivot = current;
                if (pivot != root) {
                    pivot_prev = prev;
                }
                //如果不是ROOT，需要追蹤前一個節點，為何需要追蹤請隨便舉例一種簡單的旋轉方式即可
                System.out.printf("PIVOT FIND:%d\n", current.data);
            }
            if (current.bf > 0) {//BF=左-右，大於代表左邊要調整，小於代表左邊要調整
                prev = current;
                current = current.llink;
            } else if (current.bf < 0) {
                prev = current;
                current = current.rlink;
            } else {//當上面情況都不是，代表平衡，讓current隨意向下直到為null結束迴圈
                current = current.llink;
            }
        }
        return pivot;
    }

    public node search(int set) {//搜尋方式與BST相同

        current = root;
        while (current != null) {
            prev = current;
            if (set > current.data) {
                current = current.rlink;
            } else if (set < current.data) {
                current = current.llink;
            } else if (set == current.data) {
                break;
            }
        }
        return current;
    }

    public void bf(node node) {

        if (node != null) {
            //利用後序走訪計算BF

            bf(node.llink);
            bf(node.rlink);
            System.out.printf("NODE LLINK HEI:%d    NODE RLINK HEI:%d   ", height(node.llink), height(node.rlink));
            node.bf = height(node.llink) - height(node.rlink);
            System.out.printf("BF %d\n", node.bf);
        }

    }

    public int height(node node) {

        if (node != null) {
            //當傳入的節點之左右子樹為空時
            if (node.rlink == null && node.llink == null) {
                return 1;
            } else {
                return 1 + (height(node.llink) > height(node.rlink) ? height(node.llink) : height(node.rlink));
            }
            //分別堆疊計算左右子樹高，回傳較大者  
        }
        return 0;

    }

    public void list() {
        if (root != null) {
            inorder(root);
        } else {
            System.out.println("Tree is null!");
        }
    }

    public void inorder(node node) {
        if (node != null) {
            inorder(node.llink);
            System.out.printf("%d ", node.data);
            inorder(node.rlink);
        }
    }

    public static void main(String[] args) {
        avl obj = new avl();
        Scanner input = new Scanner(System.in);
        System.out.println("<1>插入 <2>刪除 <3>印出");
        while (true) {
            int doing = input.nextInt();
            switch (doing) {
                case 1:
                    obj.insert();
                    break;
                case 2:
                    obj.del();
                    break;
                case 3:
                    obj.list();
                    break;
            }
        }
    }

}