AVL

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

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

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

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

即:

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

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

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

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

換句話說，當(dāng)節(jié)點(diǎn)數(shù)為 N 時(shí)，高度 h 最多為。

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

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

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

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

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

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

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

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

從AVL樹中刪除可以通過把要?jiǎng)h除的節(jié)點(diǎn)向下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)，接著直接剪除這個(gè)葉子節(jié)點(diǎn)來完成。因?yàn)樵谛D(zhuǎn)成葉子節(jié)點(diǎn)期間最多有 log n個(gè)節(jié)點(diǎn)被旋轉(zhuǎn)，而每次 AVL 旋轉(zhuǎn)耗費(fèi)恒定的時(shí)間，刪除處理在整體上耗費(fèi) O(log n) 時(shí)間。

在AVL樹中查找同在一般BST完全一樣的進(jìn)行，所以耗費(fèi) O(log n) 時(shí)間，因?yàn)锳VL樹總是保持平衡的。不需要特殊的準(zhǔn)備，樹的結(jié)構(gòu)不會(huì)由于查詢而改變。(這是與伸展樹查找相對立的，它會(huì)因?yàn)椴檎叶兏鼧浣Y(jié)構(gòu)。)

給出一個(gè)操作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

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

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

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

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

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

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

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

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