怎么理解并掌握Java的AVL樹

這篇文章主要介紹“怎么理解并掌握Java的AVL樹”，在日常操作中，相信很多人在怎么理解并掌握Java的AVL樹問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么理解并掌握Java的AVL樹”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

一、摘要

在上篇文章，我們詳細的介紹了二叉樹的算法以及代碼實踐，我們知道不同的二叉樹形態結構，對查詢效率也會有很大的影響，尤其是當樹的形態結構變成一個鏈條結構的時候，查詢最后一個元素的效率極底，如何解決這個問題呢?

關鍵在于如何最大限度的減小樹的深度，從而提高查詢效率，正是基于這一點，平衡二叉查找樹出現了!

平衡二叉查找樹，算法由Adel'son-Vel'skii和 Landis兩位大神發明，同時也俗稱AVL 樹，來自兩位大神的姓名縮寫，特性如下：

• 它的左子樹和右子樹都是平衡二叉樹;

• 且它的左子樹和右子樹的深度之差的絕對值(平衡因子 ) 不超過1;

簡單的說，就是為了保證平衡，當前節點的左子樹、右子樹的高度差不超過1!

廢話也不多說了，直奔主題，算法思路如下!

二、算法思路

平衡二叉查找樹的查找思路，與二叉樹是一樣，每次查詢的時候對半分，只查詢一部分，以達到提供效率的目的，插入、刪除也一樣，最大的不同點：每次插入或者刪除之后，需要計算節點高度，然后按需進行調整!

如何調整呢?主要方法有：左旋轉、右旋轉!

下面我們分別來分析一下插入、刪除的場景調整。

2.1、插入場景

我們來分析一下插入的場景，如下：

場景一

當我們在40的左邊或者右邊插入的時候，也就是50的左邊，只需繞80進行右旋轉，即可達到樹高度差不超過1!

場景二

當我們在60的左邊或者右邊插入的時候，也就是50的右邊，需要進行兩次旋轉，先會繞50左旋轉一次，再繞80右旋轉一次，即可達到樹高度差不超過1!

場景三

當我們在120的左邊或者右邊插入的時候，也就是90的右邊，只需繞80進行左旋轉，即可達到樹高度差不超過1!

場景四

當我們在85的左邊或者右邊插入的時候，也就是90的左邊，需要進行兩次旋轉，先會繞90右旋轉一次，再繞80左旋轉一次，即可達到樹高度差不超過1!

總結

對于插入這種操作，總共其實只有這四種類型的插入，即：單次左旋轉、單次右旋轉、左旋轉-右旋轉、右旋轉-左旋轉，總結如下：

• 當插入節點位于需要旋轉節點的左節點的左子樹時，只需右旋轉;

• 當插入節點位于需要旋轉節點的左節點的右子樹時，需要左旋轉-右旋轉;

• 當插入節點位于需要旋轉節點的右節點的右子樹時，只需左旋轉;

• 當插入節點位于需要旋轉節點的右節點的左子樹時，需要右旋轉-左旋轉;

2.2、刪除場景

接下來，我們分析一下刪除場景!

其實，刪除場景跟二叉樹的刪除思路是一樣的，不同的是需要調整，刪除的節點所在樹，需要層層判斷節點的高度差是否大于1，如果大于1，就進行左旋轉或者右旋轉!

場景一

當刪除的節點，只有左子樹時，直接將左子樹轉移到上層即可!

場景二

當刪除的節點，只有右子樹時，直接將右子樹轉移到上層即可!

場景三

當刪除的節點，有左、右子樹時，因為當前節點的左子樹的最末端的右子樹或者當前節點的右子樹的最末端的左子樹，最接近當前節點，找到其中任意一個，然后將其內容替換并移除最末端節點，即可實現刪除!

總結

第三種場景稍微復雜了一些，但基本都是這么一個套路，與二叉樹不同的是，刪除之后需要判斷樹高，對超過1的進行調整，類似上面插入的左旋轉、右旋轉操作!

