?????????? 前言

?????????????????????? 前面一篇文章，筆者就二叉查找樹進行了一些解釋與實現，這篇文章筆者將會就平衡二叉樹

?????????????????? 做一些總結與實現。讀者若不了解二叉查找樹的話，可以參考這篇文章：

?????????????????? http://blog.csdn.net/kiritor/article/details/8889176

?????????????????? ?? 在學習平衡二叉樹之前，我們先回顧下二叉查找樹的特點和性質。

????????????????????? 基于二叉查找樹以下的操作是低性能的：

??????????????????? ? ? ? ? ? 1、如果我們向一棵空的二叉查找樹中插入一個預先排好序的序列的（升序），根據插入

? ? ? ? ? ? ? ? ? ?? 操作我們會發現形成的二叉樹結點層次太深，且沒有左兒子結點。情況如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????

????????????????????? 這樣就造成了二叉樹的深度過深，明顯不合理。

?????????????????????????????? 2、在二叉查找樹的情況下，對于任意個單一的操作我們不再保證O（logN）的時間界

?????????????????????? 但是我們可以證明的是在連續M次操作時間花費可能達到O（MlogN）,消耗太高了。

????????????????????????????? 基于上述的原因，我們就需要考慮平衡二叉樹了。

??????????? 平衡二叉樹

????????????????????????????? 首先需要明白的是平衡二叉樹是對二叉查找的一種改進，對于二叉查找樹的一個明顯的

??????????????????? 缺點就是，樹的結構仍舊具有極大的變動性，最壞的情況下就是一棵單支二叉樹，丟失了二叉

??????????????????? 查找樹一些原有的優點。

????????????????????????????? 平衡二叉樹定義（AVL）：它或者是一棵空樹，或者是具有一下性質的二叉查找樹--

???????????????????? 它的結點左子樹和右子樹的深度之差不超過1,而且該結點的左子樹和右子樹都是一棵

???????????????????? 平衡二叉樹。

??????????????????????????? 平衡因子：結點左子樹的深度-結點右子樹的深度。（0、1、-1）。

??????????????????? ? ? ? ? ? ??????

????????????????????? 轉換為平衡二叉樹之后的二叉樹為：

????????????????????? ? ? ? ? ? ? ???

??????????? 平衡保持

???????????????????????? 很顯然，平衡二叉樹旨在“平衡”二字，其平衡是如何保持的呢？換句話說，二叉查找樹是

??????????????????? 如何轉換為平衡二叉樹的呢？就像上面兩張圖片，到底如何轉換的呢？基本的思想就是:

???????????????????????? 當二叉查找樹中插入一個結點時，首先檢查是否因為插入而破壞了平衡。若破壞了則

??????????????????? 找出其中的最小不平衡二叉樹，在保持二叉查找樹特性的情況下，調整最小不平衡子樹中結

?????????????????? 點之間的關系，以達到平衡。

??????????????????????? 最小不平衡二叉樹指距離插入結點最近且以平衡因子的絕對值大于1的結點作為根的子樹。

????????????????????? 那么最小不平衡二叉樹結點的關系到底是如何進行調整的呢？分為四種情況討論。

??????????? 四種不平衡類型

???????????????????????? 有四種情況可以導致二叉樹不平衡：（以根結點為例）

????????????????????????? 1、LL型（右旋操作）：插入一個新的結點到根結點的左子樹的左子樹，導致根結點的平衡

??????????????????????????????? 因子1變為2。

???????????????????????? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ??

????????????????????????????????? 其右旋操作我們以一個具體的例子掌握：

??????????????????????? ? ? ? ? ? ? ? ? ? ?????????

??????????????????????????????????????? 以第一列為例，在結點2的左子樹插入結點D，插入后2結點的平衡因子變為1,導致

