二叉排序樹在網(wǎng)上商品信息檢索中的應(yīng)用

[摘 要] 隨著互聯(lián)網(wǎng)的普及應(yīng)用，網(wǎng)上購物得到了迅猛發(fā)展，而網(wǎng)上商品信息的檢索量卻也隨之與日俱增，如何提高商品信息檢索效率已成為急需解決的問題，本文提出一種基于二叉排序樹的商品信息動態(tài)檢索方法，不僅提高了商品信息的檢索效率，而且還可以根據(jù)用戶的檢索信息量判斷出用戶的購買需求，并反饋給管理者，為企業(yè)的發(fā)展起到了導(dǎo)向作用。

[關(guān)鍵詞] 二叉排序樹 平衡二叉樹 平衡因子

一、問題的提出

目前大多數(shù)的網(wǎng)上購物系統(tǒng)采用的是B/S(瀏覽器/服務(wù)器)結(jié)構(gòu)的管理軟件，其數(shù)據(jù)庫表的查詢操作大部分使用的是順序查找法，即從第一行記錄順序的查找到滿足查詢條件的記錄，這種查找方法算法簡單，對表結(jié)構(gòu)無任何要求但是當數(shù)據(jù)量的很大時，查找的時間復(fù)雜度很大，查找效率會很低。為此本文提出了基于二叉排序樹的商品信息動態(tài)檢索方法。

二、問題的分析與實現(xiàn)

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

二叉排序樹，又稱BST 樹，它是一種特殊的二叉樹，其具有的特點：(1)若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；(2)若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；(3)左、右子樹本身又各是一棵二叉排序樹。根據(jù)數(shù)據(jù)庫商品表中商品名稱的首字母信息(字符ASCII碼的大小)，構(gòu)造二叉排序樹。例如我們在商品表中搜索到五條記錄分別是：海爾冰箱、諾基亞手機、富士寶電磁爐、燕京啤酒、喜之郎果凍。提取出它們名稱首字母的前兩項，構(gòu)造一個線性表(HE，NJ，F(xiàn)S，YJ，XZ) ，以表中第一個元素HE為根結(jié)點，以后的各個數(shù)據(jù)，逐個插入結(jié)點，在插入過程的每一步，原有樹結(jié)點位置不再變動，只是將新數(shù)據(jù)的結(jié)點作為一個葉子結(jié)點插入到合適的位置，使樹中任何結(jié)點的數(shù)據(jù)與其左、右子樹結(jié)點數(shù)據(jù)之間的關(guān)系仍然符合對二叉排序樹的要求，構(gòu)造出二叉排序樹如圖1所示，并按照二叉排序樹的原理建立對應(yīng)的二叉樹商品關(guān)系表，如表1所示。

其中COMMODITY NAME表示商品名稱；COMMODITYPY表示商品名稱首字母；Father表示該結(jié)點的父結(jié)點信息，當字段值為NULL時表示該結(jié)點為根結(jié)點；SonInfo表示該結(jié)點與父結(jié)點關(guān)系信息，字段中用0或1分別表示該結(jié)點為其父結(jié)點的左子樹和右子樹，這就和二叉樹的內(nèi)存表示對應(yīng)起來。

2.樹的平衡化問題

平衡二叉樹，又稱為AVL樹，它是一棵滿足“任何一個結(jié)點的左右子樹高度差絕對值不超過1”的二叉排序樹。樹中某結(jié)點的左子樹高度減去右子樹高度，稱為該結(jié)點的平衡因子。AVL樹定義了一種機制，當二叉樹變得不平衡時，對其進行調(diào)整，使之重新變?yōu)槠胶獾??；谶@種平衡二叉樹結(jié)構(gòu)的查找算法，在目前所有動態(tài)查找算法中效率是比較高的。調(diào)整算法是旋轉(zhuǎn)法，分別針對不同失衡結(jié)構(gòu)采用LL(順時針)旋轉(zhuǎn)、RR(逆時針)旋轉(zhuǎn)、LR(先順后逆)、RL(先逆后順)4種轉(zhuǎn)法，使其達到平衡狀態(tài)。由圖1可見，該二叉樹左子樹高度HL=1，右子樹高度HR=3，根據(jù)該二叉樹的左右深度之差，求得其平衡因子系數(shù)為-2，其絕對值大于1，所以該二叉樹不平衡，需要對其進行旋轉(zhuǎn)。根據(jù)平衡二叉樹四種旋轉(zhuǎn)原理對圖1進行旋轉(zhuǎn)后樹形結(jié)構(gòu)如圖2所示。根據(jù)旋轉(zhuǎn)后平衡二叉排序樹圖形，調(diào)整二叉樹商品關(guān)系表，如表2所示。

如果某新商品(未被儲存于數(shù)據(jù)庫商品表中)被查詢次數(shù)累計到一定值N（由管理者設(shè)定）時，要對管理者進行提醒是否該經(jīng)銷此商品。如果決定經(jīng)銷此商品并開始進貨經(jīng)銷，則將其添加到相應(yīng)的數(shù)據(jù)庫商品表和二叉樹商品關(guān)系表中。再根據(jù)二叉排序樹的原理，將該結(jié)點插入。最后判斷新的二叉排序樹是否為平衡二叉樹，若不是需要對其進行平衡化處理，調(diào)整為平衡二叉樹。

相反地，當商品數(shù)據(jù)庫中的某商品在一定時間內(nèi)，被查詢的次數(shù)未到一定值W（由管理者設(shè)定）時，就要對管理者進行提醒該產(chǎn)品是否已經(jīng)滯銷，應(yīng)該對其進行低價處理等措施。如果一定時間內(nèi)不打算再經(jīng)銷此商品，則可以從相應(yīng)的數(shù)據(jù)庫商品表和二叉樹商品關(guān)系表中將其刪除。再根據(jù)二叉排序樹的原理，將該結(jié)點刪除。最后判斷新的二叉排序樹是否為平衡二叉樹，若不是需要對其進行平衡化處理，調(diào)整為平衡二叉樹。

將基于二叉排序樹的商品信息動態(tài)檢索方法應(yīng)用于B/S結(jié)構(gòu)的網(wǎng)上購物系統(tǒng)的研究中不僅很大程度的提高了網(wǎng)上商品信息的檢索效率，而且通過研究商品的被檢索量，判斷出商品的需求率，并及時地反饋給經(jīng)營者，為企業(yè)減少損失、調(diào)整經(jīng)營方向起到了積極作用。

參考文獻：

[1]曾學軍:淺析B/S和C/S結(jié)構(gòu)的開發(fā)與應(yīng)用[J].電腦知識與技術(shù)（學術(shù)交流），2007/08

[2]薩師煊 王 珊:數(shù)據(jù)庫系統(tǒng)概論[M].高等教育出版社，2000/02

[3]嚴蔚敏主編:數(shù)據(jù)結(jié)構(gòu)[M].清華大學出版社，2007/03

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文