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. Each node contains a splitter, a value less than or equal to all values in the subtree which is used during search. 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. They have mainly theoretical importance.

Tree structure

An exponential tree is a rooted tree values is defined recursively:

• children

• The splitter of the root is the same as the splitter of the leftmost child

• The splitters of all children are stored in a local data structure

• values

.

Local data structure

.

A Fusion tree can be used as this data structure.

Operations

Search

The exponential tree can be searched in the same way as a normal search tree. In each node, the local data structure can be used to find the next child quickly.

denote the time complexity of the search. Then it satisfies the following recurrence:

Insert

Delete

References