二叉查找树在超市商品信息检索中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇二叉查找树在超市商品信息检索中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：随着超市管理信息系统在超市经营中的普及应用，数据检索成为超市管理信息系统中最频繁典型的操作。如何提高商品信息检索效率成了各类超市管理信息系统急待解决的问题，本文提出一种基于二叉查找树的商品信息动态检索方法，不仅提高了商品信息的检索效率，而且还可以根据用户的检索信息量判断出用户的购买需求，并反馈给管理者，为企业的发展起到了导向作用。

关键词：信息检索；二叉查找树；平衡二叉树；平衡因子

Abstract：Along with the supermarket management information system in the supermarket business in the wider application, data retrieval has become one of the most frequent supermarket management information system in typical operation. How to improve the commodity information retrieval efficiency into all kinds of supermarket management information system urgently needs to solve the problem, this paper presents a method based on two binary search trees commodity information dynamic retrieval methods, not only improve the commodity information retrieval efficiency, but also based on the user's retrieval information quantity determine the user 's demand, and feedback to management, for the development of enterprises has played a guiding role.

Key words：Information retrieval；Two binary search trees；Balance two forks tree；Balance factor

中图分类号：TP18文献标识码：A 文章编号：2095-2104（2012）

1 问题的提出

超市形式在我国于20世纪90年初期起步，现已成为我国零售业一种重要形态，随着超市形态的高速发展，其经营管理也变得愈加复杂。日常所需数据量也逐渐增大，原始的人工管理已无法应对复杂的市场。于是，各类超市信息管理系统应运而生，而数据检索成为超市管理信息系统中最频繁典型的操作。如何提高商品信息效率成为各类超市管理信息系统急待解决的问题。目前大多数的超市管理信息系统中数据库表的检索操作大部分使用的是顺序表查找和折半查找两种方法，这两种查找方法均是静态查找。顺序表查找即从表中最后一个记录开始逐个进行记录的关键字和待检索值的比较，若某个记录关键字和待检索值比较相等，则查找成功；反之若直至第一个记录，其关键字和待检索值比较都不想等，则表明表中没有所查记录，查找不成功，这种查找方法算法简单，对表结构无任何要求。但是当数据量很大时，查找的时间复杂度会很大，查找效率会很低 [1]。折半查找是另一种查找的方法，它需要先确定待检索记录所在的区间，以区间中间位置记录的关键字与待检索值进行比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于待检索值或者查找区间的大小小于零时（表明查找不成功）为止[1]。折半查找效率较高，但对数据的存储格式有要求。必须是顺序存储。通过分析以上两种查找方法中各自存在的问题，我们提出了基于二叉查找树的商品信息检索方法。

2 问题的分析与实现

2.1构造二叉查找树

二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

二叉查找树，它是一种特殊的二叉树，其具有的特点：① 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ② 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③ 左、右子树本身又各是一棵二叉查找树。其构造方法如下：原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求，根据超市信息管理系统商品表中商品名称的首字母信息(字符ASCII码的大小)，构造二叉查找树。例如我们在商品表中搜索到五条记录分别是：海信电视、耐克休闲服、苹果手机、张裕葡萄酒、帅康抽油烟机。提取出它们名称首字母的前两项，构造一个线性表S(HX,NK,PG,ZY,SK) ,若将线性表S构造为一棵二叉查找树T需首先插入结点HX为二叉查找树T的根结点，其次插入结点NK，因为结点NK首字母N的ASCII码的值为大于结点HX首字母H的ASCII码的值,则将结点NK作为一个叶子结点插入到结点HX右子树根结点的位置；同样的结点PG, 作为一个叶子结点插入到结点NK右子树根结点的位置；结点ZY, 作为一个叶子结点插入到结点PG右子树根结点的位置；因为结点SK首字母S的ASCII码的值为小于结点ZY首字母Z的ASCII码的值,则将结点SK作为一个叶子结点插入到结点ZY左子树根结点的位置。构造二叉查找树T过程如图1所示。

图1

