二叉排序樹(shù)查找內(nèi)容

1.二叉排序樹(shù)的概念:

二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表。

二叉排序樹(shù)的定義：二叉排序樹(shù)或者是一棵空樹(shù)，

或者是一棵具有如下性質(zhì)的二叉樹(shù)：

⑴ 若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

⑵ 若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

⑶ 左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。二叉排序樹(shù)的性質(zhì)： 按中序遍歷二叉排序樹(shù)，所得到的中序遍歷序列是一個(gè)遞增有序序列。

2.二叉排序樹(shù)的插入:

在二叉排序樹(shù)中插入新結(jié)點(diǎn)，要保證插入后的二叉樹(shù)仍符合二叉排序樹(shù)的定義。

插入過(guò)程：若二叉排序樹(shù)為空，則待插入結(jié)點(diǎn)*S作為根結(jié)點(diǎn)插入到空樹(shù)中；

當(dāng)非空時(shí)，將待插結(jié)點(diǎn)關(guān)鍵字S->key和樹(shù)根關(guān)鍵字t->key進(jìn)行比較，

若s->key = t->key,則無(wú)須插入，若s->key< t->key,則插入到根的左子樹(shù)中，

若s->key> t->key,則插入到根的右子樹(shù)中。而子樹(shù)中的插入過(guò)程和在樹(shù)中的插入過(guò)程相同，

如此進(jìn)行下去，直到把結(jié)點(diǎn)*s作為一個(gè)新的樹(shù)葉插入到二叉排序樹(shù)中，或者直到發(fā)現(xiàn)樹(shù)已有相同關(guān)鍵字的結(jié)點(diǎn)為止。

3. 二叉排序樹(shù)生成：

從空的二叉排序樹(shù)開(kāi)始，經(jīng)過(guò)一系列的查找插入操作以后，生成了一棵二叉排序樹(shù)。

說(shuō)明：

① 每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn)。

② 由不同順序的關(guān)鍵字序列，會(huì)得到不同二叉排序樹(shù)。

③ 對(duì)于一個(gè)任意的關(guān)鍵字序列構(gòu)造一棵二叉排序樹(shù)，其實(shí)質(zhì)上對(duì)關(guān)鍵字進(jìn)行排序。

4.二叉排序樹(shù)查找的程序?qū)崿F(xiàn):

5. 二叉排序樹(shù)的刪除:

假設(shè)被刪結(jié)點(diǎn)是*p，其雙親是*f，不失一般性，設(shè)*p是*f的左孩子，下面分三種情況討論：

⑴ 若結(jié)點(diǎn)*p是葉子結(jié)點(diǎn)，則只需修改其雙親結(jié)點(diǎn)*f的指針即可。

⑵ 若結(jié)點(diǎn)*p只有左子樹(shù)PL或者只有右子樹(shù)PR，則只要使PL或PR 成為其雙親結(jié)點(diǎn)的左子樹(shù)即可。

⑶ 若結(jié)點(diǎn)*p的左、右子樹(shù)均非空，先找到*p的中序前趨結(jié)點(diǎn)*s（注意*s是*p的左子樹(shù)中的最右下的結(jié)點(diǎn)，它的右鏈域?yàn)榭眨缓笥袃煞N做法：

① 令*p的左子樹(shù)直接鏈到*p的雙親結(jié)點(diǎn)*f的左鏈上,而*p的右子樹(shù)鏈到*p的中序前趨結(jié)點(diǎn)*s的右鏈上。

② 以*p的中序前趨結(jié)點(diǎn)*s代替*p（即把*s的數(shù)據(jù)復(fù)制到*p中），將*s的左子樹(shù)鏈到*s的雙親結(jié)點(diǎn)*q的左（或右）鏈上。

6. 刪除算法演示 :

7. 二叉排序樹(shù)的查找:

在二叉排序樹(shù)中進(jìn)行查找的過(guò)程和二分查找類(lèi)似，也是一個(gè)逐步縮小查找范圍的過(guò)程。若查找成功，則是走了一條從根結(jié)點(diǎn)到待查結(jié)點(diǎn)的路徑；若查找失敗，則是走了一條根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)的路徑。因此，查找過(guò)程中和關(guān)鍵字比較的次數(shù)不超過(guò)樹(shù)的深度。

由于含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)不唯一，形態(tài)和深度可能不同。故含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形態(tài)有關(guān)。

最好的情況是： 二叉排序樹(shù)和二叉判定樹(shù)形態(tài)相同。

最壞的情況是： 二叉排序樹(shù)為單支樹(shù)，這時(shí)的平均查找長(zhǎng)度和順序查找時(shí)相同。

最壞情況示例

就平均性能而言，

二叉排序樹(shù)上的查找和二分查找相差不大，并且二叉排序樹(shù)上的插入和刪除結(jié)點(diǎn)十分方便，無(wú)須大量移動(dòng)結(jié)點(diǎn)。

二叉排序樹(shù)查找

若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。

否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹(shù)。

若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹(shù)。

若子樹(shù)為空，查找不成功。

插入算法：

首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。

判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。

若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。

注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。

void InsertBST(t，key)

//在二叉排序樹(shù)中插入查找關(guān)鍵字key

{

if(t==NULL){

t=new BiTree;

t->lchild=t->rchild=NULL;

t->data=key;

return; }

if(keydata ) InsertBST(t->lchild,key);

else InsertBST (t->rchild, key );

}

void CreateBiTree(tree,d【 】,n）

//n個(gè)數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹(shù)根

{tree=NULL;

for(i=0;i InsertBST(tree,d);

}

在計(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ù))

換句話說(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ì)由于查詢而改變。(這是與伸展樹(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