怎么理解并掌握J(rèn)ava的AVL樹(shù)

這篇文章主要介紹“怎么理解并掌握J(rèn)ava的AVL樹(shù)”，在日常操作中，相信很多人在怎么理解并掌握J(rèn)ava的AVL樹(shù)問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”怎么理解并掌握J(rèn)ava的AVL樹(shù)”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

一、摘要

在上篇文章，我們?cè)敿?xì)的介紹了二叉樹(shù)的算法以及代碼實(shí)踐，我們知道不同的二叉樹(shù)形態(tài)結(jié)構(gòu)，對(duì)查詢效率也會(huì)有很大的影響，尤其是當(dāng)樹(shù)的形態(tài)結(jié)構(gòu)變成一個(gè)鏈條結(jié)構(gòu)的時(shí)候，查詢最后一個(gè)元素的效率極底，如何解決這個(gè)問(wèn)題呢?

關(guān)鍵在于如何最大限度的減小樹(shù)的深度，從而提高查詢效率，正是基于這一點(diǎn)，平衡二叉查找樹(shù)出現(xiàn)了!

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

• 它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù);

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

簡(jiǎn)單的說(shuō)，就是為了保證平衡，當(dāng)前節(jié)點(diǎn)的左子樹(shù)、右子樹(shù)的高度差不超過(guò)1!

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

二、算法思路

平衡二叉查找樹(shù)的查找思路，與二叉樹(shù)是一樣，每次查詢的時(shí)候?qū)Π敕?，只查詢一部分，以達(dá)到提供效率的目的，插入、刪除也一樣，最大的不同點(diǎn)：每次插入或者刪除之后，需要計(jì)算節(jié)點(diǎn)高度，然后按需進(jìn)行調(diào)整!

如何調(diào)整呢?主要方法有：左旋轉(zhuǎn)、右旋轉(zhuǎn)!

下面我們分別來(lái)分析一下插入、刪除的場(chǎng)景調(diào)整。

2.1、插入場(chǎng)景

我們來(lái)分析一下插入的場(chǎng)景，如下：

場(chǎng)景一

當(dāng)我們?cè)?0的左邊或者右邊插入的時(shí)候，也就是50的左邊，只需繞80進(jìn)行右旋轉(zhuǎn)，即可達(dá)到樹(shù)高度差不超過(guò)1!

場(chǎng)景二

當(dāng)我們?cè)?0的左邊或者右邊插入的時(shí)候，也就是50的右邊，需要進(jìn)行兩次旋轉(zhuǎn)，先會(huì)繞50左旋轉(zhuǎn)一次，再繞80右旋轉(zhuǎn)一次，即可達(dá)到樹(shù)高度差不超過(guò)1!

場(chǎng)景三

當(dāng)我們?cè)?20的左邊或者右邊插入的時(shí)候，也就是90的右邊，只需繞80進(jìn)行左旋轉(zhuǎn)，即可達(dá)到樹(shù)高度差不超過(guò)1!

場(chǎng)景四

當(dāng)我們?cè)?5的左邊或者右邊插入的時(shí)候，也就是90的左邊，需要進(jìn)行兩次旋轉(zhuǎn)，先會(huì)繞90右旋轉(zhuǎn)一次，再繞80左旋轉(zhuǎn)一次，即可達(dá)到樹(shù)高度差不超過(guò)1!

總結(jié)

對(duì)于插入這種操作，總共其實(shí)只有這四種類型的插入，即：?jiǎn)未巫笮D(zhuǎn)、單次右旋轉(zhuǎn)、左旋轉(zhuǎn)-右旋轉(zhuǎn)、右旋轉(zhuǎn)-左旋轉(zhuǎn)，總結(jié)如下：

• 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的左節(jié)點(diǎn)的左子樹(shù)時(shí)，只需右旋轉(zhuǎn);

• 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的左節(jié)點(diǎn)的右子樹(shù)時(shí)，需要左旋轉(zhuǎn)-右旋轉(zhuǎn);

• 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的右節(jié)點(diǎn)的右子樹(shù)時(shí)，只需左旋轉(zhuǎn);

• 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的右節(jié)點(diǎn)的左子樹(shù)時(shí)，需要右旋轉(zhuǎn)-左旋轉(zhuǎn);

2.2、刪除場(chǎng)景

接下來(lái)，我們分析一下刪除場(chǎng)景!

