Fusion tree

From Wikipedia, the free encyclopedia

 The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.
This article is orphaned as few or no other articles link to it.
Please help introduce links in articles on related topics. (May 2007)

A fusion tree is a tree data structure that implements an associative array with integer keys up to a fixed size; by exploiting the constant-time machine word multiplication operation available on many real processors, it is able to achieve all operations in

O\left(\frac{\log n}{\log \log n}\right)

time (see Big O notation), which is slightly faster asymptotically than a self-balancing binary search tree.

[edit] References

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.