그래프
- 정점과 간선으로 이루어진 자료 구조
- 방향 유/무에 따라 단방향 그래프, 양방향 그래프로 나뉨
- 정점으로 나가는/들어오는 간선 - outdegree/indegree
- 간선에 가중치가 있을 수 있음트리
- 사이클이 없는 그래프
- 트리 구조로 배열된 계층적 데이터의 집합
- 루트 노드, 내부 노드, 리프 노드로 구성 특징
- 부모, 자식 계층 구조를 가짐
- V - 1 = E (노드 수 - 1 = 간선 수)
- 두 노드 사이의 경로는 유일무이함구성
- 루트 노드 - 가장 위에 있는 노드
- 내부 노드 - 루트 노드와 리프 노드 사이
- 리프 노드 - 자식 노드가 없는 노드트리의 높이와 레벨
- 깊이, 레벨 - 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
- 높이: 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
- 서브트리: 트리 내의 하위 집합이진 트리
- 모든 노드의 자식 노드수가 두 개 이하인 트리이진 탐색 트리 (BST)
- 노드의 왼쪽 - 노드 값보다 작은 값
- 노드의 오른쪽 - 노드 값보다 큰 값
- 탐색 평균 O(log N), 최악 O(N) → 삽입 순서에 따라 트리 구조가 선형적일 수 있음
→ AVL Tree, Red Black Tree로 균등화 가능순회
전위 (preorder)
루트 → 왼쪽 → 오른쪽
1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14중위 (inorder)
왼쪽 → 루트 → 오른쪽
8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 → 14 → 7후위 (postorder)
왼쪽 → 오른쪽 → 루트
8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1레벨 (level-order)
루트부터 계층별로 방문
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 …※ 루트의 위치에 따라 전위, 중위, 후위 구분
