一种基于分类特性和平衡二叉树的数据存储、查询方法

摘要

本发明公布了一种基于分类特性和平衡二叉树的数据存储、查询方法，通过构建平衡二叉树，创建结点；可以按照3种顺序：中序、前序、后续遍历规则，动态地将数据信息分类存储到相应结点；输入查询内容，动态遍历AVL树，得到所需的数据信息。本发明将动态查询的时间复杂度降低到静态查询级别，大大提高了存储和查询的效率，具有速度快、能耗低、占内存少、算法简单的优点，而且可用多种语言实现。该方法广泛适用于通信领域中的数据管理，尤其是物联网通信中大数据量的数据存储和查询。

权利要求

1.一种基于分类特性和平衡二叉树的数据存储、查询方法，其特征在于，包括以下步骤：

1.1构建平衡二叉树，创建结点；

1.2按照遍历的规则，动态地将数据信息存储到相应结点；

1.3输入需要查询的信息，动态遍历平衡二叉树，直到找到所需的数据信息或遍历完平衡二叉树返回查找失败；

所述平衡二叉树为有序的，按照中序、前序或后序的遍历规则，动态地将数据信息存储到相应结点；

连续且满的结点数为n的平衡二叉树，其共有L=log2n级结点，CL为当前级数，DCL为当前级数结点的层距差，层距差为相邻树层之间的结点值的差；那么所有结点的中序遍历L -1公式为：根结点Pr= 2 ，当前结点的父节点为PF,其左孩子PL = PF- DCL,其右孩子PR = L-CL-1PF +DCL, DCL = 2 ,CL∈[1，L)；前序遍历公式为：Pr= 1，PL = PF+1, PR = PF +DCL, DCL = L-CL L L-CL

2 ,CL∈[1，L)；后序遍历公式为：Pr= 2-1，PL = PF-DCL, PR = PF-1, DCL = 2 ,CL∈[1，L)所述步骤1.1，按如下方法实现：首先按照平衡二叉树的建树规则构建一个节点数为n，树高为log2n的平衡二叉树，然后增加结点，每一个结点代表一个特征类C1、C2、C3、C4……CN，每个结点包含一类细化的信息；

所述步骤1.2，对数据信息的插入，按照中序、前序或后序的遍历规则对结点进行数据信息的插入，同时调整平衡二叉树的树形结构，分为利用C++语言形式实现和利用C语言形式实现：① C++语言形式实现：采用C++语言中VECTOR类作为结点中数据存储结构，当有数据信息需要存储时，首先判断平衡二叉树是否为空；若是，则新建一个根结点并将数据信息保存到根结点同时返回保存成功；若否，则遍历平衡二叉树，判断其是否属于已存储结点；若是，则按照存储信息的规则，将需要保存的信息保存到相应结点，并返回保存成功；若否，则执行步骤1.1，再将所需保存的数据信息保存到新建结点中，最后由返回函数将保存结果返回供上层调用；

② C语言实现：利用结构体变量构建一个结构体struct，所有结点采用双向链表的存储结构，将对结点的所有操作定义为结构体的成员变量，当有数据信息需要保存时，首先判断平衡二叉树是否为空；若是，则新建一个根结点并将数据信息保存到根结点同时返回保存成功；若否，则遍历平衡二叉树，判断是否为已存储结点类；若是，则调用结构体的保存成员对象执行相应的保存操作并返回保存成功；若否，则执行步骤1.1，再将所需保存的数据信息保存到新建结点类中，最后由返回函数将保存结果返回供上层调用；

所述步骤1.3中结点数据信息的查询，通过将结点中的数据信息读取到缓冲区中，利用二分法查找，分为利用C++语言形式实现和利用C语言形式实现：① C++语言实现：当输入查询信息时，首先判断平衡二叉树是否为空；若是，则直接返回树为空；若否，则遍历平衡二叉树，判断是否为已存储结点；若是，则继续访问结点信息，并将结点信息加载到缓存.区，利用二分法进行查找，并将查询结果给返回函数供上层调用；若否，则返回无结点类给返回函数；

