배열은 데이터를 입력하면 순차적으로 입력이 되며, 물리적 주소 또한 순차적입니다.
또한 한번 크기가 결정이 되면 변경이 불가능 합니다. 하지만 인덱스가 있어 데이터에 접근하는 속도가 빠릅니다.
하지만 중간에 삽입하거나 삭제하는 경우 인덱스를 재배열해야 하기 때문에 효율이 떨어집니다.
링크드 리스트는 다음 원소의 주소 값을 가지고 있어, 이를 이용해 리스트를 생성합니다.
따라서 크기가 가변적이고, 삽입과 삭제가 주소 값을 변경해 주면 되기 때문에 간편합니다.
하지만 중간에 있는 원소에 접근하기 위해서는 포인터를 따라 탐색이 필요해, 배열과 같이 한번에 접근할 수가 없습니다.
스택은 나중에 들어온 원소가 가장 먼저 빠져나갈 수 있는 자료구조입니다.
top이라는 포인터를 이용해 데이터에 접근합니다.
큐는 처음 들어온 원소가 가장 먼저 빠져나갈 수 있는 자료구조입니다.
front와 rear 두가지 포인터를 사용하며 front는 삭제시, rear는 삽입시 포인터에 변경이 이루어집니다.
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.
해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다.
해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고,
이 index를 활용해 값을 저장하거나 검색합니다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
'Perfect 이진 트리'는 깊이가 h일 때, 1에서 h까지 모든 노드가 두 개씩 채워져 있는 트리입니다.
'Complete 이진 트리'는 루트부터 리프노드 이전의 깊이 까지 모든 노드들이 2개의 자식을 가지고 있고, 리프 노드 깊이에서는 왼쪽부터 노드가 채워져 있는 트리를 말합니다.
'Full 이진 트리'는 모든 노드가 0개 또는 2개의 자식 노드만을 갖는 트리입니다.
그래프는 self-loop, 순환구조가 가능하며, 루트 노드라는 개념이 없습니다. 또한 노드들 사이에 방향성,
2개 이상의 엣지를 가지는 것이 가능합니다.
트리는 계층 구조이며, 한 개의 루트노드만이 존재하며, 모든 자식 노드는 하나의 부모노드만을 가집니다.
따라서 엣지의 개수가 항상 노드수-1개를 가집니다. 그리고, 트리는 방향성이 있는 그래프의 한 종류로 볼 수 있습니다.
완전 이진트리의 일종으로, 우선 순위 큐를 구현하기 위해 만들어진 자료구조 입니다.
Max, Min 두가지 방식으로 구성이 가능하고, 최댓값이나 최솟값을 빠르게 찾을 수 있습니다.
이진트리와의 차이점으로는 중복된 값을 허용한다는 점이 있습니다.
삽입 과정시,
새로운 원소에 대해
1. 힙의 마지막 노드에 이어서 삽입합니다.
2. 새로운 노드를 부모 노드들과 교환해서, 해당 힙의 성질을 만족시킵니다.
삭제시,
* 힙의 삭제는 루트의 삭제
1. Root를 꺼내옵니다.
2. 가장 끝에 있는 노드를 루트에 놓고, 교환을 통해 제자리를 찾습니다.
3. 힙트리가 재구성됩니다.
자식 노드의 개수가 2개 이상인 트리를 말합니다.
또한 노드 내의 데이터가 1개 이상일 수 있습니다.
노드 내의 데이터 수에 따라 M차 B-Tree라고 부르며, 차수가 짝수냐 홀수냐에 따라 알고리즘이 달라집니다.
한 노드는 [데이터 수+1]개의 자식을 가지며, 노드 내 데이터는 정렬된 상태이어야 합니다.
자식 노드의 데이터는 부모노드 데이터를 기준으로 데이터 보다 작은 값은 왼쪽 서브 트리,
큰값들은 오른쪽 서브 트리에 위치하는 형태를 취합니다.
데이터 탐색이 root부터 시작하며 데이터의 크기에 따라 어느 자식으로 이동할지 결정합니다.
삽입시 리프노드에 데이터가 가득차있으면 중간값을 부모노드로 해 트리를 재구성합니다.
최소신장트리(MST)는 가능한 신장트리 가운데 엣지 가중치의 합이 최소인 신장트리를 말합니다.
MST는 노드 간 연결성을 보장하면서 노드 사이를 잇는 거리/비용 등을 최소로 하는 그래프를 의미하기 때문에 응용 범위가 넓습니다.
* 크루스칼 알고리즘 / 프림 알고리즘
