二叉检索树构造

第１２卷第１期　２０１３年３月　南通大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｎａｎｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏｌ＿１２　Ｎｏ．１　Ｍａｒ．２０１３　由先序序列和结点的左孩子情况构造　严格二叉树的高效算法　唐自立　（苏州大学计算机科学与技术学院，江苏苏州　２１５００６）　摘要：提出一种新的由一棵严格二叉树的先序序列和结点的左孩子情况构造该严格二叉树的非递归算法．通过实　例给出了新算法的执行过程，同时说明，与已有的等价递归算法相比，新算法的时间复杂性更低，而最差情　况空间复杂性相同．　关键词：先序序列；结点；左孩子；非递归算法；严格二叉树构造　中图分类号：ＴＰ３１１．１２，ＴＰ３０１．６　文献标志码：Ａ　文章编号：１６７３—２３４０（２０１３）Ｏ１—０００９—０５　Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｃｏｎｓｔｒｕｃｔｉｎｇ　ａ　Ｓｔｒｉｃｔｌｙ　Ｂｉｎａｒｙ　Ｔｒｅｅ　ｆｒｏｍ　Ｐｒｅｏｒｄｅｒ　Ｔｒａｖｅｒｓａｌ　ａｎｄ　Ｌｅｆｔ　Ｃｈｉｌｄ　ｏｆ　Ｅａｃｈ　Ｎｏｄｅ　ＴＡＮＧ　Ｚｉ－ｌｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｕｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｕｚｈｏｕ　２１５００６，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ　ｎｏｎ－ｒｅｃｕｒｓｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｆｏｒ　ｃｏｎｓｔｒｕｃｔｉｎｇ　ａ　ｓｔｒｉｃｔｌｙ　ｂｉｎａｒｙ　ｔｒｅｅ　ｆｒｏｍ　ｉｔｓ　ｐｒｅｏｒｄｅｒ　ｔｒａｖｅｒｓａｌ　ａｎｄ　ｔｈｅ　ｌｅｆｔ　ｃｈｉｌｄ　ｏｆ　ｅａｃｈ　ｎｏｄｅ．Ｔｈｅ　ｅｘｅｃｕｔｉｏｎ　ｏｆ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｉｌｌｕｓｔｒａｔｅｄ　ｂｙ　ａｎ　ｅｘａｍｐｌｅ．Ｌｅｔ　ｎ　ｂｅ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｎｏｄｅｓ　ｏｆ　ａ　ｓｔｒｉｃｔｌｙ　ｂｉｎａｒｙ　ｔｒｅｅ．Ｔｈｅ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　Ｏ（ｎ），ａｎｄ　ｉｔ　ｉｓ　ｌｏｗｅｒ　ｔｈａｎ　ｔｈａｔ　ｏｆ　ｔｈｅ　ｅｑｕｉｖａｌｅｎｔ　ｒｅｃｕｒｓｉｖｅ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｗｏｒｓｔ　ｃａｓｅ　ｓｐａｃｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　Ｏ（　），ａｎｄ　ｉｔ　ｉｓ　ｔｈｅ　ｓａｍｅ　ａｓ　ｔｈａｔ　ｏｆ　ｔｈｅ　ｅｑｕｉｖａｌｅｎｔ　ｒｅｃｕｒｓｉｖｅ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｐｒｅｏｒｄｅｒ　ｔｒａｖｅｒｓａｌ；ｅａｃｈ　ｎｏｄｅ；ｌｅｆｔ　ｃｈｉｌｄ；ｎｏｎ—ｒｅｃｕｒｓｉｖｅ　ａｌｇｏｒｉｔｈｍ；ｓｔｒｉｃｔｌｙ　ｂｉｎａｒｙ　ｔｒｅｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　

数据结构与算法上机作业

第五章 查找

一、选择题

1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。

A. n/2 B. n C. (n+1)/2 D. n+1

2、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ：

A. (100, 80, 90, 60, 120, 110, 130) B. (100, 120, 110, 130, 80, 60, 90)

