| 摘要 |
<p>A digital memory structure manages a subset N of a universe U = {0...M-1} of elements e, where the universe U is represented by a complete binary tree of height m+1 with elements e of the universe U at its leaves. The digital memory structure has an array of overlapped registers reg[i], preferably where 0 ≤ i ≤M/2-1, for storing internal nodes of the binary tree along respective paths from ancestors of said leaves to root. Location j of register reg[i] is arranged to store internal node k, preferably where k = i div 2?j)+ 2m-j-1¿). Any internal node of the binary tree is stored as tagged, if the right and/or the left subtree thereof contain(s) at least one element of subset N. The digital memory structure also has an array of pointers internal[1], preferably where 1 ≤1 ≤M-1), to the smallest element in the right subtree, and/or the largest element in the left subtree, of each respective internal node 1.</p> |
