[SWEA] [파이썬 SW 문제해결 기초] 6. Tree

[Tree]

- 비선형 구조 + 원소들 간에 1:n 관계를 가지는 자료구조
- 원소들 간에 계층 관계를 가지는 계층형 자료구조
- 상위 원소에서 하위 원소로 내려가면서 확장되는 Tree 모양의 구조
- 한 개 이상의 노드로 이루어진 유한 집합
  ⇒ 루트(Root): 노드 중 최상위 노드
  ⇒ 나머지 노드들: n(>=0)개의 분리 집합 T1, ... ,TN으로 분리될 수 있음
- T1, ..., TN은 각각 하나의 트리가 되며(재귀적 정의), 루트의 서브트리라고 함

노드(node): 트리의 원소
간선(edge): 부모 노드와 자식 노드를 연결

구성요소	설명
루트 노드 (Root node)	트리의 시작 노드
형제 노드 (Sibling node)	같은 부모 노드의 자식 노드들
조상 노드 (Ancestor node)	간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
서브트리 (SubTree)	부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
자손 노드 (Descendent node)	서브트리에 있는 하위 레벨의 노드들

※ 차수(degree)
- 의미: 노드에 연결된 자식 노드의 수
- 트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값
- 단말 노드(리프 노드): 차수가 0인 노드 / 자식 노드가 없는 노드※ 높이
- 노드의 높이: 노드의 레벨
- 트리의 높이: 트리에 있는 노드의 높이 중에서 가장 큰 값 (= 최대 레벨)

 

[Binary Tree]

- 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
- 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
- 레벨 i에서의 노드의 최대 개수: 2^i개
- 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수: h+1개 / 최대 개수: 2^(h+1)-1개

※ 포화 이진 트리 (Full Binary Tree)
- 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
- 최대의 노드 개수인 (2^(h+1)-1)의 노드를 가진 이진 트리
- 루트를 1번으로 하여 2^(h+1)-1까지 정해진 위치에 대한 노드 번호를 가짐

※ 완전 이진 트리 (Complete Binary Tree)
- 높이가 h이고 노드 수가 n개일 때 (단 2^h <= n < 2^(h+1)-1), Full 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

※ 편향 이진 트리 (Skewed Binary Tree)
- 높이 h에 대한 최소 개수의 노드를 가지면서 한 쪽 방향의 자식 노드만을 가진 이진 트리

※ 순회(Traversal)
- 트리의 각 노드를 중복되지 않게 전부 방문하는 것
- 트리는 비선형 구조 => 선후 연결 관계를 알 수 없으므로 특별한 방법 필요

이름	방법
전위 순회 (Preorder traversal)	Root → Left → Right 자손 노드보다 루트 노드를 먼저 방문
중위 순회 (Inorder traversal)	Left → Root → Right 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
후위 순회 (Postorder traversal)	Left → Right → Root 루트 노드보다 자손을 먼저 방문

# 전위 순회
def preorder_traverse(T):
  if T:				# T is not None
    visit(T)			# print(T.item)
    preorder_traverse(T.left)
    preorder_traverse(T.right)
    

# 중위 순회
def inorder_traverse(T):
  if T:				# T is not None
    inorder_traverse(T.left)
    visit(T)			# print(T.item)
    inorder_traverse(T.right)


# 후위 순회
def postorder_traverse(T):
  if T:				# T is not None
    postorder_traverse(T.left)
    postorder_traverse(T.right)
    visit(T)			# print(T.item)

 

 

[Expression Tree]

※ 리스트를 이용한 이진 트리의 표현
1) 이진 트리에 각 노드 번호를 다음과 같이 부여
2) 루트의 번호를 1로 함
3) 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2n부터 2^(n+1)-1까지 번호를 차례로 부여 
4) 노드 번호를 리스트의 인덱스로 사용
5) 높이가 h인 이진 트리를 위한 리스트 크기는?
- 레벨 i의 최대 노드 수: 2^i

※ 노드 번호의 성질?
1) 노드 번호가 i인 노드의 부모 노드 번호: i // 2
2) 노드 번호가 i인 노드의 왼쪽 자식의 노드 번호: 2 * i
3) 노드 번호가 i인 노드의 오른쪽 자식의 노드 번호: 2 * i + 1 

 

[Binary Search Tree]

- 탐색 작업을 효율적으로 하기 위한 자료구조
- 모든 원소는 서로 다른 유일한 키를 가짐
- key(왼쪽 서브트리): 루트보다 작은 값 < key(루트 노드) < key(오른쪽 서브트리): 루트보다 큰 값
- 왼쪽 서브트리, 오른쪽 서브트리 => 이진 탐색 트리
- 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음

※ 탐색 연산
1) 루트에서 시작
2) 탐색할 키값 x를 루트 노드의 키값과 비교
- 키값 x = 루트 노드의 키값: 원하는 원소를 찾았으므로 탐색 연산 성공
- 키값 x < 루트 노드의 키값: 루트 노드의 왼쪽 서브트리에 대해서 탐색 연산 수행
- 키값 x > 루트 노드의 키값: 루트 노드의 오른쪽 서브트리에 대해서 탐색 연산 수행 
3) 서브트리에 대해서 순환적으로 탐색 연산을 반복※ 삽입 연산
1) 먼저 탐색 연산을 수행
- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없음 => 같은 원소가 트리에 있는지 탐색하여 확인
- 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 됨
2) 탐색 실패한 위치에 원소를 삽입※ BST의 성능
- 탐색, 삽입, 삭제 시간: 트리의 높이에 좌우됨 => O(h)
- 평균의 경우: 이진 트리가 균형적으로 생성되어 있는 경우 => O(log n)
- 최악의 경우: 한쪽으로 치우친 경사 이진 트리의 경우 => O(n)

 

[Heap]

- 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 가장 작은 노드를 찾기 위해 만든 자료구조

최대 힙 (Max heap)	최소 힙 (Min heap)
키값이 가장 큰 노드를 찾기 위한 완전 이진 트리 부모 노드의 키값 > 자식 노드의 키값 루트 노드: 키값이 가장 큰 노드	키값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키값 < 자식 노드의 키값 루트 노드: 키값이 가장 작은 노드

삽입 연산: 비어 있는 곳에 임시로 삽입하고 부모 노드와 비교해가며 위치 바꾸기
삭제 연산: 루트 노드의 원소 삭제 → 마지막 노드를 루트 노드 위치로 이동 → 자식 노드와 비교해가며 위치 바꾸기