1)트리(Tree)
1. 트리의 구조
– 데이터를 1:N의 계층 구조로 표현하는 자료구조
– 각 노드는 하나의 간선(Edge, Branch)으로 연결
– N개의 노드를 가진 트리의 간선 개수: N-1
– 방향성이 있는 비순환 그래프의 한 종류
– 트리의 구조에 따라 이진 트리, 포화 이진 트리, 완전 이진 트리 등으로 나뉜다.
2. 트리의 용어
– 노드는 위치와 서로의 관계에 따라 여러 역할을 가진다.
– 근(Root) 노드: 부모가 없는 노드, 트리에는 하나의 루트 노드만 존재
– 단말(Leaf) 노드: 자식이 없는 최하단 레벨 노드
– 내부(Internal) 노드: 단말 노드가 아닌 노드
– 형제(Sibling) 노드: 같은 부모를 갖는 노드
– Size: 자신을 포함한 모든 자식 노드 개수
– Depth: 자신의 부모 노드 개수
– Height: 자신으로부터 가장 깊은 단말 노드까지의 거리(간선 개수)
– 트리의 높이: 루트 노트로부터 가장 깊은 단말 노드까지의 거리(간선 개수)
– Level: 같은 깊이를 가지는 노드의 결합
– Degree: 자신의 자식 노드(간선) 개수
– 트리의 차수: 최대 차수를 가지는 노드의 차수
3. 이진(Binary) 트리
– 자식 노드가 최대 2개인 노드들로만 구성된 트리
– 전, 포화, 완전 이진트리
– 전(Full): 마지막 레벨까지 모든 형제 노드가 0개 또는 2개인 트리
– 완전(Complete): 마지막 레벨을 제외한 모든 형제 노드가 2개이고, 마지막 레벨의 노드는 왼쪽에서 오른쪽으로(순서대로) 채워져있는 트리
– 포화(Perfact): 마지막 레벨까지 모든 형제 노드가 2개인 트리
2)트리의 순회
1. 중위 순회(In-Order)
– 가장 좌측의 자식 노드로 시작하여 해당 노드의 부모 노드, 형제 노드 순으로 순회하는 방식
– 좌측 자식 노드 -> 부모 노드 -> 우측 자식 노드 순으로 순회
– G > D > H > B > E > A > F > C
2. 전위 순회(Pre-Order)
– 부모 노드로 시작하여 해당 노드의 자식 노드를 차례로 순회하는 방식
– 부모 노드 -> 좌측 자식 노드 -> 우측 자식 노드 순으로 순회
– A > B > D > G > H > E > C > F
3. 후위 순회(Post-Order)
– 가장 좌측의 자식 노드로 시작하여 해당 노드의 형제 노드, 부모 노드 순으로 순회
– 좌측 자식 노드 -> 우측 자식 노드 -> 부모 노드 순으로 순회
– G > H > D > E > B > F > C > A
3) 그래프(Graph)
1. 그래프의 구조
– 노드를 N:M의 구조로 연결하여 데이터 간의 관계를 표현하는 자료 구조
– 노드 간 2개 이상의 경로 설정이 가능한 네트워크 모델
– 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성
– 노드 간 순환이 가능하므로 루트 노드, 부모-자식 관계라는 개념이 없다
– 방향의 유무: 방향 그래프, 무방향 그래프
– 모든 노드의 연결 여부: 부분 그래프, 완전 그래프
– 특정 노드의 연결 여부: 연결 그래프, 비연결 그래프
– 순환 여부: 비순환 그래프, 순환 그래프
– 가중치 유무: 가중치 그래프, 비가중치 그래프
2. 그래프 용어
– 구성 요소는 정점과 정정과의 관계로 이루어 진다.
– 정점(Vertex): 트리의 Node와 같은 개념
– 간선(Edge, Branch): 정점을 연결하는 선
– 인접 정점(Adjacent Vertex): 간선에 의해 직접 연결된 정점
– 사이클(Cycle): 시작과 종료의 정점이 없는 경로
– 단순 경로(Simple Path): 반복되는 정점이 없는 경로
– 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
– 진입 차수(In Degree):
– 진출 차수(Out-Deree):
– 경로 길이(Path Length):