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

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

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

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

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

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

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

隨著計(jì)算機(jī)技術(shù)的發(fā)展，電子商務(wù)成為新的商業(yè)媒介，各類信息系統(tǒng)應(yīng)運(yùn)而生，數(shù)據(jù)檢索成為信息系統(tǒng)中最頻繁典型的操作，如何提高查詢效率成了各類信息系統(tǒng)急待解決的問題。目前大多數(shù)信息系統(tǒng)對(duì)數(shù)據(jù)庫表的查詢操作采用的是順序查找法，即用所給關(guān)鍵字與數(shù)據(jù)庫表中記錄按順序逐個(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ǔ)。本文提出了一種基于二叉排序樹的動(dòng)態(tài)檢索方法，并以超市管理系統(tǒng)為例，給出二叉排序樹的應(yīng)用過程。該方法查找效率類似于二分法，對(duì)于數(shù)據(jù)需要頻繁增加、刪除時(shí)，可以很方便的實(shí)現(xiàn)。

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

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

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

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

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

根據(jù)數(shù)據(jù)表中的信息，我們可以建立二叉排序樹，表中的每行記錄看成一個(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)是左子樹還是右子樹，當(dāng)FATHERINFO字段為NULL時(shí)，表示該節(jié)點(diǎn)為根結(jié)點(diǎn)，SONINFO字段用0和1分別表示該結(jié)點(diǎn)的左子樹和右子樹。如表1建立的COMMODITY_TREE表結(jié)構(gòu)。

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

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

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

表2 COMMODITY_TREE關(guān)系表

2 二叉排序樹的平衡

2.1 二叉排序樹平衡算法

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

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

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

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

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

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

3.1.1 插入

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

3.1.2 刪除

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

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

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

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

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

復(fù)制算法的思想：節(jié)點(diǎn)有兩個(gè)子女時(shí)可以把該節(jié)點(diǎn)左子樹中的最大節(jié)點(diǎn)（或者右子樹中的最小節(jié)點(diǎn)）的鍵復(fù)制到該節(jié)點(diǎn)中，并刪除左子樹的最大節(jié)點(diǎn)（或右子樹的最小節(jié)點(diǎn)）。這個(gè)算法不會(huì)增加樹高，但是如果刪除和插入同時(shí)多次進(jìn)行，也存在一個(gè)問題：算法是不對(duì)稱的，如果每次都刪除左子樹的最大節(jié)點(diǎn)，將會(huì)使整棵樹向右傾斜。為了解決這個(gè)問題，可以對(duì)算法的對(duì)稱性作一個(gè)簡(jiǎn)單的改進(jìn)。算法交替地從左子樹和右子樹中復(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ù)二叉排序樹的添加、刪除的算法對(duì)結(jié)點(diǎn)進(jìn)行操作，然后再判斷是否平衡，并將之調(diào)整為平衡二叉排序樹。

4 功能的擴(kuò)展

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

5 結(jié) 語

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

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

[2]張淵，余小清，萬旺根.空間二叉樹排序查找算法及其在網(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]黃水松，於朝暉，李世平.一種最佳二叉排序樹的動(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ù)庫技術(shù)、軟件工程。