(자료구조 & 알고리즘 정리) 트리(Tree) (2023.06.13)

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. 트리 순회

(Java)백준 1991. 트리 순회