User:Theresource/Fusion tree

This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (Learn how and when to remove this message)

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

${\displaystyle 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 ${\displaystyle O\left(1\right)}$ time, using a bitwise AND operation with an apropriate bit mask.

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

Category:Trees (data structures)

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e