View source for Exponential tree

{{Infobox data structure
|name=Exponential tree
|type=tree
|invented_by=Arne Andersson
|invented_year=1995
|space_avg=O(''n'')
|space_worst=O(''n'')
|search_avg=O(min({{radic|log&nbsp;''n''}}, log&nbsp;''n''/log&nbsp;''w''+ log&nbsp;log&nbsp;''n'', log&nbsp;''w'' log&nbsp;log&nbsp;''n''))
|search_worst=O(min({{radic|log&nbsp;''n''}}, log&nbsp;''n''/log&nbsp;''w''+ log&nbsp;log&nbsp;''n'', log&nbsp;''w'' log&nbsp;log&nbsp;''n''))
|insert_avg=O(min({{radic|log&nbsp;''n''}}, log&nbsp;''n''/log&nbsp;''w''+ log&nbsp;log&nbsp;''n'', log&nbsp;''w'' log&nbsp;log&nbsp;''n''))
|insert_worst=O(min({{radic|log&nbsp;''n''}}, log&nbsp;''n''/log&nbsp;''w''+ log&nbsp;log&nbsp;''n'', log&nbsp;''w'' log&nbsp;log&nbsp;''n''))
|delete_avg=O(min({{radic|log&nbsp;''n''}}, log&nbsp;''n''/log&nbsp;''w''+ log&nbsp;log&nbsp;''n'', log&nbsp;''w'' log&nbsp;log&nbsp;''n''))
|delete_worst=O(min({{radic|log&nbsp;''n''}}, log&nbsp;''n''/log&nbsp;''w''+ log&nbsp;log&nbsp;''n'', log&nbsp;''w'' log&nbsp;log&nbsp;''n''))
}}

An '''exponential tree''' is a type of [[Search tree|search tree]] where the number of children of its nodes decreases doubly-[[Exponential function|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 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 <math>n</math> values is defined recursively:
* The root has <math>\Theta(n^{1/k})</math> 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 <math>\Theta(n^{1-1/k})</math> 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 <math>s</math> and it's right sibling contains the splitter <math>s'</math>, then this subtree can only contain keys in the range <math>[s,s')</math>.

== Local data structure ==
The tree uses a static data structure in every inner node to allow fast lookup of values. It must be possible to build this structure with <math>d</math> values in time <math>O(d^{k-1})</math>. The lookup time in this structure is denoted <math>S(d)</math>.

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.

Let <math>T(n)</math> denote the time complexity of the search. Then it satisfies the following recurrence:

<math>T(n) \le T(n^{1-1/k}) + O(S(n))</math>

=== Insert ===

=== Delete ===

== References ==
* {{Cite book |last=Andersson |first=Arne |title=Proceedings of 37th Conference on Foundations of Computer Science |chapter=Faster deterministic sorting and searching in linear space |date=October 1996 |chapter-url=https://ieeexplore.ieee.org/document/548472 |pages=135–141 |doi=10.1109/SFCS.1996.548472|isbn=0-8186-7594-2 |s2cid=13603426 }}
* {{Cite journal |last1=Andersson |first1=Arne |last2=Thorup |first2=Mikkel |date=2007-06-01 |title=Dynamic ordered sets with exponential search trees |url=https://dl.acm.org/doi/10.1145/1236457.1236460 |journal=Journal of the ACM |volume=54 |issue=3 |pages=13–es |doi=10.1145/1236457.1236460 |arxiv=cs/0210006 |s2cid=8175703 |issn=0004-5411}}

{{CS-Trees}}

[[Category:Trees (data structures)]]


{{Sourceattribution|Exponential tree}}