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 「log\-k［(k-1)n+1］, but the times of Hash operations required is raised to ［(「log\-k［(k-1)n+1］-1)k/2+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(n/p)/2+1)n, but the space required is raised to (「lb(n/p)+1)p.