Search data structure: Difference between revisions

Revision as of 14:46, 19 August 2009

Revision as of 01:39, 23 August 2009

Line 32:

|-

| Sorted linked list

| O(1n)

| O(1)

| O(n)

Line 38:

| O(n)

|-

| [[BinarySelf-balancing binary search tree|Balanced binary tree]]

| O(log n)

| O(log n)

Line 47:

| [[Heap (data structure)|Heap]]

| O(log n)

†| O(log n)<ref>Can only delete the max (or min in a min heap)</ref>

| O(log n)†

| N/AO(n)

| O(1)

| O(n)

Line 57:

| O(1)

| O(n)

| O(2nn)

|}

== Footnotes ==

† Can only delete the max (or min in a min heap)

{{footnotes}}

== See also ==