Exponential tree

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Exponential tree
Typetree
Invented1995
Invented byArne Andersson
Time complexity in big O notation
Algorithm Average Worst case
Space O(n) O(n)
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))

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 2d 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.

External links[edit]