A Van Emde Boas tree (or Van Emde Boas priority queue), also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O(log m) time. Notice that m is the size of the keys — therefore O(log m) is O(log log n) in a tree where every key below n is set, exponentially better than a full self-balancing binary search tree. They also have good space efficiency when they contain a large number of elements, as discussed below. They were invented by a team led by Peter van Emde Boas in 1975.
Read more about Van Emde Boas Tree: Supported Operations, How It Works
Famous quotes containing the words van and/or tree:
“Unlike Descartes, we own and use our beliefs of the moment, even in the midst of philosophizing, until by what is vaguely called scientific method we change them here and there for the better. Within our own total evolving doctrine, we can judge truth as earnestly and absolutely as can be, subject to correction, but that goes without saying.”
—Willard Van Orman Quine (b. 1908)
“Behold I have given you every herb bearing seed which is upon the face of all the earth, and every tree, in which is the fruit of a tree yielding seed; to you it shall be for meat.”
—Bible: Hebrew Genesis 1:29.
But in a later context, God told the disgraced Adam, “and thou shalt eat the herb of the field” (Genesis 3:18)