1 问题的提出 目前流行的基于B/S模式的信息系统中对数据库表的查询操作大部分使用的是顺序查找法，即从第一行记录顺序的查找到满足查询条件的记录，由于数据量的巨大，查找的时间复杂度很大[1]。为此论文研究与实现了基于二叉排序树的商品信息动态检索，提高商品信息的查询效率。根据用户的查询信息动态的提取用户的购买需求，反馈给管理者，形成指导企业经营的决策方案的实施计划。2 问题的分析与实现2.1 建树 二叉排序树（Binary Sort Tree），简称BST 树，它是一种特殊的二叉树，其具有的特点：①每个结点左子树上的所有结点的关键字，值均小于该结点的关键字值；②每个结点右子树上的所有结点的关键字，值均大于或等于该结点的关键字值；③左“右子树本身又各是一棵二叉排序树。二叉树的内存表示一般建立在含子树结点的指针基础上，我们这里用关系(二维表)的方法表示该二叉树。根据其数据库的商品汇总表建立该二叉树商品树表，表结构如表1所示。
表1 COMMODITYTREE表结构SQL表示字段名数据类型作用备注COMMODITYIDint 节点的唯一标识COMMODITYNAMEtext商品名称COMMODITYPYvarchar 商品名称首字母FatherInfovarchar该结点的父结点信息SonInfobit该结点与父结点关系信息SearchCountint记录查询次数
将表中的每行记录看成一个包含若干数据项的数据结点，在表FatherInfo 字段中其值为NULL时表示该节点为根结点，SonInfo字段中用0或1分别表示该结点的左子树和右子树，这就和二叉树的内存表示对应起来。 按照二叉排序树的原理，根据COMMODITYTREE表中COMMODITYPY（商品名称首字母）字段的信息将COMMODITY TREE表中的FatherInfo 字段和SonInfo字段补充完整。
2.2 树的平衡化问题 由于BST树的形状取决于各个元素被插入二叉树的先后顺序。一个新的元素作为一个新的结点被添加到二叉树中，有可能导致二叉排序树不平衡，使查询效率降低。平衡二叉排序树，又称为AVL树，它是一棵满足“任何一个结点的左右子树高度差绝对值不超过1”的二叉排序树。某结点的左子树高减去右子树高，称为该结点的平衡因子。平衡二叉树定义了一种机制，当树变得不平衡时，对二叉树进行调整，使之重新变为平衡的。基于这种平衡二叉树结构的查找算法，是目前所有动态查找算法中效率最高的。调整算法是旋转法，分别针对不同失衡结构采用左转、右转、先左转后右转、先右转后左转4种转法，对失衡的二叉树进行调整使其达到平衡状态。
2.3 查询信息的处理 （1）将用户在浏览器上输入的要查询的商品名称转换为各字拼音的首字母。与COMMODITY TREE表中COMMOD ITYPY（商品名称首字母）字段信息依次比较各字母串中的字符，直到找到与用户输入商品名称拼音首字母相同的商品名。若首字母相同，还需进一步比较COMMODITYNAME是否相同，因为有可能出现不同商品名其首字母相同的情况。 （2）在设计之初，建立一个空数据表(NEEDCOMMOD ITY表)用来存储没有查询到的商品，其表结构如表2所示，当该产品被查询次数累计到一定值M（由管理者设定）时，要对管理者进行提醒是否该经销此商品。如果决定经销此商品并开始进货经销，则将其添加到相应的商品汇总表和COMMODITYTREE表。
表2 NEEDCOMMODITY 表结构字段名类型作用备注NEEDCOMMODITYIDint节点的唯一标识NEEDCOMMODITYNAMEtext商品名称NEEDCOMMODITYPYvarchar商品名称首字母SearchCountint记录查询次数
（3）相反地，当商品汇总表中的某商品在一定时间内，被查询的次数未到一定值N（由管理者设定）时，就要对管理者进行提醒该产品是否已经滞销，应该对其进行低价处理等措施。如果一定时间内不打算再经销此商品，则可以从相应的商品汇总表和COMMODITYTREE表中将其删除。
2.4 设计实现 实现平衡二叉排序树的查询算法用Java语言实现，与数据库操作相关语句用SQL语言实现。用JDBC—ODBC与商品数据库建立连接。二叉排序树结点信息的实现算法:Public class BinarySearchTree{BinarySearchTree(){Class．forName(“sun．jdbc．odbc．Jdhc0r1h DriVer”)；connection=DriverManager．getConnection(“jdbc： odbc：tree”)；statement=tatement()；} private BinaryNode root； // 根节点 private BinaryNode find(Comparable x,BinaryNode root) { if( root = = null ) return null； if( eTo( ITYPY )0 ) return find( x, )； else if( eTo( ITYPY )0 ) return find( x, )； 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( eTo( t )0 ) = insert( x, )； else if( eTo( t )0 ) = insert( x, )； else ； // 树root中已有该节点；无操作 return； Update COMMODITYPY fro COMMODITY TREE； }// 将元素插入到二叉排序树rootprivate BinaryNode remove(Comparable x,BinaryNode root) { if( t = = null ) return root； if ( eTo( t )0) = remove( x,)； else if ( eTo( t )0) = remove( x, )； else if ( root. left != null && root. right != null )//两个孩子 { t = findMin(). element； = remove ( )； } else root = ( != null )? : ； return root； Update COMMODITYPY fro COMMODITY TREE； }//二叉排序树删除节点 }
3 实例应用 下面以网上购物系统信息为例，介绍其实现原理。根据COMMODITY TREE表结构形成关系数据表，如表3所示。
表3 COMMODITYTREE关系表COMMODITY IDCOMMODITY NAMECOMMODITYPYFather InfoSon InfoSearch Count1卡西欧运动表KXOYDBNULLNULL02派克墨水笔PKMSBKXOYDB103迪士尼书包DSNSBKXOYDB004跳舞毯TWTPKMSB105李宁牌跑鞋LNPPXPKMSB006卡通电子称KTDZCDSNSB107收纳箱SNXTWT008装饰靠垫ZSKDTWT109按摩器AMQDSNSB0010瑞士军刀RSJDSNX00...........
按照二叉排序树的原理，根据COMMODITYTREE表中COMMODITYPY（商品名称首字母）字段的信息将COMMODITYTREE表中的FatherInfo字段和SonInfo字段补充完整，过程①将第一条记录设为根节点，其Father Info字段和Son Info字段内容均为NULL，即为根节点;②根据各记录的COMMODITYPY字段信息与根结点信息比较，形成如下二叉排序树结构，见图1。图1 关系表的二叉树形表示由图1可见，该二叉树左子树深度HL=2，右子树深度HR=4，根据该二叉树的左右深度之差，求得其平衡因子系数为2，由于平衡树的平衡因子为-1，0，1，所以该二叉树不平衡，需要对其进行旋转，使其达到平衡状态，这样查询效率最高。根据平衡二叉树四种旋转原理对图1进行旋转后树形结构如图2所示。图2 旋转后关系表的平衡二叉树形表示 根据旋转后平衡二叉排序树图形，调整COMMODITY TREE关系表，如表4所示。
表4 调整后COMMODITYTREE关系表
COMMODITY IDCOMMODITY NAMECOMMODITYPYFather InfoSon InfoSearch Count1卡西欧运动表KXOYDBPKMSB002派克墨水笔PKMSBNULLNULL03迪士尼书包DSNSBKXOYDB004跳舞毯TWTPKMSB105李宁牌跑鞋LNPPXKXOYDB106卡通电子称KTDZCDSNSB107收纳箱SNXTWT008装饰靠垫ZSKDTWT109按摩器AMQDSNSB0010瑞士军刀RSJDSNX00............ (注：加粗字体为本次调整过程中变动的记录项)添加结点的操作流程描述：当用户查找商品名为“西铁城手表”的商品时，系统提取该商品名的拼音首字母即“XTCSB”,按照已建好的平衡二叉排序树对其进行动态查找，发现该商品未在COMMODITY TREE关系表中出现，将该商品信息添加到NEEDCOMMODITY 表中，当用户查询此商品次数到达一定数量M时，向经营者报告是否增加该商品的进货，若经营者增加该商品时，将该商品信息添加到商品汇总表和COMMODITYTREE表，根据排序二叉树的原理，将该结点插入。根据平衡化原理判断该排序二叉树是否为平衡排序二叉树，若不是需要对其进行平衡化处理，调整为平衡排序二叉树。 删除结点的操作流程描述：当经营者发现商品名为“收纳箱”的查询次数小于某一值时，经营者决策该商品是否需要停止采购，若是则将商品汇总表和COMMODITYTREE表中的该记录删除，根据平衡化原理判断该排序二叉树是否为平衡排序二叉树，若不是需要对其进行平衡化处理，调整为平衡排序二叉树。
4 结束语 论文讨论了如何用二叉树来表示关系表的问题，并将其应用于B/S模式信息系统研究上，提高查询效率。由于该问题基于B/S模式，所以论文用Java语言实现了平衡二叉排序树的查询算法。并研究了根据用户的查询信息动态的提取用户的购买需求，形成指导企业经营的决策方案的实施计划。随着关系数据库技术的应用越来越广泛，利用数据库技术、结构化查询语言等研究基于关系数据库表格的外存储结构的数据结构有着实际的意义。
参考文献[1] 魏勇. 基于关系数据库表树的数据结构研究[J]. 深圳信息职业技术学院学报2006年9,4(3). 王世民 主编.数据结构与算法分析[M].清华大学出版社,2005年7月. (美)Mark Allen Structures and Algorithm Analysis in Java,2nd ed(英文版)[M].2007.
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。 返回电子论文列表
