HastTable

Hash(또는 HashMap)은 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 인덱스를 이용한 빠른 검색 속도를 갖는다. 특정한 값을 searching하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 시간 복잡도가 O(1)이 되는 것이다.
[항상 O(1)이 아니고 average case에 대해서 O(1)인 것은 collision 때문이다.]

RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식의 자료구조이다.

먼저 레드 블랙 트리를 알아보기 전에 BST가 무엇인지 한번 더 알고 넘어가자.

• Heap

Tree

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.
트리는 계층적 관계를 표현하는 자료구조이며, 표현에 집중한다.
무엇인가를 저장하고 꺼내야 한다는 사고를 벗어나 트리라는 자료구조를 보자.

2019.03.20 일자 기준으로 공부했던 내용을 수정하려고 한다. 이유는 이렇게 정리해놨지만 머리에 기억으로 남지 않기 때문이다.

Stack

• Last In First Out(LIFO)의 구조로 나중에 들어간 원소가 가장 먼저 나오는 자료구조이다.
• 반대로 제일 먼저 들어간 원소가 가장 늦게 나온다.
• 함수의 콜스택에 쓰이고 문자열을 역순으로 출력할 때, 연산자 후위표기법 등에 쓰인다.