② C语言实现：利用结构体变量去构建一个结构体struct，所有结点采用双向链表的存储结构，将对结点的所有操作定义为结构体的成员对象；当需要查询数据信息时，首先判断平衡二叉树是否为空；若是，则直接返回树为空；若否，则遍历平衡二叉树，判断是否为已存储结点；若是，则调用结构体的查询操作成员对象执行相应的查询操作，继续访问结点类中的细化信息，直到查询到所需结果或查询完所有记录信息，并将查询结果赋给返回函数供上层调用；若否，则返回无结点类给返回函数供上层调用。

2.根据权利要求1所述的基于分类特性和平衡二叉树的数据存储、查询方法，其特征在于，结点数据以C语言或C++语言的形式存储。

3.根据权利要求1所述的基于分类特性和平衡二叉树的数据存储、查询方法，其特征还在于，平衡二叉树的删除操作分为两类，删除结点和删除结点中的数据；删除时首先保存删除的方式和需要删除的数据信息，然后调用获取删除方式的AVLTreeDeleteStyle函数，具体分以下两种情况：①当AVLTreeDeleteStyle值为删除结点Ci时，则直接遍历平衡二叉树，查询所需要删除的结点Ci，若遍历完所有结点未找到，则返回无此结点删除失败；若找到直接删除结点Ci，并返回删除成功；最后将删除结果赋给返回函数供上层调用，同时调整平衡二叉树的树形结构；

②当AVLTreeDeleteStyle值为删除结点Ci中的数据时，则首先遍历平衡二叉树，查询结点Ci，遍历完所有结点未找到则返回无此结点信息删除失败；若找到所需要删除的结点Ci，则继续查找结点中的信息，直到找到所需删除数据，将其删除并返回删除成功；或者查询完所有记录没有找到所需信息，返回无数据记录删除失败；最后将删除结果赋给返回函数供上层调用。

4.根据权利要求 3所述的基于分类特性和平衡二叉树的数据存储、查询方法，其特征在于，对平衡二叉树进行平衡化调整，分为以下四种情况： ①平衡二叉树的L型旋转，当平衡二叉树进行插入且插入结点在最小子树根结点的左孩子的左子树中，或者删除操作且删除的结点是最小子树根结点的右孩子且为叶节点时，且满足最小子树的平衡因子bf大于1时,则需要进行L型旋转来调节平衡二叉树的结构；

②平衡二叉树的R型旋转，当平衡二叉树进行插入且插入结点在最小子树根结点的右孩子的右子树中，或者删除操作且删除的结点是最小子树根结点的左孩子且为叶节点时，且满足最小子树根结点的平衡因子bf小于-1时，需要进行R型旋转来调节平衡二叉树的结构；

③平衡二叉树的LR型旋转，当平衡二叉树进行插入且插入结点在最小子树根结点的右孩子的左子树中时，同时满足最小子树根结点的平衡因子bf小于-1且其左孩子的平衡因子bf大于1时，则需要进行LR型旋转来调节平衡二叉树的结构；

④平衡二叉树的RL型旋转，当平衡二叉树进行插入且插入结点在最小子树根结点的左孩子的右子树中时，同时满足最小子树根结点的平衡因子bf大于1且其右孩子的平衡因子bf小于-1时；则需要进行RL型旋转来调节平衡二叉树的结构。

说明书

一种基于分类特性和平衡二叉树的数据存储、查询方法

技术领域

[0001] 本发明属于物联网通信领域中大数据量的存储、查询方法领域，特别是一种基于分类特性和平衡二叉树的数据存储、查询方法。

背景技术

[0002] 通信技术中，传统的数据查询方法包括静态查找方法和动态查找方法。静态查找方法包括顺序查找、二分查找、索引查找；动态查找方法包括二叉搜索树、B-树、哈希（Hash）查找法、键树等。

[0003] 顺 序 查 找 中 假 设 对 于 n 个 记 录 的 查 找 表，其 查 找 成功 时 的 平 均 查 找 长 度 为 ASL(Average Search Length),ASL=
= ，且比较次数为=n-i+1,查找到的概率为Pi= 则
ASL=nP1+(n-1)P2+……+2Pn-1+Pn = = ，则其算法时间复杂度为O(n)。