其實(shí)，刪除場(chǎng)景跟二叉樹(shù)的刪除思路是一樣的，不同的是需要調(diào)整，刪除的節(jié)點(diǎn)所在樹(shù)，需要層層判斷節(jié)點(diǎn)的高度差是否大于1，如果大于1，就進(jìn)行左旋轉(zhuǎn)或者右旋轉(zhuǎn)!

場(chǎng)景一

當(dāng)刪除的節(jié)點(diǎn)，只有左子樹(shù)時(shí)，直接將左子樹(shù)轉(zhuǎn)移到上層即可!

場(chǎng)景二

當(dāng)刪除的節(jié)點(diǎn)，只有右子樹(shù)時(shí)，直接將右子樹(shù)轉(zhuǎn)移到上層即可!

場(chǎng)景三

當(dāng)刪除的節(jié)點(diǎn)，有左、右子樹(shù)時(shí)，因?yàn)楫?dāng)前節(jié)點(diǎn)的左子樹(shù)的最末端的右子樹(shù)或者當(dāng)前節(jié)點(diǎn)的右子樹(shù)的最末端的左子樹(shù)，最接近當(dāng)前節(jié)點(diǎn)，找到其中任意一個(gè)，然后將其內(nèi)容替換并移除最末端節(jié)點(diǎn)，即可實(shí)現(xiàn)刪除!

總結(jié)

第三種場(chǎng)景稍微復(fù)雜了一些，但基本都是這么一個(gè)套路，與二叉樹(shù)不同的是，刪除之后需要判斷樹(shù)高，對(duì)超過(guò)1的進(jìn)行調(diào)整，類似上面插入的左旋轉(zhuǎn)、右旋轉(zhuǎn)操作!

三、代碼實(shí)踐

接下來(lái)，我們從代碼層面來(lái)定義一下樹(shù)的實(shí)體結(jié)構(gòu)，如下：

1public class AVLNode<E extends Comparable<E>> {  2  3    /**節(jié)點(diǎn)關(guān)鍵字*/  4    E key;  5  6    /**當(dāng)前節(jié)點(diǎn)樹(shù)高*/  7    int height;  8  9    /**當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)*/ 10    AVLNode<E> lChild = null; 11 12    /**當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)*/ 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}

