Search data structure

<h2 id="classification">Classification</h2>
The simplest kind of query is to locate a record that has a specific field (the key) equal to a specified value v. Other common kinds of query are "find the item with smallest (or largest) key value", "find the item with largest key value not exceeding v", "find all items with key values between specified bounds vmin and vmax".
In certain databases the key values may be points in some <a href="/facts/Dimension_(mathematics)/0ktmUyac">multi-dimensional space</a>. For example, the key may be a geographic position (<a href="/facts/Latitude/IBYqkjhU">latitude</a> and <a href="/facts/Longitude/HsC61ML9">longitude</a>) on the <a href="/facts/Earth/HLLmDfj0">Earth</a>. In that case, common kinds of queries are "find the record with a key closest to a given point v", or "find all items whose key lies at a given distance from v", or "find all items within a specified region R of the space".
A common special case of the latter are simultaneous range queries on two or more simple keys, such as "find all employee records with salary between 50,000 and 100,000 and hired between 1995 and 2007".

<h3>Single ordered keys</h3>
<ul><li><a href="/facts/Array_data_structure/BKGvF8AM">Array</a> if the key values span a moderately compact interval.</li>
<li>Priority-sorted list; see <a href="/facts/Linear_search/cBh6w2sq">linear search</a></li>
<li>Key-sorted array; see <a href="/facts/Binary_search/FFmQzunc">binary search</a></li>
<li><a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">Self-balancing binary search tree</a></li>
<li><a href="/facts/Hash_table/Ht4ptDPF">Hash table</a></li></ul>
<h3>Finding the smallest element</h3>
<ul><li><a href="/facts/Heap_(data_structure)/A67B0K7L">Heap</a></li></ul>
<h2 id="asymptotic-worst-case-analysis">Asymptotic worst-case analysis</h2>
In this table, the <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic</a> <a href="/facts/Big-O_notation/weFFjSWg">notation O(f(n))</a> means "not exceeding some fixed multiple of f(n) in the worst case."

