顧衛(wèi)杰，錢月霞

（常州機(jī)電職業(yè)技術(shù)學(xué)院，江蘇 常州213164）

二叉排序樹(shù)在動(dòng)態(tài)檢索中的應(yīng)用研究

顧衛(wèi)杰，錢月霞

（常州機(jī)電職業(yè)技術(shù)學(xué)院，江蘇 常州213164）

在信息系統(tǒng)廣泛應(yīng)用的今天，數(shù)據(jù)查詢的效率越來(lái)越受人們關(guān)注，以往的順序查找法查詢效率低，很難滿足大數(shù)據(jù)量的查詢，本文提出一種基于二叉排序樹(shù)的動(dòng)態(tài)檢索方法，并結(jié)合實(shí)例，闡述了二叉排序樹(shù)的構(gòu)造、平衡、查詢等操作，大大提高了檢索效率。

二叉排序樹(shù)；動(dòng)態(tài)檢索；平衡

隨著計(jì)算機(jī)技術(shù)的發(fā)展，電子商務(wù)成為新的商業(yè)媒介，各類信息系統(tǒng)應(yīng)運(yùn)而生，數(shù)據(jù)檢索成為信息系統(tǒng)中最頻繁典型的操作，如何提高查詢效率成了各類信息系統(tǒng)急待解決的問(wèn)題。目前大多數(shù)信息系統(tǒng)對(duì)數(shù)據(jù)庫(kù)表的查詢操作采用的是順序查找法，即用所給關(guān)鍵字與數(shù)據(jù)庫(kù)表中記錄按順序逐個(gè)比較，直到查找到滿足條件的記錄，時(shí)間復(fù)雜度為O（n）[1]，這種方法最容易實(shí)現(xiàn)，但當(dāng)數(shù)據(jù)量很大時(shí)，查詢效率很低。二分法查找是另一種查找方法，它要求線性表中的結(jié)點(diǎn)按關(guān)鍵字值升序或降序排列，查找時(shí)不必逐個(gè)順序比較，直接與中間位置的關(guān)鍵字比較，若相同，則查找成功，若給定值大于該關(guān)鍵字的值，則在后半部分進(jìn)行折半查找，否則在前半部進(jìn)行折半查找，二分查找效率較高，時(shí)間復(fù)雜度為O（log n），但對(duì)數(shù)據(jù)的存儲(chǔ)格式有要求，必須是順序存儲(chǔ)。本文提出了一種基于二叉排序樹(shù)的動(dòng)態(tài)檢索方法，并以超市管理系統(tǒng)為例，給出二叉排序樹(shù)的應(yīng)用過(guò)程。該方法查找效率類似于二分法，對(duì)于數(shù)據(jù)需要頻繁增加、刪除時(shí)，可以很方便的實(shí)現(xiàn)。

1 二叉排序樹(shù)的構(gòu)造

1.1 二叉排序樹(shù)的特點(diǎn)

二叉排序樹(shù)（Binary Search Tree），是具有下列性質(zhì)的二叉樹(shù)：①若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；②若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；③它的左、右子樹(shù)也分別為二叉排序樹(shù)。

作用于二叉排序樹(shù)上的基本操作的時(shí)間與樹(shù)的高度成正比，對(duì)一棵含n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，這些操作的最壞情況運(yùn)行時(shí)間為O（log n），但如果樹(shù)是含n個(gè)節(jié)點(diǎn)的線性鏈，則這些操作的最壞情況運(yùn)行時(shí)間為O（n）。

1.2 二叉排序樹(shù)的構(gòu)造方法

根據(jù)數(shù)據(jù)表中的信息，我們可以建立二叉排序樹(shù)，表中的每行記錄看成一個(gè)包含若干數(shù)據(jù)項(xiàng)的數(shù)據(jù)結(jié)點(diǎn)，為這個(gè)結(jié)點(diǎn)設(shè)置ID （結(jié)點(diǎn)編號(hào)）、NAME（結(jié)點(diǎn)名稱）、FATHERINFO（結(jié)點(diǎn)的父結(jié)點(diǎn)信息）、SONINFO（結(jié)點(diǎn)與父結(jié)點(diǎn)關(guān)系信息）等屬性，用FATHERINFO字段表示出該結(jié)點(diǎn)的父結(jié)點(diǎn)信息，用SONINFO字段表示出該結(jié)點(diǎn)是左子樹(shù)還是右子樹(shù)，當(dāng)FATHERINFO字段為NULL時(shí)，表示該節(jié)點(diǎn)為根結(jié)點(diǎn)，SONINFO字段用0和1分別表示該結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。如表1建立的COMMODITY_TREE表結(jié)構(gòu)。

表1 COMMODITY_TREE表結(jié)構(gòu)

1.3 構(gòu)造實(shí)例

根據(jù)超市管理系統(tǒng)中商品信息表里的數(shù)據(jù)，我們選用毛巾、香皂、卡通書、電飯鍋、籃球、按摩器六件商品為例來(lái)說(shuō)明構(gòu)造過(guò)程。把以上六種商品的信息補(bǔ)充到COMMODITY_TREE中，可得到表2，其中FATHERINFO和SONINFO中的值可根據(jù)二叉排序樹(shù)的性質(zhì)獲取，構(gòu)造的二叉排序樹(shù)如圖1。

