Search data structure: Difference between revisions

Revision as of 22:16, 18 July 2018

Revision as of 22:51, 18 July 2018

Line 58:

| ''O''(1)

| ''O''(''n'')

|-

| [[Stack (abstract data type)|Stack]]

|

|

|

|

|

|

|

|

|-

| [[Queue (abstract data type)|Queue]]

|

|

|

|

|

|

|

|

|-

| Unsorted [[linked list]]

| ''O''(1)

| ''O''(1)<ref name="listdelete">{{cite book |title=[[Introduction to Algorithms]] |publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|quote=LIST-DELETE runs in ''O''(1) time, but if we wish to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH.}}</ref>

| N/A

| ''O''(''n'')

Line 78 ⟶ 98:

| ''O''(1)

| ''O''(''n'')

|-

| [[Skip list]]

|

|

|

|

|

|

|

|

|-

| [[Self-balancing binary search tree]]

Line 118 ⟶ 148:

| ''O''(''k'')

| ''O''(''k'' ''n'')

|-

| [[Cartesian tree]]

|

|

|

|

|

|

|

|

|-

| [[B-tree]]

|

|

|

|

|

|

|

|

|-

| [[Red-black tree]]

|

|

|

|

|

|

|

|

|-

| [[Splay tree]]

|

|

|

|

|

|

|

|

|-

| [[AVL tree]]

|

|

|

|

|

|

|

|

|-

| [[k-d tree]]

|

|

|

|

|

|

|

|

|}