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 new trees containing about pointers all together. As the tree grows, more and more subtrees are reused, especially the larger ones. In a full tree of elements, only 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. The implementation described above uses pointers and occupies a total space of , proportional to the size of the key universe. This can be seen as follows. The recurrence is . Resolving that would lead to . One can, fortunately, also show that by induction. Similar structures The space usage of vEB trees is an enormous overhead unless a large fraction of the universe of keys is being stored. This is one reason why vEB trees are not popular in practice. This limitation can be addressed by changing the array used to store children to another data structure. One possibility is to use only a fixed number of bits per level, which results in a trie. Alternatively, each array may be replaced by a hash table, reducing the space to (where is the number of elements stored in the data structure) at the expense of making the data structure randomized. Other data structures including x-fast tries and y-fast tries have comparable update and query times to vEB trees and also use randomized hash tables to reduce the space to and respectively. Implementations There is a verified implementation in Isabelle (proof assistant). Both functional correctness and time bounds are proved. Efficient imperative Standard ML code can be generated. See also Integer sorting Predecessor problem Fusion tree Tango tree References Further reading Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). Lecture 11 notes. March 22, 2012. Computer science articles needing expert attention Priority queues Search trees