表2 COMMODITY_TREE關(guān)系表

2 二叉排序樹(shù)的平衡

2.1 二叉排序樹(shù)平衡算法

二叉排序樹(shù)方便查找、插入、刪除等操作，其復(fù)雜度為O（log n），但這是個(gè)“期望值”，如果二叉排序樹(shù)失去平衡，相應(yīng)的查找時(shí)間將增加，在最壞情況下，如果插入的關(guān)鍵字有序時(shí)，構(gòu)造的二叉排序樹(shù)變成單支樹(shù)，平均查找時(shí)間變成 （n+1）/2。因此必須對(duì)二叉排序樹(shù)進(jìn)行平衡操作，使之成為“平衡二叉排序樹(shù)”，在“平衡二叉排序樹(shù)”中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別為1，節(jié)點(diǎn)的平衡因子是它的右子樹(shù)的高度減去它的左子樹(shù)的高度。平衡因子為 1、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的，否則該節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個(gè)樹(shù)[2]。

平衡調(diào)整的算法是旋轉(zhuǎn)法，分別針對(duì)不同失衡結(jié)構(gòu)采用 LL（順時(shí)針）旋轉(zhuǎn)、RR（逆時(shí)針）旋轉(zhuǎn)、LR（先順后逆）、RL（先逆后順）4種轉(zhuǎn)法，使其達(dá)到平衡狀態(tài)。本文給出LL（順時(shí)針）旋轉(zhuǎn)的圖解表示，如圖3所示。

2.2 平衡二叉排序樹(shù)

由圖1可看出，該二叉樹(shù)左子樹(shù)高度為3，右子樹(shù)高度為1，根據(jù)該二叉樹(shù)的左右深度之差，求得其平衡因子系數(shù)為-2，所以該二叉樹(shù)不平衡，需要對(duì)其進(jìn)行LL（順時(shí)針）旋轉(zhuǎn)，根據(jù)旋轉(zhuǎn)算法，旋轉(zhuǎn)后樹(shù)形結(jié)構(gòu)如圖2所示，再調(diào)整二叉樹(shù)商品關(guān)系表，如表3所示。

表3 調(diào)整后的COMMODITY_TREE關(guān)系表

3 商品信息的動(dòng)態(tài)操作

3.1 節(jié)點(diǎn)的插入和刪除

插入和刪除節(jié)點(diǎn)會(huì)引起二叉排序樹(shù)表示的動(dòng)態(tài)集合的變化，要反映出這種變化就要修改數(shù)據(jù)結(jié)構(gòu)，但在修改的同時(shí)還要保持二叉排序樹(shù)的性質(zhì)，插入一個(gè)新元素而修改樹(shù)結(jié)構(gòu)相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，但在刪除操作時(shí)情況要復(fù)雜一點(diǎn)。

3.1.1 插入

為將一個(gè)新值 v插入二叉排序樹(shù) T，可調(diào)用過(guò)程TREE-INSERT。傳給該過(guò)程的參數(shù)是個(gè)節(jié)點(diǎn)z，且有key [z]=v，left[z]=NIL，right[z]=NIL。該過(guò)程修改T和z的某些域，并把z插入樹(shù)中的合適位置[3]。算法思想：從根節(jié)點(diǎn)開(kāi)始，沿樹(shù)下降，指針x跟蹤這條路徑，而y始終指向x的父節(jié)點(diǎn)。根據(jù)key[z]與key[x]的值比較結(jié)果，決定向左子樹(shù)或向右子樹(shù)搜索，直到x成為NIL。這個(gè)NIL位置即插入z的地方。算法如下：

3.1.2 刪除

從二叉查找樹(shù)中刪除一個(gè)節(jié)點(diǎn)，可分為三種情況：

（1）節(jié)點(diǎn)是一個(gè)樹(shù)葉，沒(méi)有子女。這種情況，直接刪除即可；

（2）節(jié)點(diǎn)有一個(gè)子女。這種情況，將父節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的引用改為對(duì)其子女的引用即可；

（3）節(jié)點(diǎn)有兩個(gè)子女。如果刪除了該節(jié)點(diǎn)，其下的兩個(gè)子女就成了兩棵孤立的樹(shù)了。有兩種方法可以解決這一問(wèn)題：歸并刪除法和復(fù)制刪除法[4]。

歸并算法的思想：將節(jié)點(diǎn)的兩個(gè)子樹(shù)合并成一棵樹(shù)，然后將它連接到節(jié)點(diǎn)的父節(jié)點(diǎn)上。根據(jù)二叉排序樹(shù)的性質(zhì)，右子樹(shù)中的每個(gè)鍵都大于左子樹(shù)的鍵，因此最好的方法是尋找左子樹(shù)中鍵最大的節(jié)點(diǎn) （即最右邊的一個(gè)節(jié)點(diǎn)），并將其作為右子樹(shù)的父節(jié)點(diǎn)。對(duì)稱地，也可以找到右子樹(shù)中鍵最小的節(jié)點(diǎn)（即最左邊的一個(gè)節(jié)點(diǎn)），并將其作為左子樹(shù)的父節(jié)點(diǎn)。

