Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Priority search tree
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a priority search tree is a tree data structure for storing points in two dimensions. It was originally introduced by <a href="/facts/Edward_M._McCreight/2rlaFExR">Edward M. McCreight</a>. It is effectively an extension of the <a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a> with the purpose of improving the search time from O(<i>n</i>) to O(<i>s</i> + log <i>n</i>) time, where <i>n</i> is the number of points in the tree and <i>s</i> is the number of points returned by the search. </p>