Exponential tree

Exponential trees achieve optimal asymptotic complexity on some operations. They have mainly theoretical importance.

Tree structure

An exponential tree is a rooted tree where every node contains a splitter and every leaf node contains a value. The value may be different from the splitter. An exponential tree with ${\displaystyle n}$ values is defined recursively:

• The root has ${\displaystyle \mathrm{\Theta }(n^{1/k})}$ 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
• The subtrees are exponential trees with ${\displaystyle \mathrm{\Theta }(n^{1-1/k})}$ values

An additional condition is that searching for a value using the splitters must yield the correct node (i.e. the one containing the value). Therefore, if a root of a subtree contains the splitter ${\displaystyle s}$ and its right sibling contains the splitter ${\displaystyle s^{\prime }}$, then this subtree can only contain keys in the range ${\displaystyle [s,s^{\prime })}$.