An exponential tree is a type of search tree where the number of children of its nodes decreases doubly-exponentially with increasing depth.
Values are stored only in the leaf nodes.
Exponential trees use another data structure in inner nodes containing the splitters from children, allowing fast lookup.
Exponential trees achieve optimal asymptotic complexity on some operations.
An exponential tree is a rooted tree where every node contains a splitter and every leaf node contains a value.
The tree uses a static data structure in every inner node to allow fast lookup of values.
The lookup time in this structure is denoted
A Fusion tree can be used as this data structure.
In each node, the local data structure can be used to find the next child quickly.
denote the time complexity of the search.
This algorithms or data structures-related article is a stub.