User:Theresource/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

$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. Because the fusion tree is very hard to understand, it is sometimes called the confusion tree.

The central idea leading to the fusion tree is to utilise a compacted form of a B-tree with a specific branching factor B such that all the keys of a node's childs can fit in a word of w bits. Then the selection of a child node can be done in $O\left(1\right)$ time, using a bitwise AND operation with an apropriate bit mask.

References

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

Category:Trees (data structures)