-
- Graph
- Tree
- Binary Tree
- Full Binary Tree
- Complete Binary Tree
- Binary Search Tree
- Heap
- Trie
- AVL Tree
- Red-Black Tree
Graph 그래프
1. 정점(node, vetex)와 간선(edge)로 이루어진 자료구조
2. 방향 그래프와 무방향 그래프로 나누어진다.
무방향 그래프
: 두 정점을 연결하는 간선에 방향이 없는 그래프연결그래프 모든 정점간 경로가 존재할 때 비연결그래프 모든 정점간 경로가 존재하지 않을 떄 완전그래프: 그래프 모든 정점이 서로 연결되어 있는 그래프
3. 차수(degree) : 무방향 그래프에서 한 정점에 인접한 간선 수
진입차수(ind-degree): 방향 그래프에서 내부로 향하는 간선 수
진출 차수: 방향 그래프에서 외부로 향하는 간선 수
사이클: 경로의 시작 정점과 종료 정점이 동일한 것
4. 표현방법: 인접행렬과 인접 리스트
트리와 그래프 차이점
트리는 그래프의 일종이다.
그래프는 정점마다 간선이 있을 수도 없을 수도 있다.부모-자식 개념이 존재하지 않는다. 사이클이 존재한다.
Tree 트리
1. 정점(node, vetex)와 간선(edge)로 이루어진 자료구조
2. 루트 노드가 존재, 루트노드와 자식노드로 구성 => level 존재
3.사이클 존재 X
4. 표현방법: 인접행렬과 인접 리스트
5.. 서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프
6. 힙을 구현하는 방법 중 하나
Binary Tree 이진 트리
각 노드가 최대 두개의 자식을 가지는 트리
-Left Node, Right Node
Full Binary Tree(전 이진트리)
모든 노드가 자식을 0개 혹은 2개 가지는 트리
Complete Binary Tree(완전 이진트리)
노드가 꽉 차잇으며, 마지막 레벨에서는 왼쪽으로 차 있는 트리
-왼쪽 노드부터 순서대로 채움
-루트 노드부터 시작해 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서
-배열을 통해 표현 가능
Binary Search Tree(이진 탐색 트리)
1. 좌-우 노드가 부모를 기준으로 정렬된 트리
- 왼쪽노드는 부모보다 작고, 오른쪽 노드는 부모보다 크다.
- 트리에서 가장 왼쪽에 위치한 노드가 가장 작은값을 가진다.
2.평균 O(longN) 최악 o(N)
- Heap
- Trie
- AVL Tree
- Red-Black Tree
힙
완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
1.부모-자식간 정렬된 이진 트리
최대 힙 트리: 부모> 자식
최소 힙 트리: 자식>부모
2.완전 이진트리로 구성된다 => 배열로 표현가능
3.우선순위큐에서 사용된다.
4.중복된 값 허용
AVL Tree
스스로 균형을 잡는 이진 트리 =>어떤 시점에서 높이 차이가 1보다 커지면 회전을 통해 균형을 잡아 높이 차이를 줄인다.
이진탐색트리의 속성을 가짐
검색,삽입,삭제 시간복잡도: O(logN)
Red-Black Tree
각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 잡는 트리
1. 루트노드 색깔 = 검정
모든 NIL 리프 노드의 색은 검정
빨간 노드의 자식도느 색은 검정
모든 루트노드에서 리프노드까지의 경로에서 만나는 블랙 노드의 수는 같다.
2.삽입되는 노드의 색은 빨간색
Trie
문자열 저장 및 탐색에 적합한 트리
문자열 탐색을 빠르게 하지만 메모리 측면에서 자식들에 대한 포인터들을 모두 저장해두고 있어 비표율적이다.