自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

面試官提到的 AVL 樹，到底是個(gè)啥

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

 [[317730]]

了解過平衡二叉樹的朋友們，對(duì)它一定有印象，今天阿粉就與大家一起深入了解一下AVL樹!

一、摘要

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

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

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

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

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

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

二、算法思路

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

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

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

2.1、插入場(chǎng)景

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

場(chǎng)景一

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

 

 

 

 

場(chǎng)景二

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

 

 

 

 

場(chǎng)景三

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

 

 

 

 

場(chǎng)景四

當(dāng)我們?cè)?5的左邊或者右邊插入的時(shí)候，也就是90的左邊，需要進(jìn)行兩次旋轉(zhuǎn)，先會(huì)繞90右旋轉(zhuǎn)一次，再繞80左旋轉(zhuǎn)一次，即可達(dá)到樹高度差不超過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í)，只需右旋轉(zhuǎn);
  • 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的左節(jié)點(diǎn)的右子樹時(shí)，需要左旋轉(zhuǎn)-右旋轉(zhuǎn);
  • 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的右節(jié)點(diǎn)的右子樹時(shí)，只需左旋轉(zhuǎn);
  • 當(dāng)插入節(jié)點(diǎn)位于需要旋轉(zhuǎn)節(jié)點(diǎn)的右節(jié)點(diǎn)的左子樹時(shí)，需要右旋轉(zhuǎn)-左旋轉(zhuǎn);

2.2、刪除場(chǎng)景

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

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

場(chǎng)景一

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

 

 

 

 

場(chǎng)景二

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

 

 

 

 

場(chǎng)景三

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

 

 

 

 

總結(jié)

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

三、代碼實(shí)踐

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

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

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

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

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

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

輸出結(jié)果如下：

 

 

 

 

四、總結(jié)

平衡二叉樹查找樹，俗稱AVL樹，在查詢的時(shí)候，操作與普通二叉查找樹上的查找操作相同;插入的時(shí)候，每一次插入結(jié)點(diǎn)操作最多只需要單旋轉(zhuǎn)或雙旋轉(zhuǎn);如果是動(dòng)態(tài)刪除，刪除之后必須檢查從刪除結(jié)點(diǎn)開始到根結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)的平衡因子，也就是高度差，如果超過1就需要調(diào)整，最多可能需要O(logN)次旋轉(zhuǎn)。

整體上來說，平衡二叉樹優(yōu)于普通二叉查找樹!

五、參考

[1] 簡(jiǎn)書 - nicktming - 二叉平衡樹: https://www.jianshu.com/p/22c00b3731f5

[2] iteye - Heart.X.Raid - 平衡二叉查找樹 [AVL]: https://www.iteye.com/blog/hxraid-609949

責(zé)任編輯：武曉燕 來源： Java極客技術(shù)
AVL樹算法場(chǎng)景
相關(guān)推薦

2022-04-10 19:26:07

TypeScript類型語法

2024-02-07 12:35:00

React并發(fā)模式concurrent

2024-07-12 15:08:23

Python@wraps函數(shù)

2024-08-26 14:23:56

2022-09-06 21:38:45

數(shù)字人數(shù)字孿生

2021-12-16 15:11:59

Facebook天秤幣加密貨幣

2021-05-11 07:30:58

JNIJavaAPI

2022-05-04 08:38:32

Netty網(wǎng)絡(luò)框架

2021-01-28 17:41:32

Github網(wǎng)站Pull Reques

2021-03-03 17:26:45

面試Synchronous底層

2024-08-01 17:34:56

Promiseaxios請(qǐng)求

2021-12-26 00:01:51

Log4Shell漏洞服務(wù)器

2024-02-01 20:15:37

2013-05-29 10:17:56

Hadoop分布式文件系統(tǒng)

2012-07-25 09:09:46

GNOME OS桌面

2021-12-16 21:13:38

通信網(wǎng)管平臺(tái)

2021-05-19 10:44:42

數(shù)據(jù)庫架構(gòu)技術(shù)

2019-10-28 09:59:26

區(qū)塊鏈技術(shù)智能

2021-09-08 10:02:56

面試二維碼前端

2024-02-26 00:00:00

人工智能序列數(shù)據(jù)機(jī)器人
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)