AVL[二叉查找樹]

AVL[二叉查找樹]

AVL是Athena Vortex Lattice的簡稱，由美國麻省理工學院的Drela博士及其學生開發，可用用於亞聲速飛機氣動特性和操穩特性的分析。AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個兒子，子樹的高度最大差別為一，所以它也被稱為高度平衡樹。

基本信息

概述

在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。AVL樹得名於它的發明者G.M.Adelson-Velsky和E.M.Landis，他們在1962年的論文《Analgorithmfortheorganizationofinformation》中發表了它。

節點計算

AVLAVL
度為h的AVL樹，節點數N最多2^h−1；最少（其中）。
最少節點數n如以斐波那契數列可以用數學歸納法證明：
Nh=F【h+2】-1(F【h+2】是Fibonaccipolynomial的第h+2個數）。
即：
N0=0（表示AVLTree高度為0的節點總數）
N1=1（表示AVLTree高度為1的節點總數）
N2=2（表示AVLTree高度為2的節點總數）
Nh=N【h−1】+N【h−2】+1（表示AVLTree高度為h的節點總數）
換句話說，當節點數為N時，高度h最多為節點的平衡因子是它的右子樹的高度減去它的左子樹的高度。帶有平衡因子1、0或-1的節點被認為是平衡的。帶有平衡因子-2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。

操作

AVLAVL
AVL樹的基本操作一般涉及運做同在不平衡的二叉查找樹所運做的同樣的算法。但是要進行預先或隨後做一次或多次所謂的"AVL鏇轉"。
假設由於在二叉排序樹上插入結點而失去平衡的最小子樹根結點的指針為a（即a是離插入點最近，且平衡因子絕對值超過1的祖先結點），則失去平衡後進行進行的規律可歸納為下列四種情況：
單向右鏇平衡處理RR：由於在*a的左子樹根結點的左子樹上插入結點，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進行一次右鏇轉操作；
單向左鏇平衡處理LL：由於在*a的右子樹根結點的右子樹上插入結點，*a的平衡因子由-1變為-2，致使以*a為根的子樹失去平衡，則需進行一次左鏇轉操作；
雙向鏇轉（先左後右）平衡處理LR：由於在*a的左子樹根結點的右子樹上插入結點，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進行兩次鏇轉（先左鏇後右鏇）操作。
雙向鏇轉（先右後左）平衡處理RL：由於在*a的右子樹根結點的左子樹上插入結點，*a的平衡因子由-1變為-2，致使以*a為根的子樹失去平衡，則需進行兩次鏇轉（先右鏇後左鏇）操作。

插入

AVLAVL
向AVL樹插入可以通過如同它是未平衡的二叉查找樹一樣把給定的值插入樹中，接著自底向上向根節點折回，於在插入期間成為不平衡的所有節點上進行鏇轉來完成。因為折回到根節點的路途上最多有1.5乘logn個節點，而每次AVL鏇轉都耗費恆定的時間，插入處理在整體上耗費O(logn)時間。　在平衡的的二叉排序樹BalancedBST上插入一個新的數據元素e的遞歸算法可描述如下：　若BBST為空樹，則插入一個數據元素為e的新結點作為BBST的根結點，樹的深度增1；若e的關鍵字和BBST的根結點的關鍵字相等，則不進行；若e的關鍵字小於BBST的根結點的關鍵字，而且在BBST的左子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的左子樹上，並且當插入之後的左子樹深度增加（+1）時，分別就下列不同情況處理之：　BBST的根結點的平衡因子為-1（右子樹的深度大於左子樹的深度，則將根結點的平衡因子更改為0，BBST的深度不變；　BBST的根結點的平衡因子為0（左、右子樹的深度相等）：則將根結點的平衡因子更改為1，BBST的深度增1；　BBST的根結點的平衡因子為1（左子樹的深度大於右子樹的深度）：則若BBST的左子樹根結點的平衡因子為1：則需進行單向右鏇平衡處理，並且在右鏇處理之後，將根結點和其右子樹根結點的平衡因子更改為0，樹的深度不變；　若e的關鍵字大於BBST的根結點的關鍵字，而且在BBST的右子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的右子樹上，並且當插入之後的右子樹深度增加（+1）時，分別就不同情況處理之。

刪除

從AVL樹中刪除可以通過把要刪除的節點向下鏇轉成一個葉子節點，接著直接剪除這個葉子節點來完成。因為在鏇轉成葉子節點期間最多有logn個節點被鏇轉，而每次AVL鏇轉耗費恆定的時間，刪除處理在整體上耗費O(logn)時間。

查找

在AVL樹中查找同在一般BST完全一樣的進行，所以耗費O(logn)時間，因為AVL樹總是保持平衡的。不需要特殊的準備，樹的結構不會由於查詢而改變。（這是與伸展樹查找相對立的，它會因為查找而變更樹結構。）

代碼實現

publicclassAVLTree<TextendsComparable<?superT>>{
privateAVLNode<T>root;
publicAVLTree(){root=null;}
/***Checkifgivenitemxisinthetree.*/
publicbooleancontains(Tx){returncontains(x,root);}
/***Internalmethodtocheckifgivenitemxisinthesubtree.*
*@paramx*thegivenitemtocheck.
*@paramt*thenodethatrootsthesubtree.*/
privatebooleancontains(Tx,AVLNode<T>t){while(t!=null)
{intcompareResult=x.compareTo(t.element);
if(compareResult<0)
t=t.left;
elseif(compareResult>0)
t=t.right;
else
returntrue;}
returnfalse;}
/***InsertanewitemtotheAVLtree.*
*@paramx
*theitemtoinsert.*/
publicvoidinsert(Tx){
root=insert(x,root);}
/***Internalmethodtoinsertintoasubtree.*
*@paramx
*theitemtoinsert.
*@paramt
*thenodethatrootsthesubtree.
*@returnthenewrootofthesubtree.*/
privateAVLNode<T>insert(Tx,AVLNode<T>t){
if(t==null)
returnnewAVLNode<T>(x);
intcompareResult=x.compareTo(t.element);
if(compareResult<0)
{t.left=insert(x,t.left);
if(height(t.left)-height(t.right)==2)
if(x.compareTo(t.left.element)<0)
t=rotateWithLeftChild(t);
else
t=doubleWithLeftChild(t);}
elseif(compareResult>0)
{t.right=insert(x,t.right);
if(height(t.right)-height(t.left)==2)
if(x.compareTo(t.right.element)>0)
t=rotateWithRightChild(t);
else
t=doubleWithRightChild(t);}
else;
t.height=Math.max(height(t.left),height(t.right))+1;
returnt;}
/***Returntheheightofroott,or-1,ifnull.*
*@paramt
*anAVLNode.
*@returntheheight.*/
privateintheight(AVLNode<T>t){
returnt==null?-1:t.height}
/***Singlerotation(left-left).Updateheight,thenreturnnewroot.*/
privateAVLNode<T>rotateWithLeftChild(AVLNode<T>z){
AVLNode<T>y=z.left;
z.left=y.right;
y.right=z;
z.height=Math.max(height(z.left),height(z.right))+1;
y.height=Math.max(height(y.left),z.height)+1;
returny;}
/***Singlerotation(right-right).Updateheight,thenreturnnewroot.*/
privateAVLNode<T>rotateWithRightChild(AVLNode<T>z){
AVLNode<T>y=z.right;
z.right=y.left;
y.left=z;
z.height=Math.max(height(z.left),height(z.right))+1;
y.height=Math.max(height(y.right),z.height)+1;
returny;}
/***Doublerotation(left-right).*/
privateAVLNode<T>doubleWithLeftChild(AVLNode<T>z)
{z.left=rotateWithRightChild(z.left);
returnrotateWithLeftChild(z);}
/***Doublerotation(right-left).*/
privateAVLNode<T>doubleWithRightChild(AVLNode<T>z){
z.right=rotateWithLeftChild(z.right);
returnrotateWithRightChild(z);}
/**Removeitemx.*/
publicvoidremove(Tx)
{root=remove(x,root);}
/***Removeitemxfromsubtreet.
*@paramxtheitemtoberemoved.
*@paramtthenodethatrootsthesubtree.
*@returnthenewrootofthesubtree.*/
privateAVLNode<T>remove(Tx,AVLNode<T>t){
if(t==null)
returnt;
intcompareResult=x.compareTo(t.element);
if(compareResult<0){
t.left=remove(x,t.left);
if(height(t.right)-height(t.left)==2)
if(height(t.right.left)<height(t.right.right))
t=rotateWithRightChild(t);
else
t=doubleWithRightChild(t);}
elseif(compareResult>0)
{t.right=remove(x,t.right);
if(height(t.left)-height(t.right)==2)
if(height(t.left.left)>height(t.left.right))
t=rotateWithLeftChild(t);
else
t=doubleWithLeftChild(t);}
elseif(t.left!=null&&t.right!=null)
{t.element=findMin(t.right).element;
t.right=remove(t.element,t.right);
if(height(t.left)-height(t.right)==2)
if(height(t.left.left)>height(t.left.right))
t=rotateWithLeftChild(t);
else
t=doubleWithLeftChild(t);}
else
{t=(t.left!=null)?t.left:t.right;}
if(t!=null)
t.height=Math.max(height(t.left),height(t.right))+1;
returnt;}
publicTfindMin()
{if(isEmpty())
returnnull;
returnfindMin(root).element;}
privateAVLNode<T>findMin(AVLNode<T>t){
while(t.left!=null)
t=t.left;
returnt;}
publicTfindMax()
{if(isEmpty())
returnnull;
returnfindMax(root).element;}
privateAVLNode<T>findMax(AVLNode<T>t){
while(t.right!=null)
t=t.right;
returnt;}
publicvoidmakeEmpty()
{root=null;}
publicbooleanisEmpty()
{returnroot==null;}
/**InternalclassAVLNode*/
privatestaticclassAVLNode<T>
{Telement;
AVLNode<T>left;
AVLNode<T>right;
intheight;
publicAVLNode(Telement)
{this(element,null,null);}
publicAVLNode(Telement,AVLNode<T>left,AVLNode<T>right)
{this.element=element;
this.left=left;
this.right=right;
this.height=0;}}}
AVL

單元編碼

編碼就是對信息進行轉換，使之獲得適合於記憶系統的形式的加工過程（Encoding）。經過編碼所產生的具體的信息形式叫做代碼（Code）。
⑴回憶錯誤實驗表明：人們在回憶時產生錯誤主要發生在聲音相近的字母混淆上。說明短時記憶的信息代碼主要是聲音代碼或聽覺代碼。
⑵即使使用視覺材料作為刺激，其代碼也仍有聽覺性質，在短時記憶中出現形聲轉換，而以聲音形式貯存。
⑶鑒於字母、字詞的聽覺代碼和口語代碼都是不同形式的言語代碼，因此，常將聽覺的（Auditory）、口語的（Verbal）、言語的（Languistic）代碼聯合起來，稱之為A.V.L單元。

熱門詞條

聯絡我們