[0004] 二分查找法，对于一般情况下假设有序表的长度为n=2h-1，在每个记录的查找概率都相等的情况下，即Pi= ，可得其ASL= log2（n+1）-1,当n值大于50，其ASL可近似为log2（n+1）-1，故其算法的时间复杂度为O（log2 n）。

[0005] 索引查找法，是介于顺序查找和二分查找之间的一种方法，又可称为“分块有序”查找法，即将顺序表进行分块，按前一块的最大关键字小于后一块中的最小
关键字，内部关键字不一定有序，假设索引表的长度为b，顺序表的长度为n,则其
ASL=ASLIndex(b)+ASLSeq(n/b)≈log（2 b+1）-1+(n/b+1)/2，故其算法的时间复杂度为（O(log2 n)+ O(n)）/2。

[0006] 二叉搜索树查找法，对于有n个节点的二叉搜索树，在平衡情况下其树高为log2 n，则其每次查找的时间代价为O(log2 n),而在极端情况下如其n个节点成一条直链表形则树高为n，对于查找到每个节点的时间代价为O(n),又知其是插入节点的遍历时间代价
2
均为O(n),则其总的算法的时间复杂度最佳为O(n•log2n)，最差为O（n）。

[0007] B-树是一种平衡的多路查找树，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点，故其算法的时间复杂度为O（log2 n）。

[0008] 哈希（Hash）查找法由于自身的散列性使得其在应用于分类查找中查找效率不高。

[0009] 键树一般用于特殊查找，从根到叶子节点的一条“路径”对应为一个关键字，不适合通用的大数据量的查询。

[0010] 当前物联网通信领域中,通信数据技术的发展，越来越趋向于高实时性和巨型化。传统的静态查找方法如：顺序查找、二分查找、索引查找，很难满足当前大数据量处理对实时性的要求。而对于动态查找（DST），如二叉搜索树，B-树，哈希（Hash）查找法，键树等，其时间复杂度远远高于静态查找。

发明内容

[0011] 本发明针对以上不足，提供一种针对大量数据的速度快、能耗低、占用内存少、算法简单的基于分类特性和平衡二叉树的数据存储、查询方法。

[0012] 本发明提供一种基于分类特性和平衡二叉树（AVL树）的数据存储、查询方法，实现方法包括以下步骤：

[0013] 1.1 构建AVL树，创建结点；

[0014] 1.2 按照遍历规则，动态地将数据信息存储到相应结点；

[0015] 1.3 输入需要查询的信息，动态遍历AVL树，直到找到所需的数据信息或遍历完AVL树返回查找失败。

[0016] 所述AVL树为有序的，AVL树按照顺序（中序、前序、后序）遍历规则，动态地将数据信息存储到相应结点。

[0017] 所述结点数据储存结构按实现的语言分为C语言和C++语言。

[0018] 本发明的具体实现方法如下：

[0019] （1）新建AVL树，首先按照有AVL树的建树规则构建一个节点数为n，树高为log2 n的AVL树，然后增加结点。每一个结点代表一个特征类C1、C2、C3、C4……CN，每个结点中又包含一类细化的信息，结点中的细化信息根据实现的不同语言而使用不同的数据结构存储便于数据信息存储和查找。

[0020] （2）向AVL树中插入数据信息，对于AVL树结点采用顺序（中序、前序、后序）遍历的规则进行插入，其算法的时间复杂度为log2n，依据实现的语言可分为用C++语言实现和C语言实现：

[0021] ① C++语言实现：采用C++语言中VECTOR类作为结点中数据存储结构，当有数据信息需要存储时，首先判断AVL树是否为空；若是，则新建一个根结点并将数据信息保存到根结点同时返回保存成功；若否，则遍历AVL树，判断其是否属于已存储结点；若是，则按照存储信息的规则，将需要保存的信息保存到相应结点，并返回保存成功；若否，则执行步骤（1），再将所需保存的数据信息保存到新建结点中，最后由返回函数将保存结果返回供上层调用；

