How It Works
For the sake of simplicity, let log2 m = k for some integer k. Define M=2m. A vEB tree T over the universe {0,...,M-1} has a root node that stores an array T.children of length M1/2. T.children is a pointer to a vEB tree that is responsible for the values {iM1/2,...,(i+1)M1/2-1}. Additionally, T stores two values T.min and T.max as well as an auxiliary vEB tree T.aux.
Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in T.min and largest value is stored in T.max. These two values are not stored anywhere else in the vEB tree. If T is empty then we use the convention that T.max=-1 and T.min=M. Any other value x is stored in the subtree T.children where . The auxiliary tree T.aux keeps track of which children are non-empty, so T.aux contains the value j if and only if T.children is non-empty.
Read more about this topic: Van Emde Boas Tree
Famous quotes containing the word works:
“The slightest living thing answers a deeper need than all the works of man because it is transitory. It has an evanescence of life, or growth, or change: it passes, as we do, from one stage to the another, from darkness to darkness, into a distance where we, too, vanish out of sight. A work of art is static; and its value and its weakness lie in being so: but the tuft of grass and the clouds above it belong to our own travelling brotherhood.”
—Freya Stark (b. 1893–1993)