Fusion tree

A fusion tree is a type of tree data structure in computer science. It 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.

References

• MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.897: Advanced Data Structures: Lecture 5, More fusion trees; self-organizing data structures, move-to-front, static optimality, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.851: Advanced Data Structures: Lecture 13, Fusion Tree nodes, Prof. Erik Demaine (Spring 2007)