Fusion tree

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

<math>O\left(\frac{\log n}{\log \log n}\right)<math>

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

References

• MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine