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:
“If there is a case for mental events and mental states, it must be that the positing of them, like the positing of molecules, has some indirect systematic efficacy in the development of theory.”
—Willard Van Orman Quine (b. 1908)
“The Anglo-American can indeed cut down, and grub up all this waving forest, and make a stump speech, and vote for Buchanan on its ruins, but he cannot converse with the spirit of the tree he fells, he cannot read the poetry and mythology which retire as he advances. He ignorantly erases mythological tablets in order to print his handbills and town-meeting warrants on them.”
—Henry David Thoreau (1817–1862)