[0022] ② C语言实现：利用结构体变量构建一个结构体struct，所有结点采用双向链表的存储结构，将对结点的所有操作定义为结构体的成员变量，当有数据信息需要保存时，首先判断AVL树是否为空；若是，则新建一个根结点并将数据信息保存到根结点同时返回保存成功；若否，则遍历AVL树，判断是否为已存储结点类；若是，则调用结构体的保存成员对象执行相应的保存操作并返回保存成功；若否，则执行步骤（1），再将所需保存的数据信息保存到新建结点类中，最后由返回函数将保存结果返回供上层调用。

[0023] （3）查询AVL树的数据信息，根据有序AVL树的时间复杂度为O（log2n），于是查询结点最多需要log2n次访问内存，通过将结点中的数据信息读取到缓冲区中，利用二分法查找，其时间复杂度也是O（log2n）。依据结点的保存实现方式也可分为用C++语言实现和C语言实现：

[0024] ① C++语言实现：当输入查询信息时，调用查找函数，首先判断AVL树是否为空；若是，则直接返回树为空；若否，则遍历AVL树，判断是否为已存储结点；若是，则继续访问结点信息，并将结点信息加载到缓存区，利用二分法进行查找，并将查询结果给返回函数供上层调用；若否，则返回无结点类给返回函数；

[0025] ② C语言实现：当需要查询数据信息时，则调用结构体变量的查找变量及其对应的函数，首先判断AVL树是否为空；若是，则直接返回树为空；若否，则遍历AVL树，判断是否为已存储结点；若是，则调用结构体的查询操作成员对象执行相应的查询操作，继续访问结点类中的细化信息，直到查询到所需结果或查询完所有记录信息，并将查询结果赋给返回函数供上层调用；若否，则返回无结点类给返回函数供上层调用。

[0026] （4）删除平衡二叉树数据信息，删除时首先保存删除的方式和需要删除的数据信息，然后调用获取删除方式（AVLTreeDeleteStyle）函数，具体分以下两种情况：

[0027] ①当AVLTreeDeleteStyle值为删除结点Ci 时，则直接遍历AVL树，查询所需要删除的结点Ci，若遍历完所有结点未找到，则返回无此结点删除失败；若找到直接删除结点Ci，并返回删除成功；最后将删除结果赋给返回函数供上层调用，同时执行步骤（5），调整平衡二叉树的树形结构；

[0028] ②当AVLTreeDeleteStyle值为删除结点Ci 中的数据时，则首先遍历AVL树，查询结点Ci，遍历完所有结点未找到则返回无此结点信息删除失败；若找到所需要删除的结点Ci，则继续查找结点中的信息，直到找到所需删除数据，将其删除并返回删除成功；或者查询完所有记录没有找到所需信息，返回无数据记录删除失败；最后将删除结果赋给返回函数供上层调用。

[0029] （5）对平衡二叉树（AVL树）的插入和删除操作都会对树形结构产生影响，为了保持对树的遍历复杂度最低为log2n，需要对树进行平衡化调整，可分以下四种情况：

[0030] ①平衡二叉树的L型旋转，当AVL树进行插入（插入结点在最小子树根结点的左孩子的左子树中）或者删除操作（删除的结点是最小子树根结点的右孩子且为叶节点）时，且满足最小子树的平衡因子bf大于1时,则需要进行L型旋转来调节AVL树的结构；

[0031] ②平衡二叉树的R型旋转，当AVL树进行插入（插入结点在最小子树根结点的右孩子的右子树中）或者删除操作（删除的结点是最小子树根结点的左孩子且为叶节点）时，且满足最小子树根结点的bf小于-1时，需要进行R型旋转调整；

[0032] ③平衡二叉树的LR型旋转，当平衡二叉树进行插入（插入结点在最小子树根结点的右孩子的左子树中）时，同时满足最小子树根结点bf小于-1且其左孩子bf大于1时，则需要进行LR型旋转来调节AVL树的结构；

[0033] ④平衡二叉树的RL型旋转，当平衡二叉树进行插入（插入结点在最小子树根结点的左孩子的右子树中）时，同时满足最小子树根结点的bf大于1且其右孩子bf小于-1时；则需要进行RL型旋转来调节AVL树的结构。

