快捷導(dǎo)航

Java詳解AVL樹的應(yīng)用

更新時間：2024年02月11日 08:22:07 作者：棟zzzz

AVL樹是高度平衡的二叉樹,它的特點是AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1,本文主要給大家介紹了Java如何實現(xiàn)AVL樹,需要的朋友可以參考下

一.什么是AVL樹

在認(rèn)識AVL樹之前我們先認(rèn)識一下什么是二叉搜索樹:

1.二叉搜索樹

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

類似于這樣的樹就是一棵二叉搜索樹;

2.為什么引入了AVL樹

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

這就相當(dāng)于是一個順序表的查找了,這樣二叉搜索樹的優(yōu)勢就完全消失了,因此就引入了AVL樹!

3.什么是AVL樹

AVL樹又稱自平衡二叉查找樹,是高度平衡的二叉搜索樹,就是在二叉搜索樹的基礎(chǔ)上進行了優(yōu)化,既當(dāng)向二叉搜索樹中插入新結(jié)點后，保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整),也就是降低樹的高度,這樣就可以減少平均搜索長度了,因此AVL樹滿足它的左右子樹都是AVL樹,左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1),這就是AVL樹的優(yōu)勢所在,因此如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結(jié)點，其高度可保持在，搜索時間復(fù)雜度O( l o g 2 n log_2{n} log2?n)!!!

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

二.自己構(gòu)造AVL樹

這里的構(gòu)造還是和二叉搜索樹的構(gòu)造差不多的，只不過在這里插入元素的話就需要考慮平衡因子的事情了，因為一定要保證插入元素后此樹還是一棵AVL樹，就需要進行相關(guān)調(diào)整，這里就先不過多介紹了，下面再詳細介紹，先來構(gòu)造一棵簡單的AVL樹：

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

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

三.AVL樹的插入和刪除

1.插入

首先就是將節(jié)點插進來，和二叉搜索樹一樣，先只看位置在哪，不關(guān)注平衡因子

這個為要插入節(jié)點：

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

此時節(jié)點就已經(jīng)插進來了，此時就需要看其每個節(jié)點的平衡因子了

        //而此時就需要對樹進行平衡因子的調(diào)整了，保證樹是高度平衡的
        //再反著回去寫
        node.parent = parent;
        cur = node;
        //當(dāng)父親節(jié)點一直存在的時候，就表示沒有調(diào)到根節(jié)點就需要繼續(xù)調(diào)整
        while(parent != null){
            if(cur == parent.right){
                //在右邊右樹高度加一，因此bf+1
                parent.bf++;
            }else{
                //再左邊，左樹高度加一，因此bf-1
                parent.bf--;
            }
            //在這里就要進行判斷了，如果此時的父親節(jié)點如果平衡因子為0了，那么就不需要再往上走了，因為上面的都是平衡的
	        if(parent.bf == 0){
	            return true;
	        }else if(parent.bf == -1 || parent.bf == 1){
	            //此時父親節(jié)點的平衡因子為1、-1
	             //此時表示當(dāng)前樹平衡了，但是不表示整棵樹都平衡了，因此還需要繼續(xù)往上走
	            cur = parent;
	            parent = cur.parent;
	        }else{
	            //此時父親節(jié)點的平衡因子為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);
	                }
	            }
	            //調(diào)整完就平衡了
	            break;
	        }
        }

這是當(dāng)前會出現(xiàn)的問題：

先來討論一下調(diào)整平衡因子會出現(xiàn)的一些情況，來分別看一下：

首先是平衡因子調(diào)整為0了，那么就不需要再往上走了，因為上面的都是平衡的，當(dāng)前的父親節(jié)點的平衡因子為0了表示插入的這個元素只影響到了這一棵樹，上面是沒有影響的，因此是0的話就結(jié)束了

因此是0的話就表示當(dāng)前已經(jīng)結(jié)束了，不需要再往上了，其他變?yōu)? 的情況也是一樣的這里就不細畫了

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

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

1.1.右單旋

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

也就是如下的效果：

也就是這樣的調(diào)整過程：

下面寫一下代碼：

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

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

1.2.左單旋

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

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

也就是如下的效果：

也就是這樣的調(diào)整過程：

代碼如下：

private void rotateLeft(TreeNode parent){
        //左單旋
        //此時parent平衡因子為2，cur的平衡因子為1
        //需要記錄父親節(jié)點
        TreeNode pParent = parent.parent;
        TreeNode cur = parent.right;
        //記錄cur的左節(jié)點
        TreeNode curL = cur.left;
        parent.right = curL;
        cur.left = parent;
        //判斷左節(jié)點是不是空的，如果是空的就不需要管了，不是空的就需要將parent右節(jié)點指向它，并且它的父親節(jié)點為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{
            //是根節(jié)點
            root = cur;
            root.parent = null;
        }
        cur.bf = 0;
        parent.bf = 0;
    }

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

1.3.左右雙旋

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

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

上面左單旋和右單旋已經(jīng)介紹過了，這里就不詳細介紹了，

先左旋：

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

再右旋：

兩次旋轉(zhuǎn)之后只需要進行平衡因子的改變就可以了，

通過觀察curR的平衡因子，會決定最后其他節(jié)點的平衡因子

代碼如下：

private void rotateLR(TreeNode parent){
        //左右雙旋
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        //此時就需要看curR的平衡因子，再決定最后其他節(jié)點的平衡因子
        int bf = curR.bf;
        //先調(diào)用左旋再右旋
        rotateLeft(cur);
        rotateRight(parent);
        //這里通過規(guī)律可以得到當(dāng)curR的bf值不同的時候，其需要改變的bf值也是不同的，因此里就需要做出修改
        if(bf == -1){
            //當(dāng)bf為-1時，其應(yīng)修改的如下
            curR.bf = 0;
            cur.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            //當(dāng)bf為1時，其應(yīng)修改的如下
            curR.bf = 0;
            cur.bf = -1;
            parent.bf = 0;
        }
        //另外當(dāng)bf為0的時候就已經(jīng)平衡了，就不需要改了，因為在兩次旋轉(zhuǎn)的時候就已經(jīng)將其改為0了
    }

這樣一個左右雙旋就結(jié)束了~

1.4.右左雙旋

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

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

先右旋：

再左旋：

通過觀察發(fā)現(xiàn)其需要改變的平衡因子和curL有關(guān)系：

因此

代碼如下：

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