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:
“I philosophize from the vantage point only of our own
provincial conceptual scheme and scientific epoch, true; but I know no better.”
—Willard Van Orman Quine (b. 1908)
“Even when seen from near, the olive shows
A hue of far away. Perhaps for this
The dove brought olive back, a tree which grows
Unearthly pale, which ever dims and dries,
And whose great thirst, exceeding all excess,
Teaches the South it is not paradise.”
—Richard Wilbur (b. 1921)