[자료구조] 트리, 이진 트리, 이진 탐색 트리

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

트리와 관련된 용어

•  트리(tree)  : 한 개 이상의 노드로 이루어진 유한 집합.
  레벨(level) : 트리의 각 층에 번호를 매긴 것. 루트는 1이되고 한 층 내려갈수록 1씩 증가한다.
  높이(height) : 트리가 가지고 있는 최대 레벨
  forest : 트리들의 집합
• 노드(node) : 트리의 구성 요소
• 루트 노드(root node) : 트리에서 가장 높은 곳에 있는 노드
• 차수(degree)
  노드의 차수 : 노드가 가지고 있는 자식 노드의 개수 (단말 노드의 차수는 0)
  트리의 차수 : 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값
  
• 서브 트리 : 트리의 하위 트리구조
• 간선(edge) : 노드를 연결하는 선
• 부모 노드(parent node) : 자식 노드가 속해있는 노드
• 자식 노드(children node) : 부모 노드에 속한 부속 노드
• 형제 노드(sibling node) : 같은 부모 노드를 가지는 노드
• 조상 노드(ancestor node) : 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들을 의미
• 후손 노드(descendent node)
  - 임의의 노드 하위에 연결된 모든 노드들을 의미.
  - 어떤 노드의 서브 트리에 속하는 모든 노드들은 후손 노드이다.
• 단말 노드(terminal node, leaf node) : 자식 노드가 없는 노드
  비 단말 노드(nonterminal node) : 단말 노드의 반대
•  결정 트리(decision tree)  : 의사 결정 구조를 표현하는 방법 중 하나

 

 

 

이진트리(binary tree)

• 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합
• 이진트리의 서브 트리들은 모두 이진트리여야 한다. (서브 트리는 공집합일 수 있다.)
• 모든 노드가 2개의 서브 트리를 가지고 있는 트리이다. (서브 트리는 공집합일 수 있다.)
• 최대 2개까지의 자식 노드가 존재할 수 있다 (== 모든 노드의 차수가 2 이하이다.)
• 서브 트리 간의 순서가 존재(왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별된다.)

 

 

이진트리의 성질

• 부모와 자식 간에는 하나의 간선만 존재
• 노드가 n개인 이진트리의 간선 개수 : $n-1$(부모 노드는 항상 1개이기 때문)
• 높이가 h인 이진트리의 노드 개수 : 최소 h개 ~ 최대 $2^h - 1$개
• 레벨 i에서의 노드 최대 개수 : $2^{i - 1}$
• 노드가 n개인 이진트리의 높이 : 최소 $log_2(n+1)$ ~ 최대 n

 

 

이진트리의 종류

1. 포화 이진트리 (full binary tree)
   - 트리의 각 레벨에 노드가 꽉 차있는 이진트리 (== 노드의 개수가 항상 $2^k - 1$개)
   - 노드에 번호를 부여할 때는 (같은 레벨에서) 왼쪽에서 오른쪽으로 붙인다.
2. 완전 이진트리(complete binary tree)
   : 높이가 k일 때, 레벨 1부터 k -1까지는 노드가 모두 채워져 있고 마지막 레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리(중간에 비어있으면 안 됨)
   - 포화 이진트리는 항상 완전 이진트리
   - 포화 이진트리와 노드 번호 부여 방식은 같다.
3. 기타 이진트리

 

 

이진트리 구현

1. 배열 표현법
   : 노드의 최대 개수인 $2^k -1$개의 공간을 할당한 뒤 노드들을 저장
   - 기억공간 낭비가 심함
2. 포인터 이용 : 포인터를 이용해서 왼쪽 노드와 오른쪽 노드를 저장한다. 
   

   typedef struct TreeNode{
       int data;
       struct TreeNode *left;
       struct TreeNode *right;
   } TreeNode;​

 

 

이진트리 순회

       순회(traversal)  : 이진트리에 속한 모든 노드를 한 번씩 방문하는 것

• 전위 순회(preorder traversal) : 루트 노드를 가장 먼저 방문 (루트 → 왼쪽 서브 트리 → 오른쪽 서브 트리)
• 중위 순회(inorder traversal) : 루트 노드를 2번째로 방문 (왼쪽 서브 트리 → 루트 → 오른쪽 서브 트리)
• 후위 순회(postorder traversal) : 루트 노드를 서브 트리 방문 후에 방문 (왼쪽 서브트리 → 오른쪽 서브트리 → 루트)
• 레벨 순회(level order)
  - 각 노드를 레벨 순으로 방문
  - 같은 레벨일 경우에는 좌, 우로 방문

 

 

트리 응용

• 디렉터리 용량 계산 : 후위 순회(하위 디렉터리 용량을 알아야 현재 디렉터리 용량을 계산할 수 있음)
• 수식 트리(expression tree) 처리 : 후위 순회

 

 

 

 

 

이진 탐색 트리(binary search tree)

  : 이진트리 기반의 탐색을 위한 자료 구조

• 이진 탐색 트리의 정의
  - 모든 원소의 키는 유일한 키를 가진다.
  - 왼쪽 서브 트리 키들은 루트 키보다 작다.
  - 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
  - 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
• 탐색과 관련된 용어
  탐색 : 레코드의 집합에서 특정 레코드를 찾아내는 작업
  테이블(table) : 레코드들의 집합
  레코드(record) : 하나 이상의 필드(field)로 구성
  주요 키(primary key) : 레코드를 구별할 수 있는 값 (중복되지 않은 고유한 값)

 

 

이진 탐색 트리의 시간 복잡도

• 탐색, 삽입 삭제 연산의 시간 복잡도 : (트리의 높이가 h일때) $O(h)$
• 노드가 n개인 이진 탐색 트리 연산
  평균적인 경우(좌우 서브 트리가 균형을 이루는 경우) 시간복잡도 : $O(log_2n)$
  최악의 경우(한쪽으로 치우치는 경우) : 선형 탐색과 같이 $O(n)$
  → 최악의 경우를 방지하기 위해 트리의 높이를 $log_2n$으로 한정시키는 방식을 사용한다...