Content deleted Content added
→Asymptotic amortized worst-case analysis: edit trie asymptotics |
IMO this is old and unused term. "Introduction to Algorithms" is not enough to justify it's usage today. |
||
Line 1:
{{Merge|Data structure}}
In [[computer science]], a '''search data structure'''{{citation needed}} is any [[data structure]] that allows the efficient retrieval of specific items from a [[set (mathematics)|set]] of items, such as a specific [[record (computer science)|record]] from a [[database]].
The simplest, most general, and least efficient search structure is merely an unordered sequential [[list (computing)|list]] of all the items. Locating the desired item in such a list, by the [[linear search]] method, inevitably requires a number of operations proportional to the number ''n'' of items, in the [[worst case complexity|worst case]] as well as in the [[average case complexity|average case]]. Useful search data structures allow faster retrieval; however, they are limited to queries of some specific kind. Moreover, since the cost of building such structures is at least proportional to ''n'', they only pay off if several queries are to be performed on the same database (or on a database that changes little between queries).
| |||