[0034] （6）连续且满的AVL树的遍历，对于连续且满的结点数为n的AVL树，其共有L=log2n级结点，CL为当前级数，DCL为当前级数结点的层距差（相邻树层之间的结点值的L -1
差）；那么所有结点的遍历公式为：根结点Pr= 2 ，当前结点的父节点为PF,其左孩子PL L-CL-1
= PF- DCL,其右孩子PR = PF +DCL, DCL = 2 ,CL∈[1，L)；前序遍历公式为：Pr= 1，PL = L-CL L
PF+1, PR = PF +DCL, DCL = 2 ,CL∈[1，L)；后序遍历公式为：Pr= 2-1，PL = PF-DCL, PR = L-CL
PF-1, DCL = 2 ,CL∈[1，L)。

[0035] 本方法与现有方法的比较，具有以下有益效果：

[0036] （1）本方法算法复杂度小，实现简单，能实现快速高效存储和查询。本方法按照AVL树的构建原则构建一棵结点为n的树，则其树高为h=log2n,即当对数据进行查询时，其遍历的算法复杂度不大于 O（log2 n），同时在结点类中的信息查询采用二分法，其算法复杂度也是O（log2 n），在当前使用的查询算法中其算法复杂度最低，将动态查询的时间复杂度降低到静态查询的级别，大大提高了存储和查询的效率，达到快速查询的要求。

[0037] （2）本方法算法复杂度低，有效减少处理器的访问次数，减少能耗。本方法的算法复杂度在上一特点中已给出，相对于目前使用的其他算法，算法复杂度相对较低，在程序运行时，能有效减少处理器对于内存的访问次数，能够有效降低能耗。

[0038] （3）本方法能合理灵活的分配存储空间，节省内存空间，提高内存资源利用率。由于此方法是应用于动态存储和查找，对于资源的分配不是使用额定分配，而是基于所用描述语言的自身特性（例如C++语言中VECTOR，具有自增长特性；C语言中的双向链表，也具有动态插入特性），达到动态分配存储空间。使用C++语言是基于支持VECTOR实现的，利用VECTOR的本身具有的自增长特性，将分类到具体结点的元素按需分配存储单元；而使用C语言实现是基于构建结构体，利用结构体可以关联成员变量，将其成员变量设置为一个函数，当有数据存入时，先分类到特征类的结点处，再按照对应结点的成员变量的函数进行相应处理，并返回相应结果供上层调用，其内在的处理机制也是利用链表进行有序存储。同时其不完全使用二叉树作为存储载体，节省了用于二叉树前后指针的存储空间，从而有效节省内存资源。

[0039] （4）可支持多种语言实现，应用范围广泛。本发明方法可以基于C++/C语言实现，此两种语言是当前描述语言的主流，可以将此方法应用于大型的数据库平台，也可以应用于小型的数据终端使用，使其应用范围得到有效扩展。

附图说明

[0040] 图1是本发明实施例AVL树存储结构图；

[0041] 图2 是本发明实施例AVL树插入流程图；

[0042] 图3 是本发明实施例AVL树查找流程图；

[0043] 图4 是本发明实施例AVL树删除流程图；

[0044] 图5 是本发明实施例AVL树L型旋转示意图；

[0045] 图6是本发明实施例AVL树R型旋转示意图；

[0046] 图7是本发明实施例AVL树 LR型旋转示意图；

[0047] 图8是本发明实施例AVL树RL型旋转示意图；

[0048] 图9是本发明实施例AVL树后序存储结构图；

[0049] 图10是本发明实施例AVL树前序存储结构图。

具体实施方式

[0050] 下面结合附图和实例对本发明作进一步描述，以中序遍历为例。

[0051] 本发明是应用于物联网通信领域的大数据量的数据存储和快速查询方法。例如，对物联网中终端场所内的50000人（结点数N=50000），其中IC卡号（1字节）、姓名（10字节）、人员编号（2字节），考勤信息（2字节），协查通报信息（200字节）以及其他有关信息进行统一管理，终端RAM空间资源为8M，对于数据信息的查询可以使用刷卡和手动两种方式查询。

[0052] 针对于以上需求，用本发明来实现，采用AVL树作为结点类索引，AVL树内依次保存左指针（4字节），IC卡号（1字节），结点信息保存地址（2字节），右指针（4字节），总共需要11×50000≈530Kb。

