Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Exponential tree
open-in-new
<p>An exponential tree is a type of <a href="/facts/Search_tree/zJIIMEH8">search tree</a> where the number of children of its nodes decreases doubly-<a href="/facts/Exponential_function/ewlYxvR2">exponentially</a> 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. </p><p>Exponential trees achieve optimal asymptotic complexity on some operations. They have mainly theoretical importance. </p>