程希明 王昕

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

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

[中圖分類號] TP311.12[文獻標識碼] A[文章編號] 2095-3437（2015）07-0100-02

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

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

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

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

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

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

一、二叉樹的平均查找長度

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

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

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

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

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

即下列事件：

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

所以有：

顯然P（0）=0，P（1）=1，當n？叟2時，嚴蔚敏、吳偉民[4]給出了（1）式的一個估計上限：

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

二、平均查找長度的精確表達式

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

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

定理：（1）式中P（n）的表達式是

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

對（5）式做下列一系列變形：

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

利用引理且整理得：

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

當n較大時，（4）式有一個近似式：

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

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

三、算例驗證

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

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

[ 參 考 文 獻 ]

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

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

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

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

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