我們創(chuàng)建一個(gè)算法類AVLSolution，完整實(shí)現(xiàn)如下：

  1public class AVLSolution<E extends Comparable<E>> {   2   3    /**定義根節(jié)點(diǎn)*/   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        //左子樹(shù)搜索  20        if(key.compareTo(node.key) < 0){  21            //當(dāng)前節(jié)點(diǎn)左子樹(shù)不為空,繼續(xù)遞歸向下搜索  22            node.lChild = insertAVL(key,node.lChild);  23            //出現(xiàn)不平衡，只會(huì)是左子樹(shù)比右子樹(shù)高，大于1的時(shí)候，就進(jìn)行調(diào)整  24            if(getHeight(node.lChild) - getHeight(node.rChild) == 2){  25                if(key.compareTo(node.lChild.key) < 0){  26                    //如果插入的節(jié)點(diǎn)位于當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的左子樹(shù)，進(jìn)行單次右旋轉(zhuǎn)  27                    node = rotateRight(node);  28                }else{  29                    //如果插入的節(jié)點(diǎn)位于當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的右子樹(shù)，先左旋轉(zhuǎn)再右旋轉(zhuǎn)  30                    node = rotateLeftRight(node);  31                }  32            }  33        }else if(key.compareTo(node.key) > 0){  34            //當(dāng)前節(jié)點(diǎn)右子樹(shù)不為空,繼續(xù)遞歸向下搜索  35            node.rChild = insertAVL(key,node.rChild);  36            //出現(xiàn)不平衡，只會(huì)是右子樹(shù)比左子樹(shù)高，大于1的時(shí)候，就進(jìn)行調(diào)整  37            if(getHeight(node.rChild) - getHeight(node.lChild) == 2){  38                if(key.compareTo(node.rChild.key) < 0){  39                    //如果插入的節(jié)點(diǎn)位于當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)的左子樹(shù)，先右旋轉(zhuǎn)再左旋轉(zhuǎn)  40                    node = rotateRightLeft(node);  41                }else{  42                    //如果插入的節(jié)點(diǎn)位于當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)的右子樹(shù)，進(jìn)行單次左旋轉(zhuǎn)  43                    node = rotateLeft(node);  44                }  45            }  46        } else{  47            //key已經(jīng)存在，直接返回  48        }  49        //因?yàn)楣?jié)點(diǎn)插入，樹(shù)高發(fā)生變化，更新節(jié)點(diǎn)高度  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            //左子樹(shù)查找  68            node.lChild = deleteAVL(key,node.lChild);  69            //可能會(huì)出現(xiàn)，右子樹(shù)比左子樹(shù)高2  70            if (getHeight(node.rChild) - getHeight(node.lChild) == 2){  71                node = rotateLeft(node);  72            }  73        } else if(key.compareTo(node.key) > 0){  74            //右子樹(shù)查找  75            node.rChild = deleteAVL(key, node.rChild);  76            //可能會(huì)出現(xiàn)，左子樹(shù)比右子樹(shù)高2  77            if (getHeight(node.lChild) - getHeight(node.rChild) == 2){  78                node = rotateRight(node);  79            }  80        }else{  81            //找到目標(biāo)元素，刪除分三種情況  82            //1.當(dāng)前節(jié)點(diǎn)沒(méi)有左子樹(shù)，直接返回當(dāng)前節(jié)點(diǎn)右子樹(shù)  83            //2.當(dāng)前節(jié)點(diǎn)沒(méi)有右子樹(shù)，直接返回當(dāng)前節(jié)點(diǎn)右子樹(shù)  84            //3.當(dāng)前節(jié)點(diǎn)有左子樹(shù)、右子樹(shù)的時(shí)候，尋找當(dāng)前節(jié)點(diǎn)的右子樹(shù)的最末端的左子樹(shù)，進(jìn)行替換和移除  85            if(node.lChild == null){  86                return node.rChild;  87            }  88            if(node.rChild == null){  89                return node.lChild;  90            }  91            //找到當(dāng)前節(jié)點(diǎn)的右子樹(shù)的最末端的左子樹(shù)，也就是右子樹(shù)最小節(jié)點(diǎn)  92            AVLNode<E> minLChild = searchDeleteMin(node.rChild);  93            //刪除最小節(jié)點(diǎn)，如果高度變化，進(jìn)行調(diào)整  94            minLChild.rChild = deleteMin(node.rChild);  95            minLChild.lChild = node.lChild;//將當(dāng)前節(jié)點(diǎn)的左子樹(shù)轉(zhuǎn)移到最小節(jié)點(diǎn)上  96  97            node = minLChild;//覆蓋當(dāng)前節(jié)點(diǎn)  98            //因?yàn)槭怯易訕?shù)發(fā)生高度變低，因此可能需要調(diào)整  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        //左子樹(shù)搜索 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已經(jīng)存在，直接返回 127            return node; 128        } 129    }  130 131    /** 132     * 查找需要?jiǎng)h除的元素 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        //移除最小節(jié)點(diǎn) 159        node.lChild = deleteMin(node.lChild); 160        //此時(shí)移除的是左節(jié)點(diǎn)，判斷是否平衡高度被破壞 161        if(getHeight(node.rChild) - getHeight(node.lChild) == 2){ 162            //進(jìn)行調(diào)整 163            node = rotateLeft(node); 164        } 165        return node; 166 167    } 168 169    /** 170     * 單次左旋轉(zhuǎn) 171     * @param node 172     * @return 173     */ 174    private AVLNode<E> rotateLeft(AVLNode<E> node){ 175        System.out.println("節(jié)點(diǎn)：" + node.key + "，單次左旋轉(zhuǎn)"); 176        AVLNode<E> x = node.rChild;//獲取旋轉(zhuǎn)節(jié)點(diǎn)的右節(jié)點(diǎn) 177        node.rChild = x.lChild;//將旋轉(zhuǎn)節(jié)點(diǎn)的右節(jié)點(diǎn)的左節(jié)點(diǎn)轉(zhuǎn)移，作為旋轉(zhuǎn)節(jié)點(diǎn)的右子樹(shù) 178        x.lChild = node;//將旋轉(zhuǎn)節(jié)點(diǎn)作為旋轉(zhuǎn)節(jié)點(diǎn)的右子樹(shù)的左子樹(shù) 179 180        //更新調(diào)整節(jié)點(diǎn)高度(先調(diào)整旋轉(zhuǎn)節(jié)點(diǎn)node) 181        node.height = updateHeight(node); 182        x.height = updateHeight(x); 183        return x; 184    } 185 186    /** 187     * 單次右旋轉(zhuǎn) 188     * @return 189     */ 190    private AVLNode<E> rotateRight(AVLNode<E> node){ 191        System.out.println("節(jié)點(diǎn)：" + node.key + "，單次右旋轉(zhuǎn)"); 192        AVLNode<E> x = node.lChild;//獲取旋轉(zhuǎn)節(jié)點(diǎn)的左節(jié)點(diǎn) 193        node.lChild = x.rChild;//將旋轉(zhuǎn)節(jié)點(diǎn)的左節(jié)點(diǎn)的右節(jié)點(diǎn)轉(zhuǎn)移，作為旋轉(zhuǎn)節(jié)點(diǎn)的左子樹(shù) 194        x.rChild = node;//將旋轉(zhuǎn)節(jié)點(diǎn)作為旋轉(zhuǎn)節(jié)點(diǎn)的左子樹(shù)的右子樹(shù) 195 196        //更新調(diào)整節(jié)點(diǎn)高度(先調(diào)整旋轉(zhuǎn)節(jié)點(diǎn)node) 197        node.height = updateHeight(node); 198        x.height = updateHeight(x); 199        return x; 200    } 201 202    /** 203     * 左旋轉(zhuǎn)-右旋轉(zhuǎn) 204     * @param node 205     * @return 206     */ 207    private AVLNode<E> rotateLeftRight(AVLNode<E> node){ 208        System.out.println("節(jié)點(diǎn)：" + node.key + "，左旋轉(zhuǎn)-右旋轉(zhuǎn)"); 209        //先對(duì)當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn) 210        node.lChild = rotateLeft(node.lChild); 211        //再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn) 212        return rotateRight(node); 213    } 214 215    /** 216     * 右旋轉(zhuǎn)-左旋轉(zhuǎn) 217     * @param node 218     * @return 219     */ 220    private AVLNode<E> rotateRightLeft(AVLNode<E> node){ 221        System.out.println("節(jié)點(diǎn)：" + node.key + "，右旋轉(zhuǎn)-左旋轉(zhuǎn)"); 222        //先對(duì)當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn) 223        node.rChild = rotateRight(node.rChild); 224        return rotateLeft(node); 225 226    } 227 228    /** 229     * 獲取節(jié)點(diǎn)高度，如果為空，等于-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     * 更新節(jié)點(diǎn)高度 239     * @param node 240     * @return 241     */ 242    private int updateHeight(AVLNode<E> node){ 243        //比較當(dāng)前節(jié)點(diǎn)左子樹(shù)、右子樹(shù)高度，獲取節(jié)點(diǎn)高度 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);//遍歷當(dāng)前節(jié)點(diǎn)左子樹(shù) 255            frontTreeIterator(node.rChild);//遍歷當(dāng)前節(jié)點(diǎn)右子樹(shù) 256        } 257    } 258 259    /** 260     * 中序遍歷 261     * @param node 262     */ 263    public void middleTreeIterator(AVLNode<E> node){ 264        if(node != null){ 265            middleTreeIterator(node.lChild);//遍歷當(dāng)前節(jié)點(diǎn)左子樹(shù) 266            System.out.println("key:" + node.key); 267            middleTreeIterator(node.rChild);//遍歷當(dāng)前節(jié)點(diǎn)右子樹(shù) 268        } 269    } 270 271    /** 272     * 后序遍歷 273     * @param node 274     */ 275    public void backTreeIterator(AVLNode<E> node){ 276        if(node != null){ 277            backTreeIterator(node.lChild);//遍歷當(dāng)前節(jié)點(diǎn)左子樹(shù) 278            backTreeIterator(node.rChild);//遍歷當(dāng)前節(jié)點(diǎn)右子樹(shù) 279            System.out.println("key:" + node.key); 280        } 281    } 282 283}

測(cè)試代碼，如下：

1public class AVLClient {  2  3    public static void main(String[] args) {  4        //創(chuàng)建一個(gè)Integer型的數(shù)據(jù)結(jié)構(gòu)  5        AVLSolution<Integer> avlTree = new AVLSolution<Integer>();  6  7        //插入節(jié)點(diǎn)  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        //查詢節(jié)點(diǎn) 23        AVLNode<Integer> searchResult = avlTree.search(120); 24        System.out.println("查找結(jié)果：" + searchResult); 25        System.out.println("========刪除key為90的元素========"); 26 27        //刪除節(jié)點(diǎn) 28        avlTree.delete(90); 29        System.out.println("========再次中序遍歷元素========"); 30 31        //中序遍歷 32        avlTree.middleTreeIterator(avlTree.root); 33    } 34}

輸出結(jié)果如下：

到此，關(guān)于“怎么理解并掌握J(rèn)ava的AVL樹(shù)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！