C. (100, 60, 80, 90, 120, 110, 130) D. (100, 80, 60, 90, 120, 130, 110)

3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。

A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 5

42513

4、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。

A. LL B. LR C. RL

D. RR

5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。

A. 2k-1-1 B. 2k-1+1 C. 2k-1 D. 2k+1

6、具有5层结点的平衡二叉树至少有 A 个结点。

A. 12 B. 11

C. 10 D. 9

7、下面关于B-和B+树的叙述中，不正确的是 C 。

A. B-树和B+树都是平衡的多叉树

B. B-树和B+树都可用于文件的索引结构

C. B-树和B+树都能有效地支持顺序检索 D. B-树和B+树都能有效地支持随机检索

8、下列关于m阶B-树的说法错误的是 D 。

第１９卷　第３期　

２０１０年５月　重庆电子工程职业学院学报　

ｏｕｍａｌ　ｏｆ　Ｃｈｏｎｇｑｉｎｇ　Ｃｏｎｅｇｅ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｆｉｎｇ　ＶＯＩ．１９　Ｎｏ．３　

Ｍａｙ　２０１０　

二叉排序树在动态检索中的应用研究　

顾卫杰，钱月霞　

（常州机电职业技术学院，江苏常州２１３１６４）　

摘要：在信息系统广泛应用的今天，数据查询的效率越来越受人们关注，以往的顺序查找法查询效率低，　很难满足大数据量的查询，本文提出一种基于二叉排序树的动态检索方法，并结合实例，阐述了二叉排序树的　构造、平衡、查询等操作，大大提高了检索效率。　关键词：二叉排序树；动态检索；平衡　中图分类号：ＴＰ３９　文献标识码：Ａ　文章编号：１６７４—５７８７（２０１０）０３—０１４９—０３　

随着计算机技术的发展．电子商务成为新的商业媒　

介，各类信息系统应运而生．数据检索成为信息系统中最　

频繁典型的操作．如何提高查询效率成了各类信息系统　急待解决的问题　目前大多数信息系统对数据库表的查　

询操作采用的是顺序查找法．即用所给关键字与数据库　

表中记录按顺序逐个比较．直到查找到满足条件的记录．　时间复杂度为０（ｎ）Ⅲ，这种方法最容易实现，但当数据量　

很大时，查询效率很低。二分法查找是另一种查找方法，　

它要求线性表中的结点按关键字值升序或降序排列。查　

找时不必逐个顺序比较．直接与中间位置的关键字比较．　

若相同，则查找成功，若给定值大于该关键字的值，则在　

后半部分进行折半查找．否则在前半部进行折半查找．二　

分查找效率较高，时间复杂度为Ｏ（１ｏｇ　ｎ），但对数据的存　

储格式有要求。必须是顺序存储。本文提出了一种基于二　

叉排序树的动态检索方法．并以超市管理系统为例，给出　

二叉排序树的应用过程。该方法查找效率类似于二分法。　

对于数据需要频繁增加、删除时。可以很方便的实现。　

１　二叉排序树的构造　

１．１二叉排序树的特点　

二叉排序树（Ｂｉｎａｒｙ　Ｓｅａｒｃｈ　ｒｒｅｅ）。是具有下列性质的　

平衡二叉树

构造方法

平衡二叉树

对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。

平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1

一棵好的平衡二叉树的特征：

（1）保证有n个结点的树的高度为O(logn)

（2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1)

一、平衡二叉树的构造

在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树

1.调整方法

（1）插入点位置必须满足二叉查找树的性质 ，即任意一棵子树的左结点都小于根结点，右结点大于根结点

（2）找出插入结点后不平衡的最小二叉树 进行调整，如果是整个树不平衡，才进行整个树的调整。

2.调整方式

（1）LL型

LL型：插入位置为左子树的左结点，进行向右旋转

由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。

（2）RR型

RR型：插入位置为右子树的右孩子，进行向左旋转

由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。