二分查判定树的RHC构造法
徐有为;张宏军;程恺;陈裕田;周彬彬
【摘 要】传统面向过程的二分查判定树构造方法复杂且工作量大.通过分析二分查判定树的特点,提出倾斜二叉树的定义和构造方法,并进行了相关性质的探究.利用逆向哈弗曼编码(Reversed Huffman Coding,RHC)和二分查判定树的中序有序性,提出了一种面向计算的二分查判定树构造法——RHC构造法.结合性能分析、对比,RHC构造法比传统面向过程的方法速度更快、效率更高.
【期刊名称】《微型机与应用》
【年(卷),期】2018(037)009
【总页数】5页(P52-56)
【关键词】二分查;判定树;倾斜二叉树;逆向哈夫曼编码
【作 者】徐有为;张宏军;程恺;陈裕田;周彬彬
【作者单位】陆军工程大学 指挥控制工程学院,江苏 南京210000;陆军工程大学 指挥控制工程学院,江苏 南京210000;陆军工程大学 指挥控制工程学院,江苏 南京210000;陆军工程大学 指挥控制工程学院,江苏 南京210000;陆军工程大学 指挥控制工程学院,江苏 南京210000
【正文语种】中 文
【中图分类】TP311
0 引言
二分查又称为折半查[1]，是实现有序表查的一个非常高效的算法。在对二分查进行时间复杂性分析和评价时，应用判定树这一工具可以使分析更加科学、形象、直观。然而在结点总数发生变化的情况下，判定树树形也会相应地发生改变。通过分析二分查算法，本文旨在解决以下两个问题：对于不同结点总数的判定树树形，其结构特点是否具有一般性的规律？针对这一规律，将如何构造判定树，是否存在一个快速并且通用的构造方法？
1 二分查判定树
二分查是“基于计算中值地址的”，其原理[2]是：将数组中间位置记录的数据与待查数据K比较，若两者相等，则查成功，否则利用中间位置元素将数组分成前后两个子数组，如果中间位置数据大于待查数据，则进一步查前一子数组，否则进一步查后一子数组，重复以上过程，直到到带查数据或者查区间长度为0(即查不成功)为止。
二分查由于其高效的平均运算性能，已经广泛应用于计算机科学、通信工程、电子科学等多个学科，其在中文信息处理、中文分词方法[3]、路由查算法[4]等多个领域的应用均大大降低了传统算法的时间复杂度,取得了满意的结果。二分查的折半思想也为多目标线性规划寻近似解[5]、支持向量机分类[6]、最长前缀匹配算法[7]提供了非常高效的解决思路。
以判断选择为主要操作的算法，其流程可以表示成一棵树，称为算法的判定树。判定树由钟鸣等人[8]首次使用，并逐渐广泛应用于算法效率分析中。二分查判定树是判定树的一种典型应用：把当前查区间中间位置的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为二分查判定树(Decision Tree)或比较树(Comparison Tree)[9-10]。二分查判定树是对有序表数据结构很直观形象的表达，便于访问查。
结点数为13的二分查判定树如图1所示。
图1 二分查判定树示意图
判定树传统的构造方法是依照二分查算法的流程，逐步构造的，需要依次确定根结点位置的元素、缩小范围递归地对左子表进行操作并确定根、缩小范围递归地对右子表进行操作并确定根。图中的每一个结点都代表了一次查。显然这种面向过程的方法非常复杂，会对有序表的每一个元素都进行比较，尤其当结点数增多时，就显得“耗时耗力”。
李金霞[1]等人提出了一种改进的二分查判定树构造方法，但是该方法的本质也是一种面向过程的构造方式，同样存在着复杂性的问题。
本文提出的RHC构造方法是面向计算的，有效避免了面向过程构造方法的复杂性，做到迅速准确。为了更好地说明RHC构造法，首先给出倾斜二叉树的定义。
2 倾斜二叉树
2.1 相关定义
定义1(平衡因子)：对于二叉树的结点v，其右子树的所有结点个数NR与左子树的所有结点个数NL之差(NR-NL)称为v的平衡因子。
定义2(倾斜二叉树)：具有n(n≥1)个结点的二叉树，如果满足，对任意结点v，v的平衡因子等于0或者1，即右子树的结点个数或者比其左子树的结点个数多1，或者与其左子树的结点个数相等，那么称这样的二叉树为倾斜二叉树。
根据定义，对图2所示树形进行判断，显然图(a)是一棵倾斜二叉树，因为所有的结点都满足平衡因子等于0或者1，图(b)不是一棵倾斜二叉树，尽管结点b、c、d、e的平衡因子均等于0，但是a结点的平衡因子等于2，不符合倾斜二叉树的要求。
图2 倾斜二叉树示意图
2.2 构造——开关法
下面给出倾斜二叉树的一种构造方式，结合了面向过程的思想，称为开关法(Switch Method)。假设初态时树为空(即树有0个结点)，一共有n个小球，按顺序依次完成进树的过程。每个小球进树到不能进为止(即碰到空结点时停止进树)，并在该空结点处填补形成新的
结点，比如第一个小球进树填补后成为根结点，以此类推；每个小球变成结点的同时就在对应的结点位置生成出一个开关，开关一共有左右两个状态，用来判定当后续球经过时应该向左走还是向右走，新生成的开关初始状态为右；每有一个小球经过一个开关，该开关的状态发生一次改变。具体构造过程如图3所示。
图3 倾斜二叉树的构造示意图
如图3(a)所示，第一个小球进树，变成根结点，生成开关，初始状态向右。图3(b)中，第二个小球进树，遇到第一个开关向右，相应的开关状态变为向左。小球不能再进，变成新的结点，成为根结点的右儿子，生成新的开关，初始状态向右。图3(c)中，第三个小球进树，遇到第一个开关向左，相应的开关状态变为向右，小球不能再进，形成新的结点，成为根结点的左儿子，生成新的开关，初始状态向右。图3(d)中，第四个小球进树，遇到第一个开关向右，相应的开关状态变为向左，遇到第二个开关向右，相应的开关状态变为向左，小球不能再进，形成新的结点和开关，开关初始状态向右。
当所有的小球都完成进树时，就构造出了一棵结点数为n的倾斜二叉树。因为针对单个结点v，凡是经过结点v的小球，都是按照右、左、右、左的顺序进入其子树的，所以对于每个结
点v，其平衡因子或者等于1，或者等于0，符合倾斜二叉树的定义。
2.3 性质探究
由倾斜二叉树的定义和构造法，很容易给出以下性质：
性质1：结点数为n的倾斜二叉树树形唯一。
证明采用第二数学归纳法，对n进行归纳。
当n=1或n=2时，结论显然成立，其树形如图3(a)和图3(b)。
假设结论对n≤k均成立，那么当n=k+1时，对n进行奇偶讨论分析。
若n为偶数，令n=2p，由倾斜二叉树的定义可得：根结点的左子树有p-1个结点，右子树有p个结点。因为p-1和p均小于等于k，由归纳假设知，它们的树形是唯一的，所以这种假设下，结点总数为n的树形也是唯一的。
若n为奇数，令n=2p+1，由倾斜二叉树的定义可得：根结点的左、右子树均有p个结点，同理可得此时结点总数为n的树形是唯一的。
故结论对任意的n都成立，证明完毕。
性质1建立了倾斜二叉树与二分查判定树之间的一一对应关系，确保了两者构造的等价性，是进行后续性质推导的前提。
性质2：倾斜二叉树的左子树、右子树也为倾斜二叉树。
性质3：对于结点数为n的倾斜二叉树，树高为k，其中:k=log2(n+1)， 为上取整函数。
证明：采用第二数学归纳法,对n进行归纳，
当n=1或n=2时，结论显然成立。
假设结论对n≤k均成立，那么当n=k+1时，对n进行奇偶讨论分析。
若n为偶数，令n=2p，由倾斜二叉树的定义可得：根结点的左子树有个结点，右子树有p个结点，因为p-1和p均小于等于k，由归纳假设知，左子树树高为k1=log2(p)，右子树树高为k2=log2(p+1)，所以整个树高为log2(p+1)+1，只需证log2(p+1)+1=log2(2p+1)，而k2-1<log2(p+1)≤k2，所以2k2-1<2p+1≤2k2+1-1，因为2p+1一定为奇数，所以下界可以修正为2
k2+1≤2p+1≤2k2+1-1，故log2(2p+1)=k2+1=log2(p+1)+1；同理可证n为奇数的情况，故结论对任意的n均成立，证毕。
性质4：若n是形如2m-1(m为正整数)的整数，那么结点总数为n的倾斜二叉树是满二叉树。
二叉树的基本性质

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。