AVL

在計算機科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis，他們在 1962 年的論文《An algorithm for the organization of information》中發(fā)表了它。

高度為 h 的 AVL 樹，節(jié)點數(shù) N 最多2^h ? 1; 最少 (其中)。

最少節(jié)點數(shù) n 如以斐波那契數(shù)列可以用數(shù)學(xué)歸納法證明:

Nh=F【h+ 2】 - 1 (F【h+ 2】是 Fibonacci polynomial 的第h+2個數(shù))。

即:

N0 = 0 (表示 AVL Tree 高度為0的節(jié)點總數(shù))

N1 = 1 (表示 AVL Tree 高度為1的節(jié)點總數(shù))

N2 = 2 (表示 AVL Tree 高度為2的節(jié)點總數(shù))

Nh=N【h? 1】 +N【h? 2】 + 1 (表示 AVL Tree 高度為h的節(jié)點總數(shù))

換句話說，當節(jié)點數(shù)為 N 時，高度 h 最多為。

節(jié)點的平衡因子是它的右子樹的高度減去它的左子樹的高度。帶有平衡因子 1、0 或 -1 的節(jié)點被認為是平衡的。帶有平衡因子 -2 或 2 的節(jié)點被認為是不平衡的，并需要重新平衡這個樹。平衡因子可以直接存儲在每個節(jié)點中，或從可能存儲在節(jié)點中的子樹高度計算出來。

AVL樹的基本操作一般涉及運做同在不平衡的二叉查找樹所運做的同樣的算法。但是要進行預(yù)先或隨后做一次或多次所謂的"AVL 旋轉(zhuǎn)"。

假設(shè)由于在二叉排序樹上插入結(jié)點而失去平衡的最小子樹根結(jié)點的指針為a(即a是離插入點最近，且平衡因子絕對值超過1的祖先結(jié)點)，則失去平衡后進行進行的規(guī)律可歸納為下列四種情況:

單向右旋平衡處理RR:由于在*a的左子樹根結(jié)點的左子樹上插入結(jié)點，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進行一次右旋轉(zhuǎn)操作;

單向左旋平衡處理LL:由于在*a的右子樹根結(jié)點的右子樹上插入結(jié)點，*a的平衡因子由-1變?yōu)?2，致使以*a為根的子樹失去平衡，則需進行一次左旋轉(zhuǎn)操作;

雙向旋轉(zhuǎn)(先左后右)平衡處理LR:由于在*a的左子樹根結(jié)點的右子樹上插入結(jié)點，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進行兩次旋轉(zhuǎn)(先左旋后右旋)操作。

雙向旋轉(zhuǎn)(先右后左)平衡處理RL:由于在*a的右子樹根結(jié)點的左子樹上插入結(jié)點，*a的平衡因子由-1變?yōu)?2，致使以*a為根的子樹失去平衡，則需進行兩次旋轉(zhuǎn)(先右旋后左旋)操作。

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

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

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

給出一個操作AVLTREE的完整程序 大部分由Peter Brass編寫

public class AVLTree<T extends Comparable<? super T>> {

private AVLNode<T> root;

public AVLTree() {root = null;}

/*** Check if given item x is in the tree.*/

public boolean contains(T x) {return contains(x, root);}

/*** Internal method to check if given item x is in the subtree.*

* @param x* the given item to check.

* @param t* the node that roots the subtree.*/

private boolean contains(T x, AVLNode<T> t) {while (t != null)

{int compareResult = x.compareTo(t.element);

if (compareResult < 0)

t = t.left;

else if (compareResult > 0)

t = t.right;

else

return true;}

return false;}

/*** Insert a new item to the AVL tree.*

* @param x

* the item to insert.*/

public void insert(T x) {

root = insert(x, root);}

/*** Internal method to insert into a subtree.*

* @param x

* the item to insert.

* @param t

* the node that roots the subtree.

* @return the new root of the subtree.*/

private AVLNode<T> insert(T x, AVLNode<T> t) {

if (t == null)

return new AVLNode<T>(x);

int compareResult = 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);}

else if (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;

return t;}

/*** Return the height of root t, or -1, if null.*

* @param t

* an AVLNode.

* @return the height.*/

private int height(AVLNode<T> t) {

return t == null ? -1 : t.height}

/*** Single rotation (left-left). Update height, then return new root.*/

private AVLNode<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;

return y;}

/*** Single rotation (right-right). Update height, then return new root.*/

private AVLNode<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;

return y;}

/*** Double rotation (left-right).*/

private AVLNode<T> doubleWithLeftChild(AVLNode<T> z)

{z.left = rotateWithRightChild(z.left);

return rotateWithLeftChild(z);}

/*** Double rotation (right-left).*/

private AVLNode<T> doubleWithRightChild(AVLNode<T> z) {

z.right = rotateWithLeftChild(z.right);

return rotateWithRightChild(z);}

/**Remove item x.*/

public void remove(T x)

{root = remove(x, root);}

/*** Remove item x from subtree t.

* @param x the item to be removed.

* @param t the node that roots the subtree.

* @return the new root of the subtree.*/

private AVLNode<T> remove(T x, AVLNode<T> t) {

if (t == null)

return t;

int compareResult = 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);}

else if (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);}

else if (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;

return t;}

public T findMin()

{if (isEmpty())

return null;

return findMin(root).element;}

private AVLNode<T> findMin(AVLNode<T> t) {

while (t.left != null)

t = t.left;

return t;}

public T findMax()

{if (isEmpty())

return null;

return findMax(root).element;}

private AVLNode<T> findMax(AVLNode<T> t) {

while (t.right != null)

t = t.right;

return t;}

public void makeEmpty()

{root = null;}

public boolean isEmpty()

{return root == null;}

/** Internal class AVLNode */

private static class AVLNode<T>

{T element;

AVLNode<T> left;

AVLNode<T> right;

int height;

public AVLNode(T element)

{this(element, null, null);}

public AVLNode(T element, AVLNode<T> left, AVLNode<T> right)

{this.element = element;

this.left = left;

this.right = right;

this.height = 0;}}}

AVL

編碼就是對信息進行轉(zhuǎn)換，使之獲得適合于記憶系統(tǒng)的形式的加工過程(Encoding)。經(jīng)過編碼所產(chǎn)生的具體的信息形式叫做代碼(Code)。

⑴回憶錯誤實驗表明:人們在回憶時產(chǎn)生錯誤主要發(fā)生在聲音相近的字母混淆上。說明短時記憶的信息代碼主要是聲音代碼或聽覺代碼。

⑵即使使用視覺材料作為刺激，其代碼也仍有聽覺性質(zhì)，在短時記憶中出現(xiàn)形聲轉(zhuǎn)換，而以聲音形式貯存。

⑶鑒于字母、字詞的聽覺代碼和口語代碼都是不同形式的言語代碼，因此，常將聽覺的(Auditory)、口語的(Verbal)、言語的(Languistic)代碼聯(lián)合起來，稱之為A.V.L單元。

AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點是:

1.本身首先是一棵二叉搜索樹。

2.帶有平衡條件:每個結(jié)點的左右子樹的高度之差的絕對值(平衡因子)最多為1。

也就是說，AVL樹，本質(zhì)上是帶了平衡功能的二叉查找樹(二叉排序樹，二叉搜索樹)。