快捷導(dǎo)航

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

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

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

一.什么是AVL樹(shù)

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

1.二叉搜索樹(shù)

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

類(lèi)似于這樣的樹(shù)就是一棵二叉搜索樹(shù);

2.為什么引入了AVL樹(shù)

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

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

3.什么是AVL樹(shù)

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

平衡因子 = 右子樹(shù)的高度 - 左子樹(shù)的高度

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

這里的構(gòu)造還是和二叉搜索樹(shù)的構(gòu)造差不多的，只不過(guò)在這里插入元素的話(huà)就需要考慮平衡因子的事情了，因?yàn)橐欢ㄒＷC插入元素后此樹(shù)還是一棵AVL樹(shù)，就需要進(jìn)行相關(guān)調(diào)整，這里就先不過(guò)多介紹了，下面再詳細(xì)介紹，先來(lái)構(gòu)造一棵簡(jiǎn)單的AVL樹(shù)：

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

這樣一棵簡(jiǎn)單的AVL樹(shù)就構(gòu)造好了，下面就來(lái)寫(xiě)一下AVL樹(shù)的插入！

三.AVL樹(shù)的插入和刪除

1.插入

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

這個(gè)為要插入節(jié)點(diǎn)：

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

此時(shí)節(jié)點(diǎn)就已經(jīng)插進(jìn)來(lái)了，此時(shí)就需要看其每個(gè)節(jié)點(diǎn)的平衡因子了

        //而此時(shí)就需要對(duì)樹(shù)進(jìn)行平衡因子的調(diào)整了，保證樹(shù)是高度平衡的
        //再反著回去寫(xiě)
        node.parent = parent;
        cur = node;
        //當(dāng)父親節(jié)點(diǎn)一直存在的時(shí)候，就表示沒(méi)有調(diào)到根節(jié)點(diǎn)就需要繼續(xù)調(diào)整
        while(parent != null){
            if(cur == parent.right){
                //在右邊右樹(shù)高度加一，因此bf+1
                parent.bf++;
            }else{
                //再左邊，左樹(shù)高度加一，因此bf-1
                parent.bf--;
            }
            //在這里就要進(jìn)行判斷了，如果此時(shí)的父親節(jié)點(diǎn)如果平衡因子為0了，那么就不需要再往上走了，因?yàn)樯厦娴亩际瞧胶獾?
	        if(parent.bf == 0){
	            return true;
	        }else if(parent.bf == -1 || parent.bf == 1){
	            //此時(shí)父親節(jié)點(diǎn)的平衡因子為1、-1
	             //此時(shí)表示當(dāng)前樹(shù)平衡了，但是不表示整棵樹(shù)都平衡了，因此還需要繼續(xù)往上走
	            cur = parent;
	            parent = cur.parent;
	        }else{
	            //此時(shí)父親節(jié)點(diǎn)的平衡因子為2、-2
	            if(parent.bf == 2){
                //此時(shí)右樹(shù)高 需要降低右樹(shù)的高度
	                if(cur.bf == 1){
	                    //左單旋
	                    rotateLeft(parent);
	                }else{
	                    //右左雙旋
	                    rotateRL(parent);
	                }
	            }else{
	                //此時(shí)左樹(shù)高，需要降低左樹(shù)的高度
	                if(cur.bf == 1){
	                    //左右雙旋
	                    rotateLR(parent);
	                }else{
	                    //右單旋
	                    rotateRight(parent);
	                }
	            }
	            //調(diào)整完就平衡了
	            break;
	        }
        }

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

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

首先是平衡因子調(diào)整為0了，那么就不需要再往上走了，因?yàn)樯厦娴亩际瞧胶獾?，?dāng)前的父親節(jié)點(diǎn)的平衡因子為0了表示插入的這個(gè)元素只影響到了這一棵樹(shù)，上面是沒(méi)有影響的，因此是0的話(huà)就結(jié)束了

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

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

而如果是2或者-2的話(huà)，會(huì)以下四種情況，再來(lái)分別看一下：

1.1.右單旋

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

也就是如下的效果：

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

下面寫(xiě)一下代碼：

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

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

1.2.左單旋

這種情況就是最開(kāi)始的情況了

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

也就是如下的效果：

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

代碼如下：

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

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

1.3.左右雙旋

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

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

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

先左旋：

此時(shí)修改的平衡因子是沒(méi)有用的

再右旋：

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

通過(guò)觀察curR的平衡因子，會(huì)決定最后其他節(jié)點(diǎn)的平衡因子

代碼如下：

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

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

1.4.右左雙旋

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

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

先右旋：

再左旋：

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

因此

代碼如下：

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

2.刪除

刪除和上面的插入是差不多的，由于AVL樹(shù)也是二叉搜索樹(shù)，可按照二叉搜索樹(shù)的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不過(guò)與刪除不同的是，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。

具體步驟：