Exponential tree

Exponential tree
Type	tree
Invented	1995
Invented by	Arne Andersson
Time complexity in big O notation Operation Average Worst case Search O(min(√log n, log n/log w+ log log n, log w log log n)) O(min(√log n, log n/log w+ log log n, log w log log n)) Insert O(min(√log n, log n/log w+ log log n, log w log log n)) O(min(√log n, log n/log w+ log log n, log w log log n)) Delete O(min(√log n, log n/log w+ log log n, log w log log n)) O(min(√log n, log n/log w+ log log n, log w log log n)) Space complexity Space O(n) O(n)

An exponential tree is a type of search tree where the number of nodes in its subtrees decreases exponentially with increasing depth. The number of children of the nodes decreases doubly-exponentially. 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.

References

• Andersson, Arne (October 1996). "Faster deterministic sorting and searching in linear space". Proceedings of 37th Conference on Foundations of Computer Science: 135–141. doi:10.1109/SFCS.1996.548472.
• Andersson, Arne; Thorup, Mikkel (2007-06-01). "Dynamic ordered sets with exponential search trees". Journal of the ACM. 54 (3): 13–es. doi:10.1145/1236457.1236460. ISSN 0004-5411.