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:
“The first day that we landed upon that fatal shore
The planters they came round us full twenty score or more,
They rank’d us up like horses, and sold us out of hand
Then yok’d us unto ploughs, my boys, to plow Van
Dieman’s Land.”
—Unknown. Van Dieman’s Land (l. 9–12)
“I saw the spiders marching through the air,
Swimming from tree to tree that mildewed day
In latter August when the hay
Came creaking to the barn.”
—Robert Lowell (1917–1977)