AVL單元編碼

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

⑴回憶錯(cuò)誤實(shí)驗(yàn)表明:人們?cè)诨貞洉r(shí)產(chǎn)生錯(cuò)誤主要發(fā)生在聲音相近的字母混淆上。說(shuō)明短時(shí)記憶的信息代碼主要是聲音代碼或聽(tīng)覺(jué)代碼。

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

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

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

高度為 h 的 AVL 樹(shù)，節(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ù))

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

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

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

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

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

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

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

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

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

從AVL樹(shù)中刪除可以通過(guò)把要?jiǎng)h除的節(jié)點(diǎn)向下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)，接著直接剪除這個(gè)葉子節(jié)點(diǎn)來(lái)完成。因?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樹(shù)中查找同在一般BST完全一樣的進(jìn)行，所以耗費(fèi) O(log n) 時(shí)間，因?yàn)锳VL樹(shù)總是保持平衡的。不需要特殊的準(zhǔn)備，樹(shù)的結(jié)構(gòu)不會(huì)由于查詢(xún)而改變。(這是與伸展樹(shù)查找相對(duì)立的，它會(huì)因?yàn)椴檎叶兏鼧?shù)結(jié)構(gòu)。)

給出一個(gè)操作AVLTREE的完整程序 大部分由Peter Brass編寫(xiě)

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

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

1.本身首先是一棵二叉搜索樹(shù)。

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

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