二叉排序數(shù)

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)榭眨?，然后有兩種做法：

① 令*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ò)程和二分查找類似，也是一個(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ù)查找