[알고리즘] Tree

괄괄이·2023년 9월 19일

알고리즘 이론

목록 보기

4/9

🎄 트리

사이클이 없는 연결 그래프

사이클 ? 한 지점에서 본인으로 돌아올 수 있다
연결 그래프 ? 모든 꼭지점이 서로 갈 수 있다

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

용어들

노드: 트리의 원소
간선: 노드를 연결하는 선, 부모와 자식 노드 연결
루트 노드: 트리의 시작 노드 
형제 노드: 같은 부모 노드의 자식 노드들
조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
자손 노드: 서브 트리에 있는 하위 레벨의 노드들

순회

돌아다니기(탐색)
트리의 노드들을 체계적으로 방문하는 것
트리는 순회 순서에 따라 나오는 값이 달라진다

전위순회 VLR(preorder)

부모노드 방문(처리) 후, 자식 노드를 좌,우 순서로 방문

1. 현재 노드 n을 방문하여 처리 V
2. 현재 노드 n의 왼쪽 서브트리로 이동 L
- 왼쪽 찍고 출력, 돌아오면서 왼쪽이 없으면 오른쪽 보고 찍어옴
3. 현재 노드 n의 오른쪽 서브트리로 이동 R
- 왼쪽 찍고 출력, 돌아오면서 왼쪽이 없으면 오른쪽 보고 찍어옴

중위순회 LVR(inorder)

왼쪽 자식, 부모노드, 오른쪽 자식노드 순으로 방문
왼쪽에서 리턴할 때 처리

1. 현재 노드 n을 방문, 처리는 x, 왼쪽 서브트리로 이동 L
2. 왼쪽으로 가고, 없으면 돌아와서 본인 찍다가 부모 노드 찍고 V
3. 오른쪽 서브트리로 가서 왼쪽 가다가 없으면 본인 찍으며 돌아옴 R

후위순회 LRV(postorder)

자식노드를 좌우 순서로 방문 후, 부모노드 방문
오른쪽에서 리턴할 때 처리

1. 왼쪽 서브트리 자식들부터 보고 L 
- 왼쪽, 오른쪽 보다가 값 없으면 돌아오면서 찍고
2. 오른쪽 서브트리 자식들 보고 R
- 값 없으면 돌아오면서 찍고
3. 부모 노드 본인에게 돌아옴 V

이진 트리

모든 자녀 노드가 둘 이하인 트리

모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 => 예측 가능
각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리(왼쪽/오른쪽 자식)
최대 2개이므로 자식이 없는 것도 이진트리에 포함
레벨 i에서 노드의 최대 개수는 2^i개
높이가 h인 이진트리가 가질 수 있는 노드 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1)-1)개

0. 이진 트리 종류
    - 완전 이진 트리
      → 마지막 레벨을 제외한 모든 레벨은 꽉 차있어야 한다 
      → 마지막 레벨 노드는 왼쪽부터 채워줘야한다
    - 포화 이진 트리
      → 모든 레벨이 꽉 차있다
1. 순회 방법 : 데이터를 어떻게 찾아갈 것인가? 무슨 데이터를 먼저 볼 것인가? 
2. 트리 저장 방법 : 순회를 구현하기 위해서 실제 코드에서 트리를 어떻게 저장했는가?

이진 트리 만들기


# 0. 이진 트리 저장
# 	  - 일차원 배열 저장
# 1. 연결 리스트로 저장 - 개발용
class TreeNode:
	def __init__(selft, value):
   	self.value = value
       self.left = None
       self.right = None
       
   # 삽입 함수
   def insert(self, childNode):
   	# 왼쪽 자식이 없을 경우 
       if not self.left:
       	self.left = childNode
           return 
       # 오른쪽 자식이 없을 경우
       if not self.right:
       	self.right = childNode
           return 
       
       return
       
	# 전위 순회
   def preorder(self):
   	# 아무 것도 없는 트리를 조회
   	if self != None:
   		print(self.value, end=' ')
           # 왼쪽이 있다면 왼쪽 자식 조회
           if self.left:
           	self.left.preorder()
           # 오른쪽이 있다면 오른쪽 자식 조회
           if self.right:
           	self.right.preorder()
       
arr = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6]
# 이진 트리 만들기
nodes = [TreeNode(i) for i in range(0, 14)]
for i in range(0, len(arr), 2):
	parentNode = arr[i]
    childNode = arr[i+1]
    nodes[parentNode].insert(nodes[childNode])

nodes[1].preorder()

이진 트리 - 인접 리스트

arr = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6]
# 이진 트리 만들기
nodes = [[] for _ in range(0, 14)]
for i in range(0, len(arr), 2):
	parentNode = arr[i]
    childNode = arr[i + 1]
    nodes[parentNode].append(childNode)
    
# 자식이 더 이상 없단 걸 표현하기 위해 None 삽입
for li in nodes:
	for _ in range(len(li), 2):
    	li.append(None)
        
# 전위 순회
def preorder(nodeNumber):
	if nodeNumber == None:
    	return
        
 	print(nodeNumber, end=' ')
    preorder(nodes[nodeNumber][0])
    preorder(nodes[nodeNumber][1])