Java詳解AVL樹的應用

2022-07-11 14:00:29

一.什麼是AVL樹

在認識AVL樹之前我們先認識一下什麼是二元搜尋樹:

1.二元搜尋樹

二元搜尋樹又稱為二叉排序樹,二元搜尋樹滿足所有的左孩子節點都小於其根節點的值,所有的右孩子節點都大於其根節點的值,二元搜尋樹上的每一棵子樹都是一棵二元搜尋樹,因此二元搜尋樹通過中序遍歷可以獲得一個有序的序列(由小到大);

類似於這樣的樹就是一棵二元搜尋樹;

2.為什麼引入了AVL樹

二元搜尋樹看似很美好,但其卻有一些缺陷.對於二元搜尋樹而言,是和查詢相關的，而不論是查詢還是刪除,都需要先進行查詢,也就是對整棵樹來進行遍歷,而對有n個結點的二元搜尋樹，若每個元素查詢的概率相等，則二元搜尋樹平均查詢長度是結點在二元搜尋樹的深度函數,也就是結點越深，則比較次數越多.最優的情況下是：二元搜尋樹為完全二元樹，其平均比較次數為： l o g 2 n log_2{n} log2n,但是如果二元搜尋樹退化成了一棵單分支的樹,其平均比較次數為：n/2,就是最差的情況了

這就相當於是一個順序表的查詢了,這樣二元搜尋樹的優勢就完全消失了,因此就引入了AVL樹!

3.什麼是AVL樹

AVL樹又稱自平衡二叉查詢樹,是高度平衡的二元搜尋樹,就是在二元搜尋樹的基礎上進行了優化,既當向二元搜尋樹中插入新結點後，保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整),也就是降低樹的高度,這樣就可以減少平均搜尋長度了,因此AVL樹滿足它的左右子樹都是AVL樹,左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1),這就是AVL樹的優勢所在,因此如果一棵二元搜尋樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在，搜尋時間複雜度O( l o g 2 n log_2{n} log2n)!!!

平衡因子 = 右子樹的高度 - 左子樹的高度

二.自己構造AVL樹

這裡的構造還是和二元搜尋樹的構造差不多的，只不過在這裡插入元素的話就需要考慮平衡因子的事情了，因為一定要保證插入元素後此樹還是一棵AVL樹，就需要進行相關調整，這裡就先不過多介紹了，下面再詳細介紹，先來構造一棵簡單的AVL樹：

public class AVLTree {
    static class TreeNode{
        //內部類，表示AVL樹的每個節點
        //val值
        public int val;
        //左孩子的參照
        public TreeNode left;
        //右孩子的參照
        public TreeNode right;
        //父親節點的參照
        public TreeNode parent;
        //平衡因子(每個節點都有）
        public int bf;
        public TreeNode(int val){
            this.val = val;
        }
    }
    //根節點
    public TreeNode root;
    public boolean insert(int val){
    }
}

這樣一棵簡單的AVL樹就構造好了，下面就來寫一下AVL樹的插入！

三.AVL樹的插入和刪除

1.插入

首先就是將節點插進來，和二元搜尋樹一樣，先只看位置在哪，不關注平衡因子

這個為要插入節點：

   TreeNode node = new TreeNode(val);
        if(root == null){
            //沒有根節點，要插入的就是根節點
            root = node;
            return true;
        }
        //記錄每個節點的父節點
        TreeNode parent = null;
        //要移動的代節點
        TreeNode cur = root;
        //根據val的值和root進行比較來確定應該插入節點的位置
        while (cur != null){
            if(cur.val > val){
                //大於證明此節點應在左子樹
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                //大於證明此節點應在右子樹
                parent = cur;
                cur = cur.right;
            }else {
                //不能有值一樣的節點
                return false;
            }
        }
        //此時cur為空，需要找到對應的位置
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node;
        }

此時節點就已經插進來了，此時就需要看其每個節點的平衡因子了

        //而此時就需要對樹進行平衡因子的調整了，保證樹是高度平衡的
        //再反著回去寫
        node.parent = parent;
        cur = node;
        //當父親節點一直存在的時候，就表示沒有調到根節點就需要繼續調整
        while(parent != null){
            if(cur == parent.right){
                //在右邊右樹高度加一，因此bf+1
                parent.bf++;
            }else{
                //再左邊，左樹高度加一，因此bf-1
                parent.bf--;
            }
            //在這裡就要進行判斷了，如果此時的父親節點如果平衡因子為0了，那麼就不需要再往上走了，因為上面的都是平衡的
	        if(parent.bf == 0){
	            return true;
	        }else if(parent.bf == -1 || parent.bf == 1){
	            //此時父親節點的平衡因子為1、-1
	             //此時表示當前樹平衡了，但是不表示整棵樹都平衡了，因此還需要繼續往上走
	            cur = parent;
	            parent = cur.parent;
	        }else{
	            //此時父親節點的平衡因子為2、-2
	            if(parent.bf == 2){
                //此時右樹高 需要降低右樹的高度
	                if(cur.bf == 1){
	                    //左單旋
	                    rotateLeft(parent);
	                }else{
	                    //右左雙旋
	                    rotateRL(parent);
	                }
	            }else{
	                //此時左樹高，需要降低左樹的高度
	                if(cur.bf == 1){
	                    //左右雙旋
	                    rotateLR(parent);
	                }else{
	                    //右單旋
	                    rotateRight(parent);
	                }
	            }
	            //調整完就平衡了
	            break;
	        }
        }

