二叉排序樹在網上商品信息檢索中的應用

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

[關鍵詞] 二叉排序樹 平衡二叉樹 平衡因子

一、問題的提出

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

二、問題的分析與實現

1.構造二叉排序樹

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

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

2.樹的平衡化問題

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

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

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

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

參考文獻：

[1]曾學軍:淺析B/S和C/S結構的開發與應用[J].電腦知識與技術（學術交流），2007/08

[2]薩師煊 王 珊:數據庫系統概論[M].高等教育出版社，2000/02

[3]嚴蔚敏主編:數據結構[M].清華大學出版社，2007/03

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