[0053] （1）首先建一棵AVL树的根结点，参照附图1，构建一个复杂度为log2N（N为结点数）的平衡二叉树，调用创建结点（AVLTreeCreate）函数,增加AVL树的结点。每一个结点代表一个人C1、C2、C3、C4……CN，每个结点又包含一类细化信息D1、D2、 D3、 D4……D（N 包括个人资料、考勤信息等），结点中的细化信息根据实现的语言不同而使用不同的数据结构存储，便于数据信息存储和查找。

[0054] （2）然后向AVL树中存入数据信息，可参考附图2，此处对于AVL树采用中序遍历的规则向结点中插入数据信息，其算法复杂度为log2n，其存储结点以IC卡号为关键字Key区分，可分为用C++语言实现和C语言实现。

[0055] ① C++语言实现：当有人进行刷卡或者手动输入卡号时，保存卡号信息，首先判断树是否为空；若是，则执行AVLTreeCreate函数新建一个结点类；若否，则遍历AVL树，判断其是否属于已存储结点，若是，则执行插入（AVLTreeInsert）函数,读取文件中的结点数据信息并加载到缓存中，然后执行保存到文件（AVLTreeSaveToFile）函数，将数据按照存储结点的格式（如刷卡时间、上报时间以及日期等）保存到文件中相应结点信息类的VECTOR中；若否，则执行AVLTreeCreate函数，为其新建一个结点，再将所需保存的数据信息保存到新建结点类中。

[0056] ② C语言实现：基于C语言实现是利用结构体变量去构建一个结构体，将对数据信息的操作定义为一个结构体TPvector,结构体的成员变量是对数据的操作，
如（插入Insert,删除Delete，查找Search, 后翻PushBack,前翻PushFront）。当有
人进行刷卡或者手动输入卡号时，保存卡号信息，首先判断树是否为空；若是，则调用
AVLTreeCreate函数新建一个结点；若否，则遍历AVL树，判断其是否属于已存储结点，若是，则执行AVLTreeInsert函数, 读取文件中的结点数据信息并加载到缓存中，然后执行AVLTreeSaveToFile函数，将数据按照存储结点类的格式（如刷卡时间、上报时间以及日期等）保存到相应结点的文件中；若否，则执行AVLTreeCreate函数，为其新建一个结点，再将所需保存的数据信息保存到新建结点中。

[0057] （3）查询AVL树中的信息，可参照附图3，此处AVL树的查询依据中序顺序访问，时间复杂度log2 n，依据结点的保存实现方式也可分为用C++语言实现和C语言实现。

[0058] ① C++语言实现：当有人进行刷卡或者手动输入卡号时，保存卡号信息，并通过上层调用查找（AVLTreeSearch）函数，首先判断AVL树是否为空；若是，则跳转结束返回树为空，若否，则按中序遍历AVL树，将保存的卡号与平衡二叉树的访问结点关键字（key）进行比较，判断是否为已存储结点，若是，则读取文件信息并加载到缓存中，按照查询的方式（如按输入号查找，查找当前的前一条，查找当前后一条，查找需要删除的信息等）利用二分法继续查询结点中的信息，若找到所需要的查询信息，将查询结果通过返回函数返回供上层调用；若查询完所有记录没有找到所需信息，则将无数据记录赋给返回函数供上层调用；若否，则将无此结点数据赋给返回函数供上层调用。

[0059] ② C语言实现：定义一个结构体TPVector,结构体的成员变量是对数据的操作，如（插入Insert,删除Delete，查询Search, 后翻PushBack,前翻PushFront）。当有人进行刷卡或者手动输入卡号时，保存卡号信息，并调用结构体的查找成员对象TPVector.AVLTreeSearch，调用查找（AVLTreeSearch）函数，首先判断AVL树是否为空；若是，则跳转结束返回树为空；若否，则遍历AVL树，判断其是否为已存储结点，若是，则读取文件信息并加载到缓存中，按照查询的方式（如按输入号查找，PushFront，PushBack，Delete等）利用二分法继续查询结点中的信息，若找到所需要的信息，将查询结果通过返回函数返回供上层调用；若查询完所有记录没有找到所需信息，则将无数据记录赋给返回函数供上层调用；
若否，则将无此结点数据赋给返回函数供上层调用。

