1. 트리 개념
1) 비선형 자료구조
2) 원소들 간에 1:n관계를 가지는 자료구조
3) 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 자료구조 => 루트노드만 접근할 수 있으면 트리의 모든 노드들을 다 탐색할 수 있게 됨.
4) 용어
- 노드 : 트리의 원소
- 트리는 한 개 이상의 노드로 이루어진 유한집합이며 다음 조건을 만족
- 노드 중 최상위 노드를 루트라 함
- 나머지 노드들은 분리집합으로 분리 가능
- 위의 분리집합들은 다시 하나의 트리가 됨(재귀적 정의), 루트의 부트리(subtree)라고 함
- 간선 : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
- 루트 노드 : 트리의 시작 노드인 최상위 노드(트리 전체 탐색 시 루트노드부터 탐색)
- 형제 노드 : 같은 부모 노드의 자식 노드들
- 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
- 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
- 자손 노드 : 서브 트리에 있는 하위 레벨 노드들
- 차수
- 노드의 차수 : 노드에 연결된 자식 노드의 수
- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
- 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드
- 높이
- 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
- 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레
2. 이진트리
1) 개념
- 차수가 2인 트리
- 각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리
- 모든 노드들이 최대 3개의 서브트리를 가짐
- 높이가 i인 노드의 최대 개수는 2^i 개
- 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 h+1, 최대 개수는 2^(h+1) -1 ( 4)의 등비수열 합 고려해보면 계산 가능)
2) 포화 이진트리
- 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
- 높이가 h일 때, 최대 노드 개수인 2^(h+1) -1 의 노드를 가진 이진 트리
- 루트를 1번으로 하여 정해진 위치에 대한 노드 번호를 가짐
3) 완전 이진트리
- 높이가 h이고 노드 수가 n개일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진트리
- 포화 이진트리처럼 각각의 레벨에 노드가 포화상태로 차 있을 필욘 없지만 마지막 번호인 노드까지 빈자리가 없어야 함.
4) 편향 이진 ㅌ릐
- 높이 h에 대한 최소 개수의 노드를 가지며 한쪽 방향으로만 자식 노드를 가진 이진 트리
- 왼쪽 편향 이진트리
- 오른쪽 편향 이진트리
3. 이진트리의 구현
1) 배열을 이용한 이진트리의 구현
- 이진트리에 각 노드 번호를 부여
- 루트의 번호를 1로 함
- 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n 부터 (2^n)-1까지 번호를 차례로 부여
- 높이가 h인 이진트리를 위한 배열의 크기는 2^(h+1) +1
- 노드 번호의 성질
- 노드 번호가 i인 노드의 부모 노드 번호 : i/2
- 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 2*i
- 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 2*i +1
- 레벨 n인 노드의 시작번호 : 2^n
- 유의할 점
- 편향 이진트리의 경우, 비어있는 공간이 많아져 메모리 낭비
- 편향 이진트리 혹은 중간에 빈 노드 자리가 많을 경우 배열을 활용한 구현 방법은 좋지 않음
- 이중 연결리스트 활용하기
2) 클래스 생성을 통한 이진트리의 구현
- Node클래스와 Tree클래스 생성
- Node 클래스
- 왼쪽 자식과 오른쪽 자식을 나타내는 필드 생성
- 자기 자신의 값을 나타내는 필드 생성
- Tree클래스
- Root 노드를 나타내는 필드 생성
- Tree를 위해 필요한 메서드 생성(add, search, delete 등등)
4. 비선형 자료구조 완전 탐색
1) 비선형 자료구조인 트리, 그래프의 각 노드를 중복되지 않게 전부 탐색하는 것은 선형 자료구조와 달리 선후 연결관계를 알 수 없으므로 BFS 또는 DFS를 활용하여 탐색
2) BFS
- 너비 우선 탐색
- 루트 노드의 자식 노드들을 모두 차례로 방문한 후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식
- 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행 => 선입선출 형태인 큐 활용
- 코드
BFS() {
Queue<자료형> queue = new LinkedList<>();
queue.add(rootNode);
while(!queue.isEmpty){ // queue가 비어있지 않는 동안 반복
Node node = queue.poll();
for(children of node){ //뽑은 node와 연결된 자식 노드들을 모두 queue에 넣기
queue.add(children);
}
}
}
3) DFS
- 깊이 우선 탐색
- 루트 노드에서 출발하여 한 방향으로 갈 수 잇는 경로가 있는 곳가지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 돌아와서 다른 방향의 노드로 탐색을 반복하여 결국 모든 노드를 방문하는 순환 방법
- 가장 마지막에 만났던 갈림길의 노드로 되돌아 가서 다시 깊치 우선 탐색 반복해야 하므로, 재귀적으로 구현하거나 후입 선출 구조의 스택 사용해서 구현
- 코드
boolean[] visited = new boolean[N]; //N : 노드의 개수
DFS(int n) {
visited[n] = true; //n번 노드 방문처리
for( c of n) { //n과 연결된 자식 모두에 대해서
DFS(c);
}
}
5. 힙
1) 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
2) 최대 힙
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 큰 노드
3) 최소 힙
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 작은 노드
4) 힙 연산
- 삽입 : 부모 노드와 비교하여 자리 바꾸기
- 삭제
- 힙에서는 루트 노드의 원소만을 삭제
- 루트 노드의 원소를 삭제하여 반환
- 힙의 종류에 따라 최대값 또는 최소값 구할 수 있
6. 문제
1) 백준1991 트리순회 : 2023.06.20 - [Learning-log/Algorithm 문풀] - (Java)백준 1991. 트리 순회
'Learning-log -CS > Data Structure & Algorithm' 카테고리의 다른 글
(자료구조 & 알고리즘 정리) 분할정복 (2023.06.15) (0) | 2023.06.15 |
---|---|
(자료구조 & 알고리즘 정리) 완전 탐색, 백트래킹 (2023.06.14) (0) | 2023.06.14 |
(자료구조 & 알고리즘 정리) 스택, 큐, LinkedList (2023.06.05) (0) | 2023.06.05 |
(자료구조 & 알고리즘 정리) 재귀, 완전탐색, 순열, 조합, 부분집합 정리(2023.06.04) (0) | 2023.06.05 |
알고리즘 - 이분탐색(Binary Search)과 매개변수 탐색(Parameter Search) (Java, Python) (0) | 2023.04.20 |