基于二叉树的反向Hash链遍历  

Reverse Hash Chain Traversal Based on Binary Tree

作　　者：傅建庆[1] 吴春明[1] 吴吉义[1,2] 平玲娣[1] 

机构地区：[1]浙江大学计算机科学与技术学院,杭州310027 [2]杭州师范大学电子商务与信息安全重点实验室,杭州310036

出　　处：《计算机研究与发展》2012年第2期294-303,共10页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金重大项目(2008AA01A323;2009AA01A334;2008AA01A326;2008AA01A325;2008AA01Z214);国家自然科学基金项目(60773182;61070157);国家科技支撑计划基金项目(2008BA21B03);浙江省科技计划基金项目(2007C11088;2008C210077)

摘　　要：提出了一种反向Hash链遍历的时间、空间复杂度优化算法.采用堆栈操作实现了高效的反向Hash链遍历,并将Hash链遍历过程映射到了二叉树的后序遍历过程,利用二叉树性质对存储和计算性能进行了理论化分析和证明.分析证明结果表明,遍历对长为n的反向Hash链时,算法只需要存储[lbn]+1个节点值,并且进行不多于[(lbn-/2+1)n次Hash计算次数.相比同类其他算法,该算法并不要求链长为2的整数次方.通过对算法进行基于k叉树(k≥3)的扩展,进一步将存储空间降低到[lo gk[(k-1)n+1],但总计算次数提高到[(-logk[(k-1)n+1]-1)k/2+1]n;通过在算法执行前先把Hash链平分为p段(p≥2),将总计算次数降低到[(lb(n/p)-/2+1)n,但是所需的存储空间提高到[(lb(n/p)+1)p.An algorithm improving the time and space complexity of reverse Hash chain traversal is proposed. By mapping the traversal of a reverse Hash chain to the postorder traversal of a binary tree, the proposed algorithm reduces the product of the total times of Hash operations and the storage space required to O（n（1b n）2）, where n is the length of the reverse Hash chain. Analysis and proof using the property of the binary tree show that the proposed algorithm requires to save only lib n] if-1 nodes at the same time, and needs no more than （[1b nj [2q-1）n times of Hash operations totally. Compared with other algorithms, the proposed one can be applied to Hash chains with any length, eliminating the limitation that the length of chain must be of 2 integer-th power. Then an advanced algorithm is proposed by mapping the traversal of a reverse Hash chain to the postorder traversal of a k-ary tree, where k is an integer no less than 3, and the space required is reduced to [logk[（k--1）nq-1]], but the times of Hash opera advanced algorithm tions required is raised to [-（ [logk[（k--1）n＋ 1]] --1）k/2 q-1In. Finally, another is proposed by splittin integer no less than 2. The times of Hash g Hash chain to p part before traversing, where p is an operations required is reduced to （[1b（n/p） ]/2 if- 1）n, but the space required is raised to （[1b（n/p） j q- 1）p.

关 键 词：反向Hash链 二叉树 K叉树 后序遍历 堆栈 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]