[자료구조] 트리

용어정리

- 서브 트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리

- 단말 노드 : 자식이 없는 노드( leaf node)라고도 불림

- 비단말 노드 : 적어도 하나의 자식을 갖는 노드

- 레벨 : 트리의 각층의 번호

- 높이 : 트리의 최대 레벨 h

- 차수 : 노드가 가지고 있는 자식 노드의 개수

 

이진 트리

: 모든 노드의 차수가 2 이하가 되어 구현하기에 편리하다는 장점

특징

1. 노드의 개수가 n개이면 간선의 개수는 n-1개

2. 높이가 h인 이진트리의 경우, 최소 h개의 노드, 최대 2h-1개의 노드를 갖는다.

3. n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 ┌log₂(n+1)​┐

-> 높이가 h일 때(노드의 개수 h) 최대 2^h-1개의 노드

따라서 2^h = logn(n+1)

 

만약 h가 7일때 최대 높이는 노드를 한쪽 서브트리로 하나씩 계속 나열하는 경우이다. 이 경우일 때 레벨이 많아지므로 데이터가 매우 많아질 경우가 생김. (2^h = n+1)

이때 로그를 취하면 데이터를 효과적으로 줄일 수 있다(이진트리, logn(n+1))

 

 

이진트리의 표현

- 배열 표현법 : 모든 이진트리를 포화이진트리라고 가정했을 때, 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

- 링크 표현법 : 포인터를 이용하여 자식노드<-부모노드

 

 

이진트리의 순회

순회 : 트리의 노드들을 체계적으로 방문

3가지(V : 루트, L : 왼쪽 서브트리, R : 오른쪽 서브트리)

1. 전위순회(VLR) : 자손노드보다 루트노드를 먼저 방문한다

2. 중위순회(LVR) : 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문한다

3. 후위순회(LRV) : 루트노드보다 자손을 먼저 방문한다.

4. 층별순회 : 위쪽 노드들 부터 순서대로 아래로 방문한다.

 

수식트리계산

- 후위순회를 사용한다

ex) (3*2) + (5X6)

후위순회를 사용하면 >> 3 2 * 5 6 X +

 

=> evaluate(exp)

 

if exp is 리프노드

then return exp->data;

 

else x<-evaluate(exp->left); //x는 왼쪽 자식 계산 후 저장(숫자)

y<-evaluate(exp->right); //y는 오른쪽 자식 계산 후 저장(숫자)

op<-exp->data; //본인(연산자)

 

return(x op y); //리턴 값 (숫자)

 

이진트리연산: 노드 개수

: 각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1(본인)을 더하여 반환

 

=> int get_node_count(TreeNode *node)

{

int count = 0;

if(node != NULL)

count = 1 + get_node_count(node->left) + get_node_count(node->right);    ...1은 본인을 나타냄(1 + L + R)

 

return count;

}

 

이진트리연산: 높이

: 서브트리에 대해 순환호출을 하고 서브트리들의 반환값 중 에서 최대값에 1을 더해서 반환.

=> int get_height(TreeNode *node)

{

int height = 0;

if(node != NULL) {

height = 1 + max(get_height(node->left), get_height(node->right));

 

return height;

}

 

이진탐색트리(자료구조)

• key(왼쪽서브트리) <= key(루트노드) <= key(오른쪽서브트리)
• 중위순회로 이진탐색 >> 오름차순으로 정렬

탐색연산설명

- 종료조건 : 비교한 결과가 같으면 끝남

- 주어진 키 값 < 루트 노드의 키값 : 이 루트 노드의 왼쪽 자식을 기준으로 다시 탐색

- 주어진 키 값 > 루트 노드의 키값 : 이 루트 노드의 오른쪽 자식을 기준으로 다시 탐색

 

이진트리에서 노드 삽입/삭제

1. 삽입

- 탐색 후 탐색이 실패한 위치에 노드 삽입

 

2. 삭제 ***

3가지 경우

(1) 삭제하려는 노드가 단말 노드일 경우

: 단말 노드의 부모 노드를 찾아 연결을 끊는다

 

(2) 삭제하려는 노드가 하나의 서브트리만 가지는 경우

: 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우에는 노드는 삭제하고 서브 트리는 부모 노드에 붙여준다.

 

(3) 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

: 삭제노드와 가장 비슷한 값을 가진 노드를 삭제노드 위치로 가져온다. -> 왼쪽 서브트리에서 제일 큰 값( 삽입 시에 작은 노드가 왼쪽으로 옮겨가는 서브트리의 성질)과 오른쪽 서브트리에서 제일 작은 값( 삽입 시에 큰 노드가 오른쪽으로 옮겨가는 서브트리의 성질)을 비교하여 두 노드 중 큰 노드를 삭제노드 위치로 가져오는 방법을 채택.

>> 틀린방법 ㅡㅡ;;

BST 삭제 과정에서 **"왼쪽 서브트리에서 가장 큰 값"**(Inorder Predecessor)과 **"오른쪽 서브트리에서 가장 작은 값"**(Inorder Successor) 중 하나를 선택하여 삭제된 노드를 대체할 수 있습니다. 하지만 둘 중 하나를 선택해야 하며, **두 값을 비교해서 더 큰 노드를 대체 노드로 선택하는 것은 BST 규칙에 어긋납니다.**

### 이유:
BST의 속성은 왼쪽 서브트리는 루트보다 작고, 오른쪽 서브트리는 루트보다 커야 합니다.  
따라서 대체 노드는 다음 중 하나여야만 합니다:
1. **왼쪽 서브트리에서 가장 큰 값** (루트보다 작음).  
2. **오른쪽 서브트리에서 가장 작은 값** (루트보다 큼).  

만약 "더 큰 값"을 선택한다면, 트리의 순서 속성이 깨질 위험이 있습니다.

### 예시:
#### 초기 트리:
```
              12
           /      \
         5         15
       /   \
     3      7
```

#### 잘못된 대체 방식:
- **5를 삭제**하고 "7과 3 중 더 큰 값(=7)"을 선택해 대체:
```
              12
           /      \
         7         15
       /   
     3    
```
위 트리는 `3 < 7 < 12`라는 BST 속성을 유지하므로 운 좋게 맞아떨어졌지만, 이 방법은 일반적으로 BST를 보장하지 않습니다. 대체로 **왼쪽 서브트리 또는 오른쪽 서브트리 중 하나를 일관되게 선택하는 것이 중요**합니다.

#### 올바른 방법:
1. **왼쪽 서브트리에서 가장 큰 값(=3)**으로 대체하거나,  
2. **오른쪽 서브트리에서 가장 작은 값(=7)**으로 대체.  
위 두 방법 중 하나만 선택해야 합니다.

 

 

이진탐색트리의 성능

- 이진탐색트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 h에 비례한다 (탐색 시간 log2​n ∝ h, 밑이2이고 진수가 n인 로그)

 

- 경우

• 최선의 경우 : 이진트리가 균형적으로 생성되어 있는 경우 h = log2n
• 최악의 경우 : 이진트리가 한쪽으로 치우친 경사이진트리의 경우 h = n (순차탐색과 시간복잡도가 같다)