Implementing a Fusion Tree in C++ (2017)

Visit Project Repository | Full Paper

This was the final project for a class at MIT (6.851 - Advanced Data Structures).

A Fusion Trees is a static Data Structure that allows for predecessor queries in constant time on a set of constant size of numbers, but that requires significant large word sizes to be implemented in a computer that follows the standard word ram model. In this work, we provide the C++ code and reference to our implementation of fusion trees that performs predecessor queries with a constant number of calls to standard arithmetic operations of a general Big Integer.