復(fù)制算法的思想：節(jié)點(diǎn)有兩個(gè)子女時(shí)可以把該節(jié)點(diǎn)左子樹(shù)中的最大節(jié)點(diǎn)（或者右子樹(shù)中的最小節(jié)點(diǎn)）的鍵復(fù)制到該節(jié)點(diǎn)中，并刪除左子樹(shù)的最大節(jié)點(diǎn)（或右子樹(shù)的最小節(jié)點(diǎn)）。這個(gè)算法不會(huì)增加樹(shù)高，但是如果刪除和插入同時(shí)多次進(jìn)行，也存在一個(gè)問(wèn)題：算法是不對(duì)稱的，如果每次都刪除左子樹(shù)的最大節(jié)點(diǎn)，將會(huì)使整棵樹(shù)向右傾斜。為了解決這個(gè)問(wèn)題，可以對(duì)算法的對(duì)稱性作一個(gè)簡(jiǎn)單的改進(jìn)。算法交替地從左子樹(shù)和右子樹(shù)中復(fù)制刪除。

3.2 檢索

將用戶輸入的要查詢的商品名稱轉(zhuǎn)換為各拼音的首字母，與COMMODITY_TREE表中COMMODITY_FN（商品名稱首字母）字段信息依次比較各字母串中的字符，直到找到與用戶輸入商品名稱拼音首字母相同的商品名，若首字母相同，還需進(jìn)一步比較COMMODITY_NAME是否相同，因?yàn)橛锌赡艹霈F(xiàn)不同商品名其首字母相同的情況。

查詢算法如下：

由以上算法得知，查詢的時(shí)間復(fù)雜度為O（log n），優(yōu)于順序查找。當(dāng)對(duì)商品信息進(jìn)行維護(hù)時(shí)，也可以利用動(dòng)態(tài)檢索的方式，根據(jù)二叉排序樹(shù)的添加、刪除的算法對(duì)結(jié)點(diǎn)進(jìn)行操作，然后再判斷是否平衡，并將之調(diào)整為平衡二叉排序樹(shù)。

4 功能的擴(kuò)展

為了便于超市管理者了解客戶的查詢情況，可以在設(shè)計(jì)COMMODITY_TREE表結(jié)構(gòu)時(shí)增加一個(gè)計(jì)數(shù)屬性，把客戶對(duì)商品的查詢次數(shù)記錄下來(lái)，并設(shè)定一個(gè)閾值，及時(shí)提醒商家添加新商品，同時(shí)根據(jù)商品的瀏覽次數(shù)，也可作為進(jìn)貨的依據(jù)，提供決策信息。

5 結(jié) 語(yǔ)

隨著關(guān)系數(shù)據(jù)庫(kù)技術(shù)的應(yīng)用越來(lái)越廣泛，利用數(shù)據(jù)庫(kù)技術(shù)、結(jié)構(gòu)化查詢語(yǔ)言來(lái)研究基于關(guān)系數(shù)據(jù)庫(kù)表格的外存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)有著實(shí)際的意義，二叉排序樹(shù)操作靈活，支持動(dòng)態(tài)查詢，應(yīng)用到數(shù)據(jù)量較大的系統(tǒng)中可以大大提高查詢效率。

[1]魏勇.基于關(guān)系數(shù)據(jù)庫(kù)表樹(shù)的數(shù)據(jù)結(jié)構(gòu)研究[J].深圳信息職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006(3).

[2]張淵，余小清，萬(wàn)旺根.空間二叉樹(shù)排序查找算法及其在網(wǎng)絡(luò)游戲中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2007(6).

[3]吳洲.散列表構(gòu)造與查找的動(dòng)態(tài)實(shí)現(xiàn) [J].電腦知識(shí)與技術(shù)，2004(12).

[4]黃水松，於朝暉，李世平.一種最佳二叉排序樹(shù)的動(dòng)態(tài)檢索算法[J].武漢大學(xué)學(xué)報(bào)，2000(6).

責(zé)任編輯 王榮輝

The Application Research on Dynamic Search Based on Binary Search Tree

GU Weijie，QIAN Yuexia
（Changzhou Institute of Mechatronic Technology,Changzhou Jiangsu 213164，China）

With the widely used of information systems,the efficiency of the data query becomes more and more important.It is difficult to meet the large amount of data query because of the low efficiency of sequential search.This paper presents a dynamic search method based on Binary Search Tree.And it also explains the structure of the tree as well as the method of balance and querying.It really improves the query efficiency.

Binary Search Tree;dynamic search;balance

TP39

A

1674-5787（2010）03-0149-03

2010-03-31

顧衛(wèi)杰（1980—），男，江蘇常州人，碩士，常州機(jī)電職業(yè)技術(shù)學(xué)院，講師，主要研究方向?yàn)閿?shù)據(jù)庫(kù)技術(shù)、軟件工程。