“Van Emde Boas tree”的意思、由来-开放百科全书

词条

Van Emde Boas tree

释义

Supported operations
How it works
FindNext Insert Delete Discussion
See also
References
Further reading

Van Emde Boas tree
Type	Non-binary tree
Invented	1975
Invented by	Peter van Emde Boas
Asymptotic complexity in big O notation
Space	O(M)}}
Search	O(log log M)}}
Insert	O(log log M)}}
Delete	O(log log M)}}

A Van Emde Boas tree ({{IPA-nl|vɑn 'ɛmdə 'boːɑs}}), also known as a vEB tree or Van Emde Boas priority queue, is a tree data structure which implements an associative array with {{math|m}}-bit integer keys. It performs all operations in {{math|O(log m)}} time, or equivalently in {{math|O(log log M)}} time, where {{math|M {{=}} 2^m}} is the maximum number of elements that can be stored in the tree. The {{math|M}} is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree data-structures is often measured. The vEB tree has good space efficiency when it contains a large number of elements, as discussed below. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.^[1]

Supported operations

A vEB supports the operations of an ordered associative array, which includes the usual associative array operations along with two more order operations, FindNext and FindPrevious:^[2]

Insert: insert a key/value pair with an {{math|m}}-bit key
Delete: remove the key/value pair with a given key
Lookup: find the value associated with a given key
FindNext: find the key/value pair with the smallest key which is greater than a given {{math|k}}
FindPrevious: find the key/value pair with the largest key which is smaller than a given {{math|k}}

A vEB tree also supports the operations Minimum and Maximum, which return the minimum and maximum element stored in the tree respectively.^[3] These both run in {{math|O(1)}} time, since the minimum and maximum element are stored as attributes in each tree.

How it works

Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in {{mono|T.min}} and largest value is stored in {{mono|T.max}}. Note that {{mono|T.min}} is not stored anywhere else in the vEB tree, while {{mono|T.max}} is. If T is empty then we use the convention that {{mono|1=T.max=−1}} and {{mono|1=T.min=M}}. Any other value x is stored in the subtree {{mono|T.children[i]}} where {{math|i {{=}} ⌊x/{{sqrt|M}}⌋}}. The auxiliary tree {{mono|T.aux}} keeps track of which children are non-empty, so {{mono|T.aux}} contains the value j if and only if {{mono|T.children[j]}} is non-empty.

FindNext