這是當前會出現的問題：

先來討論一下調整平衡因子會出現的一些情況，來分別看一下：

首先是平衡因子調整為0了，那麼就不需要再往上走了，因為上面的都是平衡的，當前的父親節點的平衡因子為0了表示插入的這個元素隻影響到了這一棵樹，上面是沒有影響的，因此是0的話就結束了

因此是0的話就表示當前已經結束了，不需要再往上了，其他變為0 的情況也是一樣的這裡就不細畫了

而如果是1或者-1的話，表示當前樹平衡了，但是不表示整棵樹平衡了，因此需要再往上走；

而如果是2或者-2的話，會以下四種情況，再來分別看一下：

1.1.右單旋

此時左樹高，需要降低左樹的高度，也就是右旋（parent.bf = -2,cur.bf = -1）：

也就是如下的效果：

也就是這樣的調整過程：

下面寫一下程式碼：

private void rotateRight(TreeNode parent){
        //右單旋
        //此時parent的平衡因子為-2，cur的平衡因子為-1
        TreeNode cur = parent.left;
        //記錄cur的右節點
        TreeNode curR = cur.right;
        parent.left = curR;
        cur.right = parent;
        //如果cur有右節點需要賦給parent的左節點，但是沒有就不需要給了
        if(curR != null){
            curR.parent = parent;
        }
        //然後將cur的右孩子改變為parent
        //需要記錄parent的根節點
        TreeNode pParent = parent.parent;
        parent.parent = cur;
        //檢查當前是不是根節點，不是根節點需要看是左子樹，還是右子樹
        if(pParent != null){
            //改變之前的指向
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //此時parent就是root，因為沒有根節點
            root = cur;
            root.parent = null;
        }
        //最後記得一定要修改平衡因子
        parent.bf = 0;
        cur.bf = 0;
    }

這樣一個“簡單”的右單旋就結束了~

1.2.左單旋

這種情況就是最開始的情況了

此時右樹高，需要降低右樹的高度，也就是左旋（parent.bf = 2,cur.bf = 1）：

也就是如下的效果：

也就是這樣的調整過程：

程式碼如下：

private void rotateLeft(TreeNode parent){
        //左單旋
        //此時parent平衡因子為2，cur的平衡因子為1
        //需要記錄父親節點
        TreeNode pParent = parent.parent;
        TreeNode cur = parent.right;
        //記錄cur的左節點
        TreeNode curL = cur.left;
        parent.right = curL;
        cur.left = parent;
        //判斷左節點是不是空的，如果是空的就不需要管了，不是空的就需要將parent右節點指向它，並且它的父親節點為parent
        if(curL != null){
            //改變指向
            curL.parent = parent;
        }
        //改變cur的指向
        parent.parent = cur;
        //判斷如果pParent不為空，就表示parent不是root，就需要看其是左孩子還是右孩子
        if(pParent != null){
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //是根節點
            root = cur;
            root.parent = null;
        }
        cur.bf = 0;
        parent.bf = 0;
    }

這樣一個“簡單”的左單旋就結束了~

1.3.左右雙旋

此時左樹高，需要降低左樹的高度，（parent.bf = -2,cur.bf = 1）：

而此時僅通過單旋是無法完成的，需要通過兩種旋轉才能完成：

上面左單旋和右單旋已經介紹過了，這裡就不詳細介紹了，

先左旋：

此時修改的平衡因子是沒有用的

再右旋：

兩次旋轉之後只需要進行平衡因子的改變就可以了，

通過觀察curR的平衡因子，會決定最後其他節點的平衡因子

程式碼如下：

private void rotateLR(TreeNode parent){
        //左右雙旋
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        //此時就需要看curR的平衡因子，再決定最後其他節點的平衡因子
        int bf = curR.bf;
        //先呼叫左旋再右旋
        rotateLeft(cur);
        rotateRight(parent);
        //這裡通過規律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此裡就需要做出修改
        if(bf == -1){
            //當bf為-1時，其應修改的如下
            curR.bf = 0;
            cur.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            //當bf為1時，其應修改的如下
            curR.bf = 0;
            cur.bf = -1;
            parent.bf = 0;
        }
        //另外當bf為0的時候就已經平衡了，就不需要改了，因為在兩次旋轉的時候就已經將其改為0了
    }

這樣一個左右雙旋就結束了~

1.4.右左雙旋

此時右樹高，需要降低右樹的高度（parent.bf = 2,cur.bf = -1）：

而此時僅通過單旋是無法完成的，需要通過兩種旋轉才能完成：

先右旋：

再左旋：

通過觀察發現其需要改變的平衡因子和curL有關係：

因此

程式碼如下：

  private void rotateRL(TreeNode parent) {
        //右左雙旋
        TreeNode cur = parent.right;
        TreeNode curL = cur.left;
        //此時就需要看curL的平衡因子了，再決定最後其他節點的平衡因子
        int bf = curL.bf;
        rotateRight(cur);
        rotateLeft(parent);
        //這裡通過規律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此裡就需要做出修改
        if(bf == -1){
            //當bf為-1時，其應修改的如下
            parent.bf = 0;
            cur.bf = 0;
            curL.bf = 1;
        }else if(bf == 1){
            //當bf為1時，其應修改的如下
            parent.bf = -1;
            curL.bf = 0;
            cur.bf = 0;
        }
        //另外當bf為0的時候就已經平衡了，就不需要改了，因為在兩次旋轉的時候就已經將其改為0了
    }