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 almost identical to a binary search tree, with the exception that the dimension of the tree is not the same at all levels. In a normal binary search tree, each node has a dimension (d) of 1, and has 2^d children. In an exponential tree, the dimension equals the depth of the node, with the root node having a d = 1. So the second level can hold four nodes, the third can hold eight nodes, the fourth 16 nodes, and so on.

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.