자료구조의 흐름

#자료구조/알고리즘

1945 by 노이만
배열(Array)

1945 by 노이만
정렬되는 배열(Sorted Array)

트리의 과도기적 형태 같은데, 효율은 굉장히 달린다고 할수 있겠다.

1946 by 튜링
스택(Stack)
->굳이 설명하지 않는다.

1953 by Hans Peter Luhn, ...
해시테이블

1955 by Allen Newell, Cliff Shaw, Herbert Simon
연결리스트(Linked List)
->굳이 설명하지 않는다.

1959 by René de la Briandais
트라이(Trie)
->문자열 전용 자료구조다.
->기본적으로 다진트리를 사용한다. k의 크기는 문자의 총 개수다.

1961 by P.F. Windley, A.D. Booth, A.J.T. Colin, T.N. Hibbard
이진탐색 트리

->그냥 이진탐색트리. 높이 보장이 없어서 성능이 굉장히 불안정하다.

->이제 좀 안정적이다.

1964 by J. W. J. Williams
힙(Heap)
->최소값/최대값을 구하기에 최적화된 자료구조.
->삽입/삭제는 보통 O(log N)의 복잡도를 보인다.
->힙 정렬에 사용되기도 한다.

->이것도 안정적인 트리이긴 하다.

1972 by Rudolf Bayer
레드블랙트리

->언어에서 제공하는 트리구조는 보통 이걸 쓴다.

1975 by Jon Louis Bentley
KD 트리

다차원 트리다.
메모리 표현에 사용한다.

1979 by Jon Louis Bentley
범위 트리

1980 by Jean Vuillemin
트립(Treap)

1984 by Big Brother
피보나치 힙

->힙의 변종이다.
->힙끼리의 효율적인 병합을 위해 고안됐다고 한다.

1984 by Big Brother
R 트리

->B트리와 유사하다고 한다.

->안정적인듯 하지만 진짜 안정적인 트리는 아닌 그런 기묘한 트리다.
->검색 트리 치곤 구현이 쉬운 편이다.

1989 by W. Pugh
스킵 리스트

->접근시간을 쥐어짠 기존 연결리스트의 변종이다.

1996 by Edward Sitarski
해시 배열 트리(Hashed Array Tree)

2004 by by Erik D. Demaine, Dion Harmon, John Iacono, Mihai Pătrașcu
탱고 트리
->검색 및 삽입삭제 복잡도가 O(log log N)이다.