 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (March 2021) |
| Exponential tree | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | |||||||||||||||||||||||
| Invented | 1995 | |||||||||||||||||||||||
| Invented by | Arne Andersson | |||||||||||||||||||||||
| ||||||||||||||||||||||||
An exponential tree is a type of search tree where the number of children of its nodes decreases doubly-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.
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search