[0060] （4）删除AVL树中的信息，可参照附图4，删除时首先保存删除的方式（AVLTreeDeleteStyle）和需要删除的数据信息，然后判断AVL树是否为空；若是，则直接跳转结束返回树为空，若否则遍历AVL树，具体分以下两种情况：

[0061] ①当AVLTreeDeleteStyle值为删除结点时，则直接遍历AVL树，找到所需要删除的结点，直接删除整个结点，并将删除结果赋给返回函数供上层调用，同时调用平衡化函数调整AVL树的树形结构。

[0062] ②当AVLTreeDeleteStyle值为删除结点中数据时，则首先遍历AVL树，判断其是否为以存储结点；若否，则跳转结束返回无数据记录；若是，则调用LoadAVLTreeNode函数继续查找结点中的信息，若找到，则删除查找到的信息，并将删除结果赋给返回函数供上层调用；若查询完所有记录没有找到所需信息，则将无此记录结果赋给返回函数供上层调用。

[0063] （5）调整AVL树。AVL树的插入和删除操作都会对树形结构产生影响，导致平衡因子bf（balance factor）大于1或小于-1，为了保持对树的时间复杂度最低为log2n，需要对树进行平衡化调整，对树形的调整可分以下四种情况：

[0064] ①平衡二叉树的L型旋转，当AVL树进行插入（插入结点在最小子树根结点的左孩子的左子树中）或者删除操作（删除的结点是最小子树根结点的右孩子且为叶节点）时，且满足最小子树的bf大于1时,则需要进行L型旋转来调节AVL树的结构。

[0065] 参照图5,当插入CN 时，导致最小子树的根结点A的bf变为2，则需要进行L旋转调整，首先将BR提升为新子树的根结点，A下降为BR的右孩子，同时将BL旋转为BR的左孩子,B下降为BL 的右孩子；当删除结点AR 时，导致最小子树的根结点A的bf变为2，则需要进行L旋转调整，将BR 提升为最小子树根结点，A旋转为BR 的右孩子，B旋转为BR 的左孩子。

[0066] ②平衡二叉树的R型旋转，当AVL树进行插入（插入结点在最小子树根结点的右孩子的右子树中）或者删除操作（删除的结点是最小子树根结点的左孩子且为叶节点）时，且满足最小子树根结点的bf小于-1时，需要进行R型旋转调整。

[0067] 参照图6, 当插入CN 时，导致最小子树的根结点A的 bf变为-2，则需要进行R旋转调整；首先提升B为最小子树的根结点，A下降为B的左孩子，将 BL旋转为A的右孩子；当删除AL时，导致最小子树的根结点A的bf变为-2，则需要进行R旋转，首先提升B为最
小子树的根结点，BL 旋转为B的左孩子，A旋转为BL的左孩子。

[0068] ③平衡二叉树的LR型旋转，当平衡二叉树进行插入（插入结点在最小子树根结点的右孩子的左子树中）时，同时满足最小子树根结点bf小于-1且其左孩子bf大于1时，则需要进行LR型旋转来调节AVL树的结构。

[0069] 参照图7，当插入CN 时导致最小子树的根结点A的bf变为-2且其左孩子B的bf变为2，则需要进行LR旋转调整，首先进行L旋转，将CL 提升为右子树的根结点，CR 旋转为CL 的右孩子，C旋转为CR 的左孩子，B旋转为CR 的右孩子；此时进行R旋转，提升C为最小子树的根结点，A为C的左孩子且CL 旋转为A的右孩子，B旋转为C的右孩子，CR 旋转为B
的左孩子。

[0070] ④平衡二叉树的RL型旋转，当平衡二叉树进行插入（插入结点在最小子树根结点的左孩子的右子树中）时，同时满足最小子树根结点的bf大于1且其右孩子bf小于-1时；则需要进行LR型旋转来调节AVL树的结构。

