二叉排序樹平均查找長(zhǎng)度的精確表達(dá)式

程希明 王昕

[摘 要]查找長(zhǎng)度的精確表達(dá)式，需要對(duì)二叉排序樹的平均查找長(zhǎng)度進(jìn)行詳細(xì)分析，尋找一個(gè)平均查找長(zhǎng)度的精確表達(dá)式及其證明過程。基于二叉樹表，提出歐拉常數(shù)的一種新的計(jì)算方法，對(duì)平均查找長(zhǎng)度精確表達(dá)式進(jìn)行了算例分析，并與其他經(jīng)典平均查找長(zhǎng)度計(jì)算公式加以對(duì)比，驗(yàn)證了其正確性。

[關(guān)鍵詞]二叉排序樹 平均查找長(zhǎng)度 歐拉常數(shù)

[中圖分類號(hào)] TP311.12[文獻(xiàn)標(biāo)識(shí)碼] A[文章編號(hào)] 2095-3437（2015）07-0100-02

《數(shù)據(jù)結(jié)構(gòu)》作為一門介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的核心課程，是信息與計(jì)算科學(xué)相關(guān)專業(yè)的綜合性專業(yè)基礎(chǔ)必修課。樹形結(jié)構(gòu)是該課程的重要內(nèi)容之一，掌握二叉樹的邏輯結(jié)構(gòu)特性、各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍，有助于學(xué)生學(xué)會(huì)對(duì)處理的數(shù)據(jù)建立抽象數(shù)據(jù)類型，并使學(xué)生對(duì)算法的復(fù)雜度有一定的分析能力。

在數(shù)據(jù)處理中，查找是一種經(jīng)常使用的操作方法，樹表中數(shù)據(jù)元素的插入和刪除均需要進(jìn)行查找操作。查找是指在含有若干記錄的表中找出關(guān)鍵字值與給定值相同的記錄。若表中存在這樣的記錄，則查找成功，返回所找到記錄的信息或記錄在表中的位置;否則查找失敗，返回空記錄或空指針。當(dāng)用線性表作為表的組織形式時(shí)，可以有三種查找法，其中二分查找效率最高。但由于二分查找要求表中結(jié)點(diǎn)按關(guān)鍵字有序，且不能用鏈表作存儲(chǔ)結(jié)構(gòu)，因此，當(dāng)表的插入或刪除操作頻繁時(shí)，為維護(hù)表的有序性，勢(shì)必要移動(dòng)表中很多結(jié)點(diǎn)。這種由移動(dòng)結(jié)點(diǎn)引起的額外時(shí)間開銷，就會(huì)抵消二分查找的優(yōu)點(diǎn)。也就是說，二分查找只適用于靜態(tài)查找表，若要對(duì)動(dòng)態(tài)查找表進(jìn)行高效率的查找，可采用二叉排序樹作為表的組織形式。

二叉排序樹，作為樹形結(jié)構(gòu)的一個(gè)重要類型，又稱二叉查找樹，亦稱二叉搜索樹，其存儲(chǔ)結(jié)構(gòu)和算法比較簡(jiǎn)單，特別適合計(jì)算機(jī)處理。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹[1]：（1）它的左子樹上的所有結(jié)點(diǎn)（若存在）的值均小于根結(jié)點(diǎn)的值;（2）它的右子樹上的所有結(jié)點(diǎn)（若存在）的值均不小于根結(jié)點(diǎn)的值;（3）它的左、右子樹也分別為二叉排序樹。

例如，由一組關(guān)鍵字（18，5，20，9，6，27，3）可構(gòu)造如圖1所示的二叉排序樹。

二叉排序樹是一種動(dòng)態(tài)樹表，樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)，查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。

崔尚森等[2]提出了基于表地址前綴分布特點(diǎn)的前綴長(zhǎng)度二分查找方案;秦玉平等[3]給出了常用查找算法平均查找長(zhǎng)度的計(jì)算方法，包括查找成功和查找失敗平均查找長(zhǎng)度的計(jì)算。本文給出了一個(gè)關(guān)于二叉樹平均查找長(zhǎng)度的精確表達(dá)式及其證明過程，并給出了算例驗(yàn)證。

