14장. 트리

트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로 루트값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.

• 재귀로 정의된 자기참조 자료구조
• 트리는 자식도 트리고 그 자식도 트리다 → 여러개의 트리가 쌓아 올려져 큰 트리가 된다.
• 흔히 서브트리로 구성된다고 표현한다.

트리의 각 명칭

• 레벨은 0부터 시작한다.

• 트리는 항상 단방향이기 때문에, 간선의 화살표는 생략 가능하다.

Q. 트리와 그래프의 차이는 무엇입니까?

A. “트리는 순환구조를 갖지 않는 그래프입니다”

• 트리는 하나의 부모 노드를 갖는다. 루트 또한 하나여야 한다.

이진 트리

각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리)라고 한다.

• 여기서 m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리(Binary Tree)라고 구분해서 부른다.

• 이진 트리는 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해서 훨씬 간결할 뿐만 아니라 여러가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니면 대부분 이진 트리를 일컫는다.

• 이진 트리의 유형



• 정 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
• 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채 워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
• 포화 이진 트리(Perfect Binary Tree): 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로, 가장 완벽한Perfed 유 형의 트리다.

문제 리스트

이진 탐색 트리

정렬된 트리로, 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드가, 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 노드들로 이루어져 있는 트리이다

• 탐색시 시간 복잡도가 O(log n)이다.

• 비효율적으로 구성된 경우, 연결리스트와 다르지 않게 O(n)이 소요된다 (1-2-3-4-5-6-7)

• 이런 트리는 균형을 맞춰줄 필요가 있으며 이를 ‘자가 균형 이진 탐색 트리’라고 한다.

자가 균형 이진 탐색 트리

자가 균형(또는 높이 균형) 이진 탐색 트리는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리다.

• 자가 균형 이진 탐색 트리는 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다. 즉 높이를 가능한 한 낮게 유지하는 것이 중요하다는 이야기다.

• 루트의 높이로 불균형과 균형을 구분할 수 있다.

• 자가 균형 이진 탐색 트리의 형태
• AVL 트리
• 레드-블랙 트리

트리 순회

트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한번 방문하는 과정을 말한다.

• 전위 순회(Pre-Order) → NLR

def preorder(node):
	if node is NOne:
		return
	print(node.val)
	preorder(node.left)
	preorder(node.right)

• 중위 순회(In-Order) → LNR

def inorder(node):
	if node is None:
		return
	inorder(node.left)
	print(node.val)
	inorder(node.right)

• 후위 순회(Post-Order) → LRN

def postorder(node):
	if node is None:
		return
	postorder(node.left)
	postorder(node.right)
	print(node.val)

문제 리스트