[자료구조] 트리(Tree) 자료구조

 

리스트, 스택, 큐 등은 자료들이 직선과 같이 나열되어 있는 선형 자료 구조(linear data structure)이다. 이런 자료구조는 계층 관계를 표현하기에 적합하지 않다. 트리(tree)는 조상과 자손, 전체와 부분, 컴퓨터의 디렉터리 구조 등의 계층적인 자료를 표현하는데 이용되는 자료구조이다. 

 

트리(Tree) 자료구조

💡 트리와 관련된 용어

• 노드(node): 트리의 구성 요소
• 루트(root) 노드: 계층 구조에서 가장 높은 곳에 있는 노드
• 서브 트리(subtree): 트리에서 루트 노드를 제외한 노드들
• 간선(edge): 루트와 서브 트리를 연결하는 선
• 단말 노드(terminal node/leaf node): 자식 노드가 없는 노드
• 비단말 노드(nonterminal node): 자식 노드가 있는 노드
• 차수(degree): 어떤 노드가 가지고 있는 자식 노드의 개수
• 트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수
• 레벨(level): 트리의 각 층에 번호를 매긴 것 ({A(루트)} 레벨 1, {B, C, D}의 레벨 2, ...)
• 트리의 높이(height): 트리가 가지고 있는 최대 레벨

 

 

 

💡 이진 트리(Binary Tree)

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다. 이때 서브 트리는 공집합일 수 있다. 

 

<이진 트리의 순환적 정의>

1. 공집합이거나
2. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서버 트리들은 모두 이진 트리여야 한다. 

 

 

<이진 트리의 성질>

• n개의 노드를 가진 이진 트리는 (n - 1) 개의 간선을 가진다. 
  - 이진 트리에서 루트를 제외한 노드는 하나의 부모 노드만을 가짐
• 높이가 h인 이진 트리의 노드 개수: 최소 h개 / 최대 2^h - 1개
  - 한 레벨에 적어도 하나의 노드가 존재해야 함
  - 하나의 노드는 최대 2개의 자식을 가질 수 있음
  - 레벨 i에서 최대 노드 개수: 2^(i - 1)
• n개의 노드를 가진 이진 트리의 높이: 최대 n / 최소 ⎡log(n + 1)⎤
  - 한 레벨에 적어도 하나의 노드가 존재해야 함
  - 높이 h의 이진 트리가 가질 수 있는 최댓값 n <= 2^h - 1에서 양변에 log를 취하면 ⎡log(n + 1)⎤ <= h

 

 

<이진 트리의 분류>

• 포화 이진 트리(Full Binary Tree)
  - 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리
  - 높이가 k인 포화 이진 트리의 노드 개수: 2^k - 1
• 완전 이진 트리(Complete Binary Tree)
  - 높이가 k일 때, 레벨 1부터 k - 1까지는 노드가 모두 채워져 있고 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워진 이진 트리
  - 포화 이진 트리는 항상 완전 이진 트리이지만 그 역은 항상 성립하지는 않음

 

 

 

💡 이진 트리의 순회(Traversal)

이진 트리의 순회란 이진 트리에 속하는 모든 노드들을 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 말한다. 이진 트리의 순회 방법은 크게 3가지로 나눌 수 있다. 

• 전위 순회(preorder traversal): VLR
• 중위 순회(inorder traversal): LVR
• 후위 순회(postorder traversal): LRV

 

 

<중위 순회 알고리즘>

def inorder(root):
	if root:
    	inorder(root.left)	# 왼쪽 서브 트리 순회
        print(root.data)	# 노드 방문
        inorder(root.right)	# 오른쪽 서브 트리 순회

전위 순회와 후위 순회도 비슷한 방법으로 재귀적으로 구현할 수 있다. 

 

 

이밖에도 레벨 순회(level order) 방법으로 이진 트리를 순회할 수 있다. 레벨 순회는 각 노드를 레벨 순으로 검사하는 방법이다. 동일한 레벨의 경우에는 좌에서 우로 방문한다. 위 3가지 순회 방법은 스택(재귀 호출)을 사용했지만, 레벨 순회는 큐를 사용하는 순회 방법이다. 

 

<레벨 순회 알고리즘>

from collections import deque

def level_order(root):
	queue = deque.([root])
    while queue:
    	root = queue.popleft()
        if root:
        	print(root.data)	 # 노드 방문
            if root.left:
            	queue.append(root.left)	 # 왼쪽 서브 트리 큐에 삽입
            if root.right:
            	queue.append(root.right) # 오른쪽 서브 트리 큐에 삽입

참고: 트리는 그래프와 달리 사이클이 없기 때문에 BFS와 달리 visited를 저장할 필요가 없음

 

 

 

💡 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 이진 트리 기반의 탐색을 위한 자료구조이다. 이진 탐색 트리의 정의는 다음과 같다. 

• 모든 노드의 키는 유일하다
• 왼쪽 서브 트리의 키들은 루트의 키보다 작다
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다

 

 

<이진 탐색 트리의 search>

이진 탐색 트리에서 특정 키 값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색 키 값과 현재의 루트 노드의 키 값을 비교한다. 비교 결과는 다음 3가지로 나누어진다. 

• target == root: 탐색 종료
• target < root: 루트의 왼쪽 자식을 기준으로 재탐색
• target > root: 루트의 오른쪽 자식을 기준으로 재탐색

 

<이진 탐색 트리의 insert>

1. 트리 T에서 삽입할 키 값 x에 대한 탐색 수행
2. 탐색이 실패하면 탐색이 끝난 지점에 노드 x 삽입

이진 탐색 트리의 키 값들은 유일해야 하기 때문에 x값에 대한 탐색에 성공했다면 x를 중복 삽입하지 못한다. 

 

 

<이진 탐색 트리의 delete>

노드를 삭제하기 위해서는 먼저 노드를 탐색해야 한다. 노드를 탐색한 다음, 다음 3가지 경우를 고려해야 한다. 

1. 삭제하려는 노드 x가 단말 노드일 경우
   - 단말 노드 x만 삭제
2. 삭제하려는 노드 x가 하나의 서브 트리(왼쪽 또는 오른쪽)를 가진 경우
   - 노드 x는 삭제하고, 서브 트리를 x의 부모 노드를 가리키게 함
3. 삭제하려는 노드 x가 두 개의 서브 트리를 가진 경우
   - x를 삭제하고 x의 자리에 왼쪽 서브 트리에서 가장 큰 값 또는 오른쪽 서브 트리에서 가장 작은 값을 넣음

 

 

<시간 복잡도>

이진 탐색 트리에서 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때, O(h)이다. 따라서 n개의 노드를 가지는 이진 탐색 트리의 경우 균형 잡힌 이진 트리의 높이는⎡log(n)⎤이므로 평균의 경우 시간 복잡도는 O(log(n))이다. 

하지만 만약 한쪽으로 치우치는 경사지는 이진 트리일 경우에는 트리의 높이가 n이 되고 이때의 탐색, 삭제 , 삽입 시간은 O(n)으로 선형 탐색과 유사하다. 

 

 

 

Reference

• C언어로 쉽게 풀어쓴 자료 구조
• http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html