트리
트리는 방향 그래프의 일종으로 정점(Node)을 가리키는 간선(Edge)이 하나 밖에 없는 구조를 가지고 있다.
트리 구조 용어
루트 : 트리의 가장 위쪽 노드
리프 : 트리의 가장 아래쪽 노드 = 단말 노드 terminal node = 외부 노드 external node
물리적으로 가장 밑에 위치한다는 의미가 아닌, 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다.
비단말 노드 : 리프를 제외한 노드 (루트 포함) = 내부 노드 internal node
형제 : 부모가 같은 노드
레벨 : 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것
차수 : 각 노드가 갖는 자식의 수
높이 : 리프 레벨의 최댓값
트리의 특징
- 루트 정점을 제외한 모든 정점은 하나의 부모 정점을 가진다.
- 정점이 n개인 트리는 n-1개의 간선을 가진다.
- 루트에서 특정 정점으로 가는 경로는 유일하다.
그래프와 트리 비교
트리의 검색
너비 우선 검색 (BFS)
낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨의 검색을 마치면 다음 레벨로 내려간다.
깊이 우선 검색 (DFS)
리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법이다. 리프에 도달해 더 이상 검색할 곳이 없으면 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.
❗노드를 지나가는 것과 방문하는 것은 다른 개념이다.
-
전위 순회
노드 방문→왼쪽 자식→오른쪽 자식 -
중위 순회
왼쪽 자식→노드 방문→오른쪽 자식 -
후위 순회
왼쪽 자식→오른쪽 자식→노드 방문
이진 트리
이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리로 왼쪽 자식과 오른쪽 자식을 구분한다.
완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차 있다.
마지막 레벨에 한해서 왼쪽부터 오른쪽으로 노드를 채우되 반드시 끝까지 채우지 않아도 된다.
마지막 레벨도 노드가 가득 찬 트리를 포화 이진 트리라고 한다.
한 방향으로만 정점이 이어진 트리를 편향 트리라고 한다.
