[자료구조] 이진 트리

1. 개념

각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리이다. 

 

2. 종류

1) 편향 이진 트리

노드들이 한쪽으로 편향돼 생성된 이진트리

이렇게 저장된 이진 트리는 탐색 속도가 저하되고 공간이 많이 낭비된다

2) 포화 이진 트리

트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리

3) 완전 이진 트리

마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리

4) 이진 탐색 트리

루트보다 작은 값은 왼쪽에 위치, 루트보다 큰 값은 오른쪽에 위치하도록 하여 노드를 저장

데이터를 효율적으로 저장하고 검색, 삭제할 수 있다.

 

3. 트리의 노드와 배열 인덱스의 상관관계

• 루트 노드 인덱스 = 1
• 부모 노드 인덱스 = 현재 노드 인덱스 / 2 (현재 노드가 루트가 아니어야 함)
• 왼쪽 자식 노드 인덱스 = 현재 노드 인덱스 * 2 (현재 노드 인덱스 * 2 가 노드개수보다 작거나 같아야 함)
• 오른쪽 자식 노드 인덱스 = 현재 노드 인덱스 * 2 + 1 (현재노드 인덱스 * 2 + 1 이 노드개수보다 작거나 같아야 함)

 

4. 순회

노드를 방문하는 방법

1) 전위 순회

루트 노드를 먼저 방문하고 왼쪽 서브 트리르 방문한 후 오른쪽 서브 트리를 방문

2) 중위 순회

왼쪽 서브 트리를 순회한 후 루트를 방문하고 오른쪽 서브 트리를 방문

3) 후위 순회

윈쪽 서브 트리를 순회하고 오른쪽 서브 트리를 순회한 후 마지막으로 루트를 방문

 

5. 구현

1) 1차원 배열

• 노드의 부모 자식 관계를 나타내기 위해 완전 이진 트리를 가정하고 배열의 크기를 결정해야 한다. 
• 완전 이진 트리나 포화 이진 트리에 사용하면 좋다.
• 완전 이진트리나 포화 이진 트리가 아니면 빈 공간이 많이 생겨 메모리 낭비가 발생할 수 있다.

2) 2차원 배열

• 일반적으로 완전 이진 트리에 사용되는 방법이다.
• 최대 노드의 수가 행이되고, 왼쪽 자식 오른쪽 자식을 가지니 열은 2가 된다.

 

6. 관련 문제

백준 1991

GitHub - Lee-Min-Jung/coding_test_practice