按照二叉查找树的原理建立对应的二叉树商品关系表，如表1所示。

表1

其中Father表示该结点的父结点信息，当字段值为NULL时表示该结点为根结点；SonInfo表示该结点与父结点关系信息，字段中用0或1分别表示该结点为其父结点的左子树和右子树，这就和二叉树的内存表示对应起来。

2.2 树的平衡化问题

平衡二叉树，又称为AVL树，它是一棵具有下列性质的二叉树：（1）它的左右子树深度之差的绝对值不大于1；（2）它的左右子树也是平衡二叉树[2]。

二叉树结点的平衡因子是二叉树上某结点的左子树深度减去它的右子树深度，所以，若某二叉树是平衡二叉树，其所有结点的平衡因子只能是-1，0，1[2]。

平衡二叉树定义了一种机制，当二叉树变得不平衡时，对其进行调整，使之重新变为平衡的。这种平衡二叉树结构的查找算法，在目前所有动态查找算法中效率是比较高的。调整算法是旋转法，分别针对不同失衡结构采用LL(顺时针)旋转、RR(逆时针)旋转、LR(先顺后逆)、RL(先逆后顺)4种转法，使其达到平衡状态[3]。分析图1可得，二叉查找树T左子树高度HL=0，右子树高度HR=4，则二叉查找树T的左右子树深度之差为-4，绝对值大于1，所以该二叉树不平衡，需要对其进行旋转，其旋转过程为：只有一个结点HX的树显然是平衡二叉树，再插入结点NK之后仍是平衡的，只是根结点的平衡因子由0变为-1；再继续插入结点PG之后，结点HX的平衡因子由-1变为-2，出现了不平衡的二叉树。此时，好比一根扁担出现一头重一头轻的现象，若能将扁担的支撑点由结点HX改为结点NK，扁担的两头就平衡了，因此可以对树做一个向左逆时针“旋转”的操作，令结点NK为根结点，而结点HX为它的左子树，结点PG为它的右子树如图2所示。此时，结点HX和NK的平衡因子都为0，而且仍保持二叉查找树的特性.

图2

继续插入ZY和SK两结点如图3所示，由于结点PG的平衡因子由-1变成-2，查找树中出现了新的不平衡，需进行调整。但此时由于结点SK插在结点ZY的左子树上，因此不能如上做简单调整。对于以结点PG为根的子树来说，若要保持平衡，必须以结点SK作为根结点，而使结点PG为它左子树的根，结点ZY为它右子树的根，从而使二叉查找树由不平衡转化为平衡。得到的平衡二叉树如图4所示。

图3图4

表2

如果某新商品(未被储存于数据库商品表中)被查询次数累计到一定值N（由管理者设定）时，要对管理者进行提醒是否该经销此商品。如果决定经销此商品并开始进货经销，则将其添加到相应的数据库商品表和二叉树商品关系表中。再根据二叉查找树的原理，将该结点插入。最后判断新的二叉查找树是否为平衡二叉树，若不是需要对其进行平衡化处理，调整为平衡二叉树。

相反地，当商品数据库中的某商品在一定时间内，被查询的次数未到一定值W（由管理者设定）时，就要对管理者进行提醒该产品是否已经滞销，应该对其进行低价处理等措施。如果一定时间内不打算再经销此商品，则可以从相应的数据库商品表和二叉树商品关系表中将其删除。再根据二叉查找树的原理，将该结点删除。最后判断新的二叉查找树是否为平衡二叉树，若不是需要对其进行平衡化处理，调整为平衡二叉树。

将基于二叉查找树的商品信息动态检索方法应用于超市管理信息系统的研究中不仅很大程度的提高了数据库中商品信息的检索效率，而且通过研究商品的被检索量，判断出商品的需求率，并及时地反馈给经营者，为企业减少损失、调整经营方向起到了积极作用。

参考文献:

[1] 萨师煊,王珊.数据库系统概论[M],高等教育出版社2006/05

[2] 严蔚编.数据结构[M].清华大学出版社,2007/03

注：文章内所有公式及图表请以PDF形式查看。