二叉排序樹查找主題

二叉排序樹查找

1.二叉排序樹的概念:

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

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

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

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

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

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

2.二叉排序樹的插入:

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

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

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

若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，

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

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

3. 二叉排序樹生成：

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

說明：

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

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

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

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

5. 二叉排序樹的刪除:

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

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

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

⑶ 若結(jié)點(diǎn)*p的左、右子樹均非空，先找到*p的中序前趨結(jié)點(diǎn)*s（注意*s是*p的左子樹中的最右下的結(jié)點(diǎn)，它的右鏈域?yàn)榭眨?，然后有兩種做法：

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

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

6. 刪除算法演示 :

7. 二叉排序樹的查找:

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

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

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

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

最壞情況示例

就平均性能而言，

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

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

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

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

若子樹為空，查找不成功。

插入算法：

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

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

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

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

void InsertBST(t，key)

//在二叉排序樹中插入查找關(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為二叉排序樹根

{tree=NULL;

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

}

在計(jì)算機(jī)科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis，他們?cè)?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)最近，且平衡因子絕對(duì)值超過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ì)由于查詢而改變。(這是與伸展樹查找相對(duì)立的，它會(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