一、二叉樹的平均查找長(zhǎng)度

查找運(yùn)算的主要操作是進(jìn)行關(guān)鍵字的比較，為確定給定關(guān)鍵字在查找表中的位置，需和給定關(guān)鍵字進(jìn)行比較，將比較次數(shù)的期望值稱為平均查找長(zhǎng)度。

假設(shè)任意給定n個(gè)記錄，每個(gè)記錄帶有可比較大小的關(guān)鍵字，將這n個(gè)記錄排成一棵二叉排序樹，假定在查找成功的情況下，要求出這棵二叉排序樹的平均查找長(zhǎng)度。

不妨設(shè)這n個(gè)記錄中有i個(gè)記錄的關(guān)鍵字比第一個(gè)記錄的關(guān)鍵字小，有n-i-1個(gè)記錄的關(guān)鍵字不比第一個(gè)記錄的關(guān)鍵字小，如圖2所示。

由此得到的二叉排序樹在每個(gè)記錄等概率被查的情況下，其平均查找長(zhǎng)度為：

其中P（k）表示含k個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長(zhǎng)度。由于這n個(gè)記錄是任意的，所以它們的排列次序具有隨機(jī)性。

即下列事件：

Ai=“i個(gè)記錄的關(guān)鍵字比第一個(gè)記錄的關(guān)鍵字小，n-i-1個(gè)記錄的關(guān)鍵字比第一個(gè)記錄的關(guān)鍵字小”（i=0，1，2，…，n-1）是等概率出現(xiàn)的。

所以有：

顯然P（0）=0，P（1）=1，當(dāng)n？叟2時(shí)，嚴(yán)蔚敏、吳偉民[4]給出了（1）式的一個(gè)估計(jì)上限：

P（n）？燮1+4logn。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

二、平均查找長(zhǎng)度的精確表達(dá)式

下面，我們給出（1）式的精確表達(dá)式。

引理：如果n？叟2，n？叟k？叟1，則

定理：（1）式中P（n）的表達(dá)式是

證明：在（1）式中計(jì)算P（n）·n2-P（n-1）·（n-1）2的遞推式。

對(duì)（5）式做下列一系列變形：

上列各式連同（5）式左右分別相加，整理得：

利用引理且整理得：

考慮到P（1）=1，所以 ? ? ? ? ? ，從而證明了（4）。

當(dāng)n較大時(shí)，（4）式有一個(gè)近似式：

P（n）=2lnn+2C-3。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

其中C是Eular常數(shù)，0.577215？燮C？燮0.577216。

三、算例驗(yàn)證

我們可以簡(jiǎn)單地驗(yàn)證一下定理的正確性。當(dāng)n=3時(shí)，三個(gè)記錄的排列情況有六種，即γ1<γ2<γ3，γ1<γ3<γ2，γ2<γ1<γ3，γ3<γ1<γ2，γ2<γ3<γ1，γ3<γ2<γ1，六種情況分別對(duì)應(yīng)圖3所示六種排序樹：

圖3（a）、3（b）、3（e）、3（f）所示的四種情況下，排序樹的平均查找長(zhǎng)度都是×（1+2+3）=2;圖3（c）和3（d）兩種情況的平均查找長(zhǎng)度為×（1+2+2）=。以上六種情況出現(xiàn)的概率均等。所以對(duì)三個(gè)結(jié)點(diǎn)的查找表來說，P（3）=×（2×4+×2）=。這與公式（4）式計(jì)算的結(jié)果完全吻合。

[ 參 考 文 獻(xiàn) ]

[1] Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析[M].北京：機(jī)械工業(yè)出版社，2004.

[2] 崔尚森，馮博琴，張白一.一種前綴長(zhǎng)度二分查找的改進(jìn)算法[J].計(jì)算機(jī)工程，2007（15）：70-72.

[3] 秦玉平，王麗君，劉偉.查找算法平均查找長(zhǎng)度的計(jì)算方法[J].渤海大學(xué)學(xué)報(bào)（自然科學(xué)版），2011（4）：354-357.

[4] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1992.

[責(zé)任編輯：鐘偉芳]