| 摘要 |
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 O i M/2-1, for storing internal nodes of the binary tree along respective paths from ancestors of the leaves to root. Location j of register reg[i] is arranged to store internal node k, preferably where k=(i div 2j)+2m-j-l). Any internal node of the binary tree is stored tagged, if the right and/or left subtree thereof contain(s) at least one element of subset N. The digital memory structure also has an array of pointers internal[l], 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 ontemal node 1. |
