그래프
- 정점(vertex)과 간선(edge)로 이뤄진 자료구조
- 간선의 가중치 유무에 따라 가중치 그래프, 비가중치 그래프로 나뉜다.
- 진입차수, 진출차수 : 각각 정점에 들어오고 나가는 간선이 몇 개인지
- 자기 루프 : 정점이 자기 자신에게 간선으로 연결돼 있는 경우
- 사이클 : 노드에서 출발해 해당 노드로 다시 돌아올 수 있는 경우 사이클이 존재
트리
- 단방향, 계층적 자료구조
- 부모 노드에 여러 자식이 연결될 수 있는 비선형 구조
- 리프 노드(leaf node) : 자식이 없는 노드
- 형제 노드 : 같을 레벨이 있는 노드
- 서브 트리 : 트리 내부의 트리
이진 트리
- 자식 노드가 최대 두 개인 노드들로 구성된 트리
- 정 이진 트리 : 각 노드들은 두 개의 자식 노드를 갖는다.(1개만 가질 수 없다)
- 완전 이진 트리 : 마지막 레벨을 제외하고 모든 노드는 가득 차 있으며, 마지막 레벨의 노드는 왼쪽으로 몰려 있다.
- 포화 이진 트리 : 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 차 있다.
- 이진 탐색 트리 : 왼쪽 자식의 값이 루트 노드나 부모보다 작고, 오른쪽 자식의 값이 루트 노드나 부모보다 큰 값을 가지는 트리