三、代碼實踐

接下來，我們從代碼層面來定義一下樹的實體結構，如下：

1public class AVLNode<E extends Comparable<E>> {  2  3    /**節點關鍵字*/  4    E key;  5  6    /**當前節點樹高*/  7    int height;  8  9    /**當前節點的左子節點*/ 10    AVLNode<E> lChild = null; 11 12    /**當前節點的右子節點*/ 13    AVLNode<E> rChild = null; 14 15    public AVLNode(E key) { 16        this.key = key; 17    } 18 19    @Override 20    public String toString() { 21        return "AVLNode{" + 22                "key=" + key + 23                ", height=" + height + 24                ", lChild=" + lChild + 25                ", rChild=" + rChild + 26                '}'; 27    } 28}

我們創建一個算法類AVLSolution，完整實現如下：

  1public class AVLSolution<E extends Comparable<E>> {   2   3    /**定義根節點*/   4    public AVLNode<E> root = null;   5   6    /**   7     * 插入   8     * @param key   9     */  10    public void insert(E key){  11        System.out.println("插入[" + key + "]:");  12        root = insertAVL(key,root);  13    }  14  15    private AVLNode insertAVL(E key, AVLNode<E> node){  16        if(node == null){  17            return new AVLNode<E>(key);  18        }  19        //左子樹搜索  20        if(key.compareTo(node.key) < 0){  21            //當前節點左子樹不為空,繼續遞歸向下搜索  22            node.lChild = insertAVL(key,node.lChild);  23            //出現不平衡，只會是左子樹比右子樹高，大于1的時候，就進行調整  24            if(getHeight(node.lChild) - getHeight(node.rChild) == 2){  25                if(key.compareTo(node.lChild.key) < 0){  26                    //如果插入的節點位于當前節點的左節點的左子樹，進行單次右旋轉  27                    node = rotateRight(node);  28                }else{  29                    //如果插入的節點位于當前節點的左節點的右子樹，先左旋轉再右旋轉  30                    node = rotateLeftRight(node);  31                }  32            }  33        }else if(key.compareTo(node.key) > 0){  34            //當前節點右子樹不為空,繼續遞歸向下搜索  35            node.rChild = insertAVL(key,node.rChild);  36            //出現不平衡，只會是右子樹比左子樹高，大于1的時候，就進行調整  37            if(getHeight(node.rChild) - getHeight(node.lChild) == 2){  38                if(key.compareTo(node.rChild.key) < 0){  39                    //如果插入的節點位于當前節點的右節點的左子樹，先右旋轉再左旋轉  40                    node = rotateRightLeft(node);  41                }else{  42                    //如果插入的節點位于當前節點的右節點的右子樹，進行單次左旋轉  43                    node = rotateLeft(node);  44                }  45            }  46        } else{  47            //key已經存在，直接返回  48        }  49        //因為節點插入，樹高發生變化，更新節點高度  50        node.height = updateHeight(node);  51        return node;  52    }  53  54    /**  55     * 刪除  56     * @param key  57     */  58    public void delete(E key){  59        root = deleteAVL(key,root);  60    }  61  62    private AVLNode deleteAVL(E key, AVLNode<E> node){  63        if(node == null){  64            return null;  65        }  66        if(key.compareTo(node.key) < 0){  67            //左子樹查找  68            node.lChild = deleteAVL(key,node.lChild);  69            //可能會出現，右子樹比左子樹高2  70            if (getHeight(node.rChild) - getHeight(node.lChild) == 2){  71                node = rotateLeft(node);  72            }  73        } else if(key.compareTo(node.key) > 0){  74            //右子樹查找  75            node.rChild = deleteAVL(key, node.rChild);  76            //可能會出現，左子樹比右子樹高2  77            if (getHeight(node.lChild) - getHeight(node.rChild) == 2){  78                node = rotateRight(node);  79            }  80        }else{  81            //找到目標元素，刪除分三種情況  82            //1.當前節點沒有左子樹，直接返回當前節點右子樹  83            //2.當前節點沒有右子樹，直接返回當前節點右子樹  84            //3.當前節點有左子樹、右子樹的時候，尋找當前節點的右子樹的最末端的左子樹，進行替換和移除  85            if(node.lChild == null){  86                return node.rChild;  87            }  88            if(node.rChild == null){  89                return node.lChild;  90            }  91            //找到當前節點的右子樹的最末端的左子樹，也就是右子樹最小節點  92            AVLNode<E> minLChild = searchDeleteMin(node.rChild);  93            //刪除最小節點，如果高度變化，進行調整  94            minLChild.rChild = deleteMin(node.rChild);  95            minLChild.lChild = node.lChild;//將當前節點的左子樹轉移到最小節點上  96  97            node = minLChild;//覆蓋當前節點  98            //因為是右子樹發生高度變低，因此可能需要調整  99            if(getHeight(node.lChild) - getHeight(node.rChild) == 2){ 100                node = rotateRight(node); 101            } 102        } 103        node.height = updateHeight(node); 104        return node; 105    } 106 107    /** 108     * 搜索 109     * @param key 110     * @return 111     */ 112    public AVLNode<E> search(E key){ 113        return searchAVL(key, root); 114    } 115 116    private AVLNode<E> searchAVL(E key, AVLNode<E> node){ 117        if(node == null){ 118            return null; 119        } 120        //左子樹搜索 121        if(key.compareTo(node.key) < 0){ 122            return searchAVL(key, node.lChild); 123        }else if(key.compareTo(node.key) > 0){ 124            return searchAVL(key, node.rChild); 125        } else{ 126            //key已經存在，直接返回 127            return node; 128        } 129    }  130 131    /** 132     * 查找需要刪除的元素 133     * @param node 134     * @return 135     */ 136    private AVLNode<E> searchDeleteMin(AVLNode<E> node){ 137        if (node == null){ 138            return null; 139        } 140        while (node.lChild != null){ 141            node = node.lChild; 142        } 143        return node; 144    } 145 146    /** 147     * 刪除元素 148     * @param node 149     * @return 150     */ 151    private AVLNode<E> deleteMin(AVLNode<E> node){ 152        if(node == null){ 153            return null; 154        } 155        if (node.lChild == null){ 156            return node.rChild; 157        } 158        //移除最小節點 159        node.lChild = deleteMin(node.lChild); 160        //此時移除的是左節點，判斷是否平衡高度被破壞 161        if(getHeight(node.rChild) - getHeight(node.lChild) == 2){ 162            //進行調整 163            node = rotateLeft(node); 164        } 165        return node; 166 167    } 168 169    /** 170     * 單次左旋轉 171     * @param node 172     * @return 173     */ 174    private AVLNode<E> rotateLeft(AVLNode<E> node){ 175        System.out.println("節點：" + node.key + "，單次左旋轉"); 176        AVLNode<E> x = node.rChild;//獲取旋轉節點的右節點 177        node.rChild = x.lChild;//將旋轉節點的右節點的左節點轉移，作為旋轉節點的右子樹 178        x.lChild = node;//將旋轉節點作為旋轉節點的右子樹的左子樹 179 180        //更新調整節點高度(先調整旋轉節點node) 181        node.height = updateHeight(node); 182        x.height = updateHeight(x); 183        return x; 184    } 185 186    /** 187     * 單次右旋轉 188     * @return 189     */ 190    private AVLNode<E> rotateRight(AVLNode<E> node){ 191        System.out.println("節點：" + node.key + "，單次右旋轉"); 192        AVLNode<E> x = node.lChild;//獲取旋轉節點的左節點 193        node.lChild = x.rChild;//將旋轉節點的左節點的右節點轉移，作為旋轉節點的左子樹 194        x.rChild = node;//將旋轉節點作為旋轉節點的左子樹的右子樹 195 196        //更新調整節點高度(先調整旋轉節點node) 197        node.height = updateHeight(node); 198        x.height = updateHeight(x); 199        return x; 200    } 201 202    /** 203     * 左旋轉-右旋轉 204     * @param node 205     * @return 206     */ 207    private AVLNode<E> rotateLeftRight(AVLNode<E> node){ 208        System.out.println("節點：" + node.key + "，左旋轉-右旋轉"); 209        //先對當前節點的左節點進行左旋轉 210        node.lChild = rotateLeft(node.lChild); 211        //再對當前節點進行右旋轉 212        return rotateRight(node); 213    } 214 215    /** 216     * 右旋轉-左旋轉 217     * @param node 218     * @return 219     */ 220    private AVLNode<E> rotateRightLeft(AVLNode<E> node){ 221        System.out.println("節點：" + node.key + "，右旋轉-左旋轉"); 222        //先對當前節點的右節點進行右旋轉 223        node.rChild = rotateRight(node.rChild); 224        return rotateLeft(node); 225 226    } 227 228    /** 229     * 獲取節點高度，如果為空，等于-1 230     * @param node 231     * @return 232     */ 233    private int getHeight(AVLNode<E> node){ 234        return node != null ? node.height: -1; 235    } 236 237    /** 238     * 更新節點高度 239     * @param node 240     * @return 241     */ 242    private int updateHeight(AVLNode<E> node){ 243        //比較當前節點左子樹、右子樹高度，獲取節點高度 244        return Math.max(getHeight(node.lChild), getHeight(node.rChild)) + 1; 245    } 246 247    /** 248     * 前序遍歷 249     * @param node 250     */ 251    public void frontTreeIterator(AVLNode<E> node){ 252        if(node != null){ 253            System.out.println("key:" + node.key); 254            frontTreeIterator(node.lChild);//遍歷當前節點左子樹 255            frontTreeIterator(node.rChild);//遍歷當前節點右子樹 256        } 257    } 258 259    /** 260     * 中序遍歷 261     * @param node 262     */ 263    public void middleTreeIterator(AVLNode<E> node){ 264        if(node != null){ 265            middleTreeIterator(node.lChild);//遍歷當前節點左子樹 266            System.out.println("key:" + node.key); 267            middleTreeIterator(node.rChild);//遍歷當前節點右子樹 268        } 269    } 270 271    /** 272     * 后序遍歷 273     * @param node 274     */ 275    public void backTreeIterator(AVLNode<E> node){ 276        if(node != null){ 277            backTreeIterator(node.lChild);//遍歷當前節點左子樹 278            backTreeIterator(node.rChild);//遍歷當前節點右子樹 279            System.out.println("key:" + node.key); 280        } 281    } 282 283}

測試代碼，如下：

1public class AVLClient {  2  3    public static void main(String[] args) {  4        //創建一個Integer型的數據結構  5        AVLSolution<Integer> avlTree = new AVLSolution<Integer>();  6  7        //插入節點  8        System.out.println("========插入元素========");  9        avlTree.insert(new Integer(100)); 10        avlTree.insert(new Integer(85)); 11        avlTree.insert(new Integer(120)); 12        avlTree.insert(new Integer(60)); 13        avlTree.insert(new Integer(90)); 14        avlTree.insert(new Integer(80)); 15        avlTree.insert(new Integer(130)); 16        System.out.println("========中序遍歷元素========"); 17 18        //中序遍歷 19        avlTree.middleTreeIterator(avlTree.root); 20        System.out.println("========查找key為100的元素========"); 21 22        //查詢節點 23        AVLNode<Integer> searchResult = avlTree.search(120); 24        System.out.println("查找結果：" + searchResult); 25        System.out.println("========刪除key為90的元素========"); 26 27        //刪除節點 28        avlTree.delete(90); 29        System.out.println("========再次中序遍歷元素========"); 30 31        //中序遍歷 32        avlTree.middleTreeIterator(avlTree.root); 33    } 34}

輸出結果如下：

到此，關于“怎么理解并掌握Java的AVL樹”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！