基于二叉排序树的商品信息动态检索研究

目前流行的基于B/S模式的信息系统中对数据库表的查询操作大部分使用的是顺序查找法，即从第一行记录顺序的查找到满足查询条件的记录，由于数据量的巨大，查找的时间复杂度很大[1]。为此论文研究与实现了基于二叉排序树的商品信息动态检索，提高商品信息的查询效率。根据用户的查询信息动态的提取用户的购买需求，反馈给管理者，形成指导企业经营的决策方案的实施计划。

2 问题的分析与实现

2.1 建树

二叉排序树（Binary Sort Tree），简称BST 树，它是一种特殊的二叉树，其具有的特点：①每个结点左子树上的所有结点的关键字，值均小于该结点的关键字值；②每个结点右子树上的所有结点的关键字，值均大于或等于该结点的关键字值；③左“右子树本身又各是一棵二叉排序树。二叉树的内存表示一般建立在含子树结点的指针基础上，我们这里用关系(二维表)的方法表示该二叉树。根据其数据库的商品汇总表建立该二叉树商品树表，表结构如表1所示。

表1 COMMODITYTREE表结构SQL表示

将表中的每行记录看成一个包含若干数据项的数据结点，在表FatherInfo 字段中其值为NULL时表示该节点为根结点，SonInfo字段中用0或1分别表示该结点的左子树和右子树，这就和二叉树的内存表示对应起来。

按照二叉排序树的原理，根据COMMODITYTREE表中COMMODITYPY（商品名称首字母）字段的信息将COMMODITY TREE表中的FatherInfo 字段和SonInfo字段补充完整。

由于BST树的形状取决于各个元素被插入二叉树的先后顺序。一个新的元素作为一个新的结点被添加到二叉树中，有可能导致二叉排序树不平衡，使查询效率降低。平衡二叉排序树，又称为AVL树，它是一棵满足“任何一个结点的左右子树高度差绝对值不超过1”的二叉排序树。某结点的左子树高减去右子树高，称为该结点的平衡因子。平衡二叉树定义了一种机制，当树变得不平衡时，对二叉树进行调整，使之重新变为平衡的。基于这种平衡二叉树结构的查找算法，是目前所有动态查找算法中效率最高的。调整算法是旋转法，分别针对不同失衡结构采用左转、右转、先左转后右转、先右转后左转4种转法，对失衡的二叉树进行调整使其达到平衡状态。

（1）将用户在浏览器上输入的要查询的商品名称转换为各字拼音的首字母。与COMMODITY TREE表中COMMOD ITYPY（商品名称首字母）字段信息依次比较各字母串中的字符，直到找到与用户输入商品名称拼音首字母相同的商品名。若首字母相同，还需进一步比较COMMODITYNAME是否相同，因为有可能出现不同商品名其首字母相同的情况。

（2）在设计之初，建立一个空数据表(NEEDCOMMOD ITY表)用来存储没有查询到的商品，其表结构如表2所示，当该产品被查询次数累计到一定值M（由管理者设定）时，要对管理者进行提醒是否该经销此商品。如果决定经销此商品并开始进货经销，则将其添加到相应的商品汇总表和COMMODITYTREE表。

表2 NEEDCOMMODITY 表结构

（3）相反地，当商品汇总表中的某商品在一定时间内，被查询的次数未到一定值N（由管理者设定）时，就要对管理者进行提醒该产品是否已经滞销，应该对其进行低价处理等措施。如果一定时间内不打算再经销此商品，则可以从相应的商品汇总表和COMMODITYTREE表中将其删除。

实现平衡二叉排序树的查询算法用Java语言实现，与数据库操作相关语句用SQL语言实现。用JDBC—ODBC与商品数据库建立连接。二叉排序树结点信息的实现算法:

Public class BinarySearchTree

{

BinarySearchTree(){

Class．forName(“sun．jdbc．odbc．Jdhc0r1h DriVer”)；

connection=DriverManager．getConnection(“jdbc： odbc：tree”)；

statement=connection.creatStatement()；

}

private BinaryNode root； // 根节点

private BinaryNode find(Comparable x,BinaryNode root)

{

if( root = = null )

return null；

if( x.compareTo( root.COMMODITYPY )0 )

return find( x,root.left )；

else if( x.compareTo( root.COMMODITYPY )0 )

return find( x,root.right )；

else

return root； //匹配

Update COMMODITYPY fro COMMODITY TREE ；

}//在树root中查找关键字为x的节点

private BinaryNode insert(Comparable x,BinaryNode root)

{

if( root = = null )

root = new BinaryNode( x,null,null )；

else if( x.compareTo( root.element )0 )

root.left = insert( x,root.left )；

else if( x.compareTo( root.element )0 )

root.right = insert( x,root.right )；

else

； // 树root中已有该节点；无操作

return；

Update COMMODITYPY fro COMMODITY TREE；

}// 将元素插入到二叉排序树root

private BinaryNode remove(Comparable x,BinaryNode root)

{

if( t = = null )

return root；

if ( x.compareTo( root.element )0)

root.left = remove( x,root.left)；

else if ( x.compareTo( root.element )0)

root.right = remove( x,root.right )；

else if ( root. left != null && root. right != null )//两个孩子

{

root.element = findMin(root.right). element；

root.right = remove ( x.root.righr )；

}

else