The operation {{mono|FindNext(T, x)}} that searches for the successor of an element x in a vEB tree proceeds as follows: If {{mono|xi {{=}} x/{{sqrt|M}}}}. If {{mono|xi in {{mono|T.aux}}. This gives us the index j of the first subtree that contains an element larger than x. The algorithm then returns {{mono|T.children[j].min}}. The element found on the children level needs to be composed with the high bits to form a complete next element.

 '''function''' FindNext(T, x).     '''if''' x < T.min '''then'''         '''return''' T.min     '''if''' x ≥ T.max '''then''' ''// no next element''         '''return''' M     i = floor(x/{{sqrt|''M''}})     lo = x mod {{sqrt|''M''}}     hi = x − lo     '''if''' lo < T.children[i].max '''then'''         '''return''' hi + FindNext(T.children[i], lo)     '''return''' hi + T.children[FindNext(T.aux, i)].min '''end'''

Note that, in any case, the algorithm performs {{math|O(1)}} work and then possibly recurses on a subtree over a universe of size {{math|M^{{{sfrac|1|2}}}}} (an {{math|{{sfrac|m|2}}}} bit universe). This gives a recurrence for the running time of {{tmath|1=T(m)=T(m/2) + O(1)}}, which resolves to {{math|1=O(log m) = O(log log M)}}.

Insert

The call {{mono|insert(T, x)}} that inserts a value {{mono|x}} into a vEB tree {{mono|T}} operates as follows:

If T is empty then we set {{mono|1=T.min = T.max = x}} and we are done.
Otherwise, if {{mono|x<T.min}} then we insert {{mono|T.min}} into the subtree {{mono|i}} responsible for {{mono|T.min}} and then set {{mono|1=T.min = x}}. If {{mono|T.children[i]}} was previously empty, then we also insert {{mono|i}} into {{mono|T.aux}}
Otherwise, if {{mono|x>T.max}} then we insert {{mono|x}} into the subtree {{mono|i}} responsible for {{mono|x}} and then set {{mono|1=T.max = x}}. If {{mono|T.children[i]}} was previously empty, then we also insert {{mono|i}} into {{mono|T.aux}}
Otherwise, {{mono|T.min< x < T.max}} so we insert {{mono|x}} into the subtree {{mono|i}} responsible for {{mono|x}}. If {{mono|T.children[i]}} was previously empty, then we also insert {{mono|i}} into {{mono|T.aux}}.

In code:

 '''function''' Insert(T, x)     '''if''' T.min > T.max '''then''' ''// T is empty''         T.min = T.max = x;         '''return'''     '''if''' x < T.min '''then'''         swap(x, T.min)     '''if''' x > T.max '''then'''         T.max = x     i = floor(x / {{sqrt|''M''}})     lo = x mod {{sqrt|''M''}}     Insert(T.children[i], lo)     '''if''' T.children[i].min == T.children[i].max '''then'''         Insert(T.aux, i) '''end'''

The key to the efficiency of this procedure is that inserting an element into an empty vEB tree takes {{math|O(1)}} time. So, even though the algorithm sometimes makes two recursive calls, this only occurs when the first recursive call was into an empty subtree. This gives the same running time recurrence of {{tmath|1=T(m)=T(m/2) + O(1)}} as before.

Delete

Deletion from vEB trees is the trickiest of the operations. The call {{mono|Delete(T, x)}} that deletes a value x from a vEB tree T operates as follows:

If {{mono|1=T.min = T.max = x}} then x is the only element stored in the tree and we set {{mono|1=T.min = M}} and {{mono|1=T.max = −1}} to indicate that the tree is empty.
Otherwise, if {{mono|1=x == T.min}} then we need to find the second-smallest value y in the vEB tree, delete it from its current location, and set {{mono|1=T.min=y}}. The second-smallest value y is {{mono|T.children[T.aux.min].min}}, so it can be found in {{math|O(1)}} time. We delete y from the subtree that contains it.
If {{mono|x≠T.min}} and {{mono|x≠T.max}} then we delete x from the subtree {{mono|T.children[i]}} that contains x.
If {{mono|1=x == T.max}} then we will need to find the second-largest value y in the vEB tree and set {{mono|1=T.max=y}}. We start by deleting x as in previous case. Then value y is either {{mono|T.min}} or {{mono|T.children[T.aux.max].max}}, so it can be found in {{math|O(1)}} time.
In any of the above cases, if we delete the last element x or y from any subtree {{mono|T.children[i]}} then we also delete i from {{mono|T.aux}}

In code:

 '''function''' Delete(T, x)     '''if''' T.min == T.max == x '''then'''         T.min = M         T.max = −1         '''return'''     '''if''' x == T.min '''then'''         hi = T.aux.min * {{sqrt|''M''}}         j = T.aux.min         T.min = x = hi + T.children[j].min     i = floor(x / {{sqrt|''M''}})     lo = x mod {{sqrt|''M''}}     Delete(T.children[i], lo)     '''if''' T.children[i] is empty '''then'''         Delete(T.aux, i)     '''if''' x == T.max '''then'''         '''if''' T.aux is empty '''then'''             T.max = T.min         '''else'''             hi = T.aux.max * {{sqrt|''M''}}             j = T.aux.max             T.max = hi + T.children[j].max '''end'''

Again, the efficiency of this procedure hinges on the fact that deleting from a vEB tree that contains only one element takes only constant time. In particular, the last line of code only executes if x was the only element in {{mono|T.children[i]}} prior to the deletion.

Discussion

The assumption that {{math|log m}} is an integer is unnecessary. The operations {{math|x/{{sqrt|M}}}} and {{math|x mod {{sqrt|M}}}} can be replaced by taking only higher-order {{math|⌈m/2⌉}} and the lower-order {{math|⌊m/2⌋}} bits of {{mvar|x}}, respectively. On any existing machine, this is more efficient than division or remainder computations.

The implementation described above uses pointers and occupies a total space of {{math|O(M) {{=}} O(2^m)}}. This can be seen as follows. The recurrence is .

Resolving that would lead to .

One can, fortunately, also show that {{math|S(M) {{=}} M−2}} by induction.^[4]

In practical implementations, especially on machines with shift-by-k and find first zero instructions, performance can further be improved by switching to a bit array once {{mvar|m}} equal to the word size (or a small multiple thereof) is reached. Since all operations on a single word are constant time, this does not affect the asymptotic performance, but it does avoid the majority of the pointer storage and several pointer dereferences, achieving a significant practical savings in time and space with this trick.

An obvious optimization of vEB trees is to discard empty subtrees. This makes vEB trees quite compact when they contain many elements, because no subtrees are created until something needs to be added to them. Initially, each element added creates about {{math|log(m)}} new trees containing about {{math|m/2}} pointers all together. As the tree grows, more and more subtrees are reused, especially the larger ones. In a full tree of {{math|2^m}} elements, only {{math|O(2^m)}} space is used. Moreover, unlike a binary search tree, most of this space is being used to store data: even for billions of elements, the pointers in a full vEB tree number in the thousands.

However, for small trees the overhead associated with vEB trees is enormous: on the order of {{math|{{sqrt|M}}}}. This is one reason why they are not popular in practice. One way of addressing this limitation is to use only a fixed number of bits per level, which results in a trie. Alternatively, each table may be replaced by a hash table, reducing the space to {{math|O(n log M)}} (where {{mvar|n}} is the number of elements stored in the data structure) at the expense of making the data structure randomized. Other structures, including y-fast tries and x-fast tries have been proposed that have comparable update and query times and also use randomized hash tables to reduce the space to {{math|O(n)}} or {{math|O(n log M)}}.

References

1. ^Peter van Emde Boas: Preserving order in a forest in less than logarithmic time (Proceedings of the 16th Annual Symposium on Foundations of Computer Science 10: 75-84, 1975)
2. ^Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) (University of Aarhus, Department of Computer Science)
3. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. {{ISBN|978-0-262-53305-8}}. Chapter 20: The van Emde Boas tree, pp. 531–560.
4. ^{{cite web|last=Rex|first=A|title=Determining the space complexity of van Emde Boas trees|url=http://mathoverflow.net/questions/2245/determining-the-space-complexity-of-van-emde-boas-trees|accessdate=2011-05-27}}