[0071] 参照图8，当插入CN 时导致最小子树的根结点A的bf变为2且其左孩子B的bf变为-2，则需要进行RL旋转调整，首先进行R旋转，将C提升为左子树的根结点，B下降为C的左孩子，将CL旋转为B的右孩子；此时进行L旋转，将C提升为最小子树的根结点，A下降为C的右孩子，将CR 旋转为A的左孩子。

[0072] （6）实际情况下AVL树的遍历，对于连续且满的结点数为50000的AVL树，其共有L= log2 50000< log2 65536=16级结点，CL为当前级数，DCL为当前级数结点的层距差；那么L -1所有结点的遍历公式为：根结点Pr= 2 ，当前结点的父节点为PF,其左孩子PL = PF- DCL,L-CL-1
其右孩子PR = PF +DCL, DCL = 2 ,CL∈[1，L)。

[0073] 当需要寻找结点序号为20000时，即n=20000,则由214<20000<215 =32768可知，14 14
目标结点在根结点的左子树中，第一次查找PL =32768-2 =16384，PR = 32768+2 =49152；
13 13
显然目标结点在其左子树中，第二次查找PL =16384-2 =8192，PR = 16384+2 =24576；显然
12 12
目标结点在其右子树中，第三次查找PL = 24576-2 =20480，PR =24576+2 =28672；则执行第
11 11 10
四次查找PL =20480-2 =18332，PR = 20480+2 =22528；执行第五次，PL =18332-2 =17284，
10 9 9
PR = 18332+2 =19880；执行第六次，PL =19880-2=19368，PR = 19880+2=20392；执行第
8 8 7
七次，PL =20392-2=20136，PR = 20392+2=20648；执行第八次，PL =20136-2=20008，PR
7 6 6
= 20136+2=20264；执行第九次，PL =20008-2=19944，PR = 20008+2=20072；执行第十
5 5 4
次，PL =19944-2=19912，PR = 19944+2=19976；执行第十一次，PL =19976-2=19960，PR =
4 3 3
19976+2=19992；执行第十二次，PL =19992-2=19984，PR = 19992+2=20000；此时查找到所需要的目标结点。

[0074] 本发明公布了一种基于分类特性和平衡二叉树的数据存储、查询方法，上述实例给出了基于中序遍历的整个方法过程，下面给出基于前序和后序遍历的方法分别如图9和图10。

[0075] 图9公布的是基于前序遍历AVL树的存储结构图，与中序遍历存储结构差异在于，当对数据信息进行存储和查询时是按照根左右的顺序来遍历的，那么所有结点的遍历公式为：根结点Pr=1，当前结点的父节点为PF,其左孩子PL = PF+1,其右孩子PR = PF +DCL, DCL L-CL= 2 ,CL∈[1，L)。

[0076] 图10公布的是基于后序遍历AVL树的存储结构图，其按照左右根的遍历顺序存储L和查询AVL树，与前序和中序不同在于其结点的遍历公式为：根结点Pr= 2-1，当前结点的L-CL
父节点为PF,其左孩子PL = PF -DCL,其右孩子PR = PF -1, DCL = 2 ,CL∈[1，L)。

[0077] 上述实例中，内存资源为8M的情况下，要求结点数N为50000，那么应用AVL树其建立二叉树的高度H为log2 50000< log2 65536=16，即树高h=16,那么查找树的时间复杂度也是16，那么查找到任何一个结点最多需要访问16次内存。对于50000个结点10000000条数据记录，平均每个结点为200条，再对这200条记录信息实行二分法查找，算法复杂度也是O(log2 200)﹤8，也就是最多8次可以确定所要查找的数据。

[0078] 此方法利用有序AVL树结构将数据信息按分类特性来存储和查询，使得其存储结点类的AVL树的时间复杂度为O(log2N)，同时查找具体信息采用将数据加载到缓存区利用二分法来完成，其时间复杂度也为O(log2N)，较当前常用查询方法其算法复杂度最小，大大提高了查询效率，节省查询时间，减少了内存访问次数，降低了能耗。同时利用二叉树索引的存储方式，节省了存储二叉树前后指针的内存空间（8b×N,N结点数），实现动态的插入，灵活的分配了资源空间，提高了内存利用率。