<table><tbody><tr><th>Data Structure</th><th>Insert</th><th>Delete</th><th>Balance</th><th>Get at index</th><th>Search</th><th>Find minimum</th><th>Find maximum</th><th>Space usage</th></tr><tr><td>Unsorted <a href="/facts/Array_data_structure/BKGvF8AM">array</a></td><td><a href="/facts/Constant_time/77T62gmf">O(1)</a>(see note)</td><td>O(1)(see note)</td><td>N/A</td><td>O(1)</td><td>O(n)</td><td>O(n)</td><td>O(n)</td><td>O(n)</td></tr><tr><td><a href="/facts/Sorted_array/VAuF76AG">Sorted array</a></td><td>O(n)</td><td>O(n)</td><td>N/A</td><td>O(1)</td><td>O(log n)</td><td>O(1)</td><td>O(1)</td><td>O(n)</td></tr><tr><td><a href="/facts/Stack_(abstract_data_type)/bj7l94v1">Stack</a></td><td>O(1)</td><td>O(1)</td><td></td><td></td><td>O(n)</td><td></td><td></td><td>O(n)</td></tr><tr><td><a href="/facts/Queue_(abstract_data_type)/hVPjPXus">Queue</a></td><td>O(1)</td><td>O(1)</td><td></td><td></td><td>O(n)</td><td></td><td></td><td>O(n)</td></tr><tr><td>Unsorted <a href="/facts/Linked_list/Ik4JTgJW">linked list</a></td><td>O(1)</td><td>O(1)<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a></td><td>N/A</td><td>O(n)</td><td>O(n)</td><td>O(n)</td><td>O(n)</td><td>O(n)</td></tr><tr><td>Sorted linked list</td><td>O(n)</td><td>O(1)<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></td><td>N/A</td><td>O(n)</td><td>O(n)</td><td>O(1)</td><td>O(1)</td><td>O(n)</td></tr><tr><td><a href="/facts/Skip_list/fF200SJg">Skip list</a></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td><a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">Self-balancing binary search tree</a></td><td>O(log n)</td><td>O(log n)</td><td>O(log n)</td><td>N/A</td><td>O(log n)</td><td>O(log n)</td><td>O(log n)</td><td>O(n)</td></tr><tr><td><a href="/facts/Heap_(data_structure)/A67B0K7L">Heap</a></td><td>O(log n)</td><td>O(log n)</td><td>O(log n)</td><td>N/A</td><td>O(n)</td><td>O(1) for a min-heapO(n) for a max-heap<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></td><td>O(1) for a max-heapO(n) for a min-heap<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></td><td>O(n)</td></tr><tr><td><a href="/facts/Hash_table/Ht4ptDPF">Hash table</a></td><td>O(1)</td><td>O(1)</td><td>O(n)</td><td>N/A</td><td>O(1)</td><td>O(n)</td><td>O(n)</td><td>O(n)</td></tr><tr><td><a href="/facts/Trie/cXNr0ScT">Trie</a> (k = average length of key)</td><td>O(k)</td><td>O(k)</td><td>N/A</td><td>O(k)</td><td>O(k)</td><td>O(k)</td><td>O(k)</td><td>O(k n)</td></tr><tr><td><a href="/facts/Cartesian_tree/81061rdb">Cartesian tree</a></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td><a href="/facts/B-tree/IHE2l8GR">B-tree</a></td><td>O(log n)</td><td>O(log n)</td><td>O(log n)</td><td>N/A</td><td>O(log n)</td><td>O(log n)</td><td>O(log n)</td><td>O(n)</td></tr><tr><td><a href="/facts/Red%E2%80%93black_tree/ckgWTV7G">Red–black tree</a></td><td>O(log n)</td><td>O(log n)</td><td></td><td></td><td>O(log n)</td><td></td><td></td><td>O(n)</td></tr><tr><td><a href="/facts/Splay_tree/DHKCdoST">Splay tree</a></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td><a href="/facts/AVL_tree/DfexIbS6">AVL tree</a></td><td></td><td></td><td></td><td></td><td>O(log n)</td><td></td><td></td><td></td></tr><tr><td><a href="/facts/K-d_tree/XuhcfKKq">k-d tree</a></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
Note: Insert on an unsorted array is sometimes quoted as being O(n) due to the assumption that the element to be inserted must be inserted at one particular location of the array, which would require shifting all the subsequent elements by one position. However, in a classic array, the array is used to store arbitrary unsorted elements, and hence the exact position of any given element is of no consequence, and insert is carried out by increasing the array size by 1 and storing the element at the end of the array, which is a O(1) operation.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> Likewise, the deletion operation is sometimes quoted as being O(n) due to the assumption that subsequent elements must be shifted, but in a classic unsorted array the order is unimportant (though elements are implicitly ordered by insert-time), so deletion can be carried out by swapping the element to be deleted with the last element in the array and then decrementing the array size by 1, which is a O(1) operation.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs. Also two or more data structures can be combined to obtain lower costs.

<h2 id="footnotes">Footnotes</h2>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/List_of_data_structures/25H7hEPa">List of data structures</a></li>
<li><a href="/facts/Skip_list/fF200SJg">Skip list</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0. LIST-DELETE runs in O(1) time, but if to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH. <a href="978-0-262-53091-0" target="_blank">978-0-262-53091-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0. LIST-DELETE runs in O(1) time, but if to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH. <a href="978-0-262-53091-0" target="_blank">978-0-262-53091-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0. There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property... the largest element in a max-heap is stored at the root... The smallest element in a min-heap is at the root... The operation HEAP-MAXIMUM returns the maximum heap element in Θ(1) time by simply returning the value A[1] in the heap. <a href="978-0-262-53091-0" target="_blank">978-0-262-53091-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0. There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property... the largest element in a max-heap is stored at the root... The smallest element in a min-heap is at the root... The operation HEAP-MAXIMUM returns the maximum heap element in Θ(1) time by simply returning the value A[1] in the heap. <a href="978-0-262-53091-0" target="_blank">978-0-262-53091-0</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Allen Sherrod (2007). Data Structures and Algorithms for Game Developers. Cengage Learning. ISBN 978-1-58450-663-8. The insertion of an item into an unordered array does not depend on anything other than placing the new item at the end of the list. This gives the insertion into an unordered array of O(1). <a href="978-1-58450-663-8" target="_blank">978-1-58450-663-8</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0. <a href="978-0-262-53091-0" target="_blank">978-0-262-53091-0</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">"Algorithm - the time complexity of deletion in a unsorted array". Finding the element with a given value is linear. Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element. <a href="https://stackoverflow.com/questions/9358481/algorithm-the-time-complexity-of-deletion-in-a-unsorted-array#9358634" target="_blank">https://stackoverflow.com/questions/9358481/algorithm-the-time-complexity-of-deletion-in-a-unsorted-array#9358634</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Search data structure open-in-new

Search data structure