基于二叉树的反向哈希链遍历

摘要：

本文提出了一种反向哈希链遍历的时间、空间复杂度优化算法。算法利用堆栈操作实现了高效的遍历,并把反向哈希链映射到二叉树,利用二叉树的性质对存储和计算性能进行了理论化证明。对于长为n的反向哈希链,算法只需要存储”log2n”+1个节点值,并且全部遍历需要的哈希计算次数不大于n”log2n”/2。相比同类其它算法,本算法的主要优点是适用于链长为任意值的情况,而不要求链长一定为2的整数次方。

关键词： 反向哈希链 二叉树 中序遍历 堆栈

作者: 傅建庆 吴吉义 范容 陈健 平玲娣

作者单位: 浙江大学 计算机科学与技术学院,浙江 杭州 310027 浙江大学 计算机科学与技术学院,浙江 杭州 310027 杭州师范大学 计算机科学与技术学院,浙江 杭州 310036

会议类型: 国内会议

会议名称: 第十七届全国网络与数据通信学术会议(NDCC2010)

会议地点: 秦皇岛

会议语种:中文

页码: 272-277

在线出版日期: 2010-09-16（万方平台首次上网日期，不代表论文的发表时间）