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

提出了一种反向Hash链遍历的时间、空间复杂度优化算法.采用堆栈操作实现了高效的反向Hash链遍历,并将Hash链遍历过程映射到了二叉树的后序遍历过程,利用二叉树性质对存储和计算性能进行了理论化分析和证明.分析证明结果表明,遍历对长为n的反向Hash链时,算法只需要存储「lb n+1个节点值,并且进行不多于(「lb n/2 + 1)n次Hash计算次数.相比同类其他算法,该算法并不要求链长为2的整数次方.通过对算法进行基于k叉树(k≥3)的扩展,进一步将存储空间降低到「log-k［(k-1)n+1］,但总计算次数提高到［(「log-k［(k-1)n+1］-1)k/2+1］n;通过在算法执行前先把Hash链平分为p段(p≥2),将总计算次数降低到(「lb(n/p)/2 + 1)n,但是所需的存储空间提高到(「lb(n/p)+1)p.

Reverse Hash Chain Traversal Based on Binary Tree

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(lb 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 - lb n - +1 nodes at the same time, and needs no more than ( - lb n -2+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)n+1] - , but the times of Hash operations required is raised to [(- logk[(k-1)n+1] - -1)k2+1]n. Finally, another advanced algorithm is proposed by splitting Hash chain to p part before traversing, where p is an integer no less than 2. The times of Hash operations required is reduced to(-lb(np) -2+1)n, but the space required is raised to (- lb(np) - +1)p.