二叉排序树在网上商品信息检索中的应用

　　 [摘要]随着互联网的普及应用，网上购物得到了迅猛发展，而网上商品信息的检索量却也随之与日俱增，如何提高商品信息检索效率已成为急需解决的问题，本文提出一种基于二叉排序树的商品信息动态检索方法，不仅提高了商品信息的检索效率，而且还可以根据用户的检索信息量判断出用户的购买需求，并反馈给管理者，为企业的发展起到了导向作用。
　　[关键词]二叉排序树平衡二叉树平衡因子
　　
　　一、问题的提出
　　目前大多数的网上购物系统采用的是B/S(浏览器/服务器)结构的管理软件，其数据库表的查询操作大部分使用的是顺序查找法，即从第一行记录顺序的查找到满足查询条件的记录，这种查找方法算法简单，对表结构无任何要求但是当数据量的很大时，查找的时间复杂度很大，查找效率会很低。为此本文提出了基于二叉排序树的商品信息动态检索方法。
　　二、问题的分析与实现
　　1.构造二叉排序树
　　二叉排序树，又称BST树，它是一种特殊的二叉树，其具有的特点：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；(2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；(3)左、右子树本身又各是一棵二叉排序树。根据数据库商品表中商品名称的首字母信息(字符ASCII码的大小)，构造二叉排序树。例如我们在商品表中搜索到五条记录分别是：海尔冰箱、诺基亚手机、富士宝电磁炉、燕京啤酒、喜之郎果冻。提取出它们名称首字母的前两项，构造一个线性表(HE,NJ,FS,YJ,XZ),以表中第一个元素HE为根结点，以后的各个数据，逐个插入结点，在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求，构造出二叉排序树如图1所示，并按照二叉排序树的原理建立对应的二叉树商品关系表，如表1所示。
　　其中COMMODITYNAME表示商品名称；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