Van Emde Boas Tree

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:

    “There is no blue without yellow and without orange.”
    —Vincent Van Gogh (1853–1890)

    “A tree that can fill the span of a man’s arms
    Grows from a downy tip;
    A terrace nine stories high
    Rises from hodfuls of earth;
    A journey of a thousand miles
    Starts from beneath one’s feet.”
    —Lao-Tzu (6th century B.C.)