??????????????????????????????? 結點5(根結點）的平衡因子變為2，則結點5為根結點的子樹是最小不平衡子樹。調整時

??????????????????????????????? 將結點5的左孩子3向右上旋轉代替結點5為根結點，將根結點右下旋轉為3的右子樹的根

??????????????????????????????? 結點，而結點3的原右子樹變為結點5的左子樹。

???????????????????????????????????????? 在結點2的右孩子處插入的情況原理一樣的。

?????????????????????????????? 2、RR型（左旋操作）：插入一個新的結點到根結點的右子樹的右子樹，導致根結點的平衡

??????????????????????????????? 因子1變為2。

??????????????????? ? ? ? ? ? ? ? ? ? ? ? ?? ????????

???????????????????????????????????????? 其具體的操作我們同樣以一個例子為例：

?????????????????????????? ? ?? ????

????????????????????????????? 其操作步驟與右旋操作沒有什么太大的區別，這里筆者就不詳述過程了。

?????????????????????????????? 3、LR型（左旋+右旋）：在根結點的左孩子的右子樹上插入結點，插入情況筆者就

????????????????????????????? 不給實例圖了。直接演示其操作過程。

????????????????????????????????????

???????????????????????????? 可見的是LR型需要兩次的旋轉才能達到要求，不過在進行右旋操作的時候需要注意C

????????????????????????? 的位置。

?????????????????????????????? 4、RL型（右旋+左旋）在根結點的右子樹的左子樹上插入結點。同樣以一個實例圖

????????????????????????? 來演示操作。

????????????????????????? ? ????? ???

???????????? 完整源碼實現：

??????????????????????? 根據上述的旋轉操作，我們簡單的實現二叉平衡樹：

package com.kiritor; /** ?*二叉平衡樹簡單實現 ?*@author kiritor ?*/ public class AvlTree< T extends Comparable< ? super T>> { private static class AvlNode< T>{//avl樹節點 AvlNode( T theElement ) { this( theElement, null, null ); } AvlNode( T theElement, AvlNode< T> lt, AvlNode< T> rt ) { element = theElement; left = lt; right = rt; height = 0; } T element; // 節點中的數據 AvlNode< T> left; // 左兒子 AvlNode< T> right; // 右兒子 int height; // 節點的高度 } private AvlNode< T> root;//avl樹根 public AvlTree( ) { root = null; } //在avl樹中插入數據，重復數據復略 public void insert( T x ) { root = insert( x, root ); } //在avl中刪除數據,這里并未實現 public void remove( T x ) { System.out.println( "Sorry, remove unimplemented" ); } //在avl樹中找最小的數據 public T findMin( ) { if( isEmpty( ) ) System.out.println("樹空");; return findMin( root ).element; } //在avl樹中找最大的數據 public T findMax( ) { if( isEmpty( ) ) System.out.println("樹空"); return findMax( root ).element; } //搜索 public boolean contains( T x ) { return contains( x, root ); } public void makeEmpty( ) { root = null; } public boolean isEmpty( ) { return root == null; } //排序輸出avl樹 public void printTree( ) { if( isEmpty( ) ) System.out.println( "Empty tree" ); else printTree( root ); } private AvlNode< T> insert( T x, AvlNode< T> t ) { if( t == null ) return new AvlNode< T>( x, null, null ); int compareResult = x.compareTo( t.element ); if( compareResult < 0 ) { t.left = insert( x, t.left );//將x插入左子樹中 if( height( t.left ) - height( t.right ) == 2 )//打破平衡 if( x.compareTo( t.left.element ) < 0 )//LL型（左左型） t = rotateWithLeftChild( t ); else //LR型（左右型） t = doubleWithLeftChild( t ); } else if( compareResult > 0 ) { t.right = insert( x, t.right );//將x插入右子樹中 if( height( t.right ) - height( t.left ) == 2 )//打破平衡 if( x.compareTo( t.right.element ) > 0 )//RR型（右右型） t = rotateWithRightChild( t ); else //RL型 t = doubleWithRightChild( t ); } else ; // 重復數據，什么也不做 t.height = Math.max( height( t.left ), height( t.right ) ) + 1;//更新高度 return t; } //找最小 private AvlNode< T> findMin( AvlNode< T> t ) { if( t == null ) return t; while( t.left != null ) t = t.left; return t; } //找最大 private AvlNode< T> findMax( AvlNode< T> t ) { if( t == null ) return t; while( t.right != null ) t = t.right; return t; } //搜索（查找） private boolean contains( T x, AvlNode t ) { while( t != null ) { int compareResult = x.compareTo( (T) t.element ); if( compareResult < 0 ) t = t.left; else if( compareResult > 0 ) t = t.right; else return true; // Match } return false; // No match } //中序遍歷avl樹 private void printTree( AvlNode< T> t ) { if( t != null ) { printTree( t.left ); System.out.println( t.element ); printTree( t.right ); } } //求高度 private int height( AvlNode< T> t ) { return t == null ? -1 : t.height; } //帶左子樹旋轉,適用于LL型 private AvlNode< T> rotateWithLeftChild( AvlNode< T> k2 ) { AvlNode< T> k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1; k1.height = Math.max( height( k1.left ), k2.height ) + 1; return k1; } //帶右子樹旋轉，適用于RR型 private AvlNode< T> rotateWithRightChild( AvlNode< T> k1 ) { AvlNode< T> k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1; k2.height = Math.max( height( k2.right ), k1.height ) + 1; return k2; } //雙旋轉，適用于LR型 private AvlNode< T> doubleWithLeftChild( AvlNode< T> k3 ) { k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( k3 ); } //雙旋轉,適用于RL型 private AvlNode< T> doubleWithRightChild( AvlNode< T> k1 ) { k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( k1 ); } ???? // Test program ??? public static void main( String [ ] args ) ??? { ??????? AvlTree< Integer> t = new AvlTree< Integer>( ); ??????? final int NUMS = 200; ??????? final int GAP? =?? 17; ??????? System.out.println( "Checking... (no more output means success)" ); ??????? for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) ??????????? t.insert( i ); ?????????? t.printTree( ); ??????????? System.out.println(t.height(t.root)); ???? ? ??? } }????????????? 上述main函數中我們簡單的插入了1-199個數至二叉樹中，如果是二叉查找樹的話，可以

????????? 知道的是二叉樹的層樹應該為199，但是實際情況如何呢？

?????????????

????????????

轉載于:https://blog.51cto.com/kiritor/1226767

總結

以上是生活随笔為你收集整理的平衡二叉树（AVL）--查找、删除、插入（Java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。