[자료구조/알고리즘] 4. 트리
대표적인 자료구조
- 선형 구조 : 스택, 큐
- 자료가 순서를 가지고 연속됨
- 비선형 구조 : 트리, 그래프
- 선형 구조에 해당하지 않는 자료구조
💥 먼저, 그래프(Graph)
- 트리는 그래프의 특수한 형태 중 하나이다. 즉, 트리는 그래프라고 할 수 있다.
- 그러므로 그래프부터 무엇인지 살펴보도록 하자.
- 위 그림은 동그라미와 선으로 이루어져 있다.
- 여기서 동그라미는 정점, 선은 간선이다.
- 정점 : 자료, 상태 등 뭔가를 담고 있는 것 (노드라고도 한다)
- 간선 : 정점 간의 관계를 나타냄
- 어떤 정점에서 간선을 통해 다르 정점으로 이동할 수 있다.
- 어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점을
경로
라고 한다.
- 그래프의 간선은 방향이 있을 수도, 없을 수도 있다.
- 방향이 있는 간선을 가진 그래프는 유향 그래프라고 한다.
- 어떤 정점에서 출발해서 자기 자신으로 돌아오는 경로가 있을 수 있다.
- 처음 시작한 정점으로 다시 돌아오는 경로를
사이클
이라고 한다.
- 3 - 5 - 6 - 3 :
사이클
💥 이제, 트리(Tree)
- 그래프 중 특별한 성질을 갖는 그래프를 트리라고 한다.
- 특별한 성질 ?
- 트리의 간선들은 모두 방향성을 갖는다.
- 어떤 정점을 가리키는 정점의 개수는 최대 1개이다.
- 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다.
- 트리는 사이클을 갖지 않는다.
- 트리에서 어떠한 정점도 가리키지 않는 정점을 루트 노드(Root Node)라고 한다.
- 가장 위에 있는 노드
- 루트 노드로부터 다른 정점까지의 거리를 그 정점의 깊이라고 한다.
- 임의의 정점 A가 다른 정점 B를 가리킬 때, 즉 A -> B
- A는 B의 부모 노드(Parent Node)
- B를 A의 자식 노드(Child Node)
- 가리키는 정점이 없는 정점을 리프 노드(Leaf Node)라고 한다.
- 가장 아래에 있는 노드
- 어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점을
경로
라고 한다.
- 방향이 있는 간선을 가진 그래프는 유향 그래프라고 한다.
- 처음 시작한 정점으로 다시 돌아오는 경로를
사이클
이라고 한다. - 3 - 5 - 6 - 3 :
사이클
- 그래프 중 특별한 성질을 갖는 그래프를 트리라고 한다.
- 특별한 성질 ?
- 트리의 간선들은 모두 방향성을 갖는다.
- 어떤 정점을 가리키는 정점의 개수는 최대 1개이다.
- 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다.
- 트리는 사이클을 갖지 않는다.
- 트리에서 어떠한 정점도 가리키지 않는 정점을 루트 노드(Root Node)라고 한다.
- 가장 위에 있는 노드
- 루트 노드로부터 다른 정점까지의 거리를 그 정점의 깊이라고 한다.
- 임의의 정점 A가 다른 정점 B를 가리킬 때, 즉 A -> B
- A는 B의 부모 노드(Parent Node)
- B를 A의 자식 노드(Child Node)
- 가리키는 정점이 없는 정점을 리프 노드(Leaf Node)라고 한다.
- 가장 아래에 있는 노드
트리는 계층적인 구조로 되어 있는 자료구조이다.
운영체제에서 파일을 분류하기 위해 사용하는 디렉토리가 트리 구조의 대표적인 예시 !
➕ 이진 트리
- 각 정점들이 자식 노드를 최대 2개까지만 갖는 트리
- 이진 탐색 트리 등 유용하게 활용되는 트리 중에는 대부분 이진 트리를 응용한 것
➕ 포화 이진 트리
- 리프 노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있고
- 모든 리프 노드의 깊이가 동일한 트리
- 트리의 높이를
h
라고 하면, 정점의 개수는2^h - 1
개 이다.
➕ 완전 이진 트리
- 마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며, 마지막 깊이의 정점들은 가능한 한 왼쪽에 있는 트리를 가리키는 것
- 포화 이진 트리에서 마지막 깊이의 정점이 오른쪽에서부터 일부 제거된 트리라고 볼 수 있다.
- 높이가 h일 때, 정점의 개수는 2^(h-1) 이상 2^h -1 이하이다.
➕ 정 이진 트리
- 리프 노드를 제외한 모든 노드들이 두 개의 자식을 갖고 있는 트리이다.
- 즉, 모든 정점은 0개 또는 2개의 자식 노드를 가진다.
🌳♻ 트리의 순회
- 트리의 순회란, 트리의 모든 노드를 방문하는 것이다.
- 트리에 들어있는 자료에 접근하기 위해 순회한다.
- 배열, 연결 리스트 등 선형 구조는 각 자료가 순서를 갖지만, 비선형 구조(트리 등)는 정해진 순서가 존재하지 않는다.
- 트리의 모든 노드를 방문하는 순서는 크게 두 가지가 있다. 이는 그래프 순회에도 동일하게 적용된다.
위 트리를 기준으로 순회를 해보겠다.
DFS (깊이 우선 탐색)
- 전위 순회 : root -> left -> right
- 1 - 2 - 4 - 5 - 3 - 6 - 7
- 중위 순회 : left -> root -> right
- 4 - 2 - 5 - 1 - 6 - 3 - 7
- 후위 순회 : left -> right -> root
- 4 - 5 - 2 - 6 - 7 - 3 - 1
- DFS는 재귀 호출을 사용하는 알고리즘으로, DFS를 이해하기 위해서는 트리의 재귀적 특성을 이해해야 한다.
- 트리의 재귀적 특성 : 전체 트리를 순회하기 위해, 서브 트리를 순회한다.
- 순회를 위해 순회한다 -> 재귀 호출
DFS방식 구현
- preorder, inorder, postorder 구현
def preorder(tree) :
# 순회를 한 결과 방문한 노드들을 순서대로 담고 있는 리스트
# result에 값을 추가한다 = 현재 노드를 방문한다.
result = []
result.append(tree.index)
if tree.left != None:
result = result + preorder(tree.left)
if tree.right != None:
result = result + preorder(tree.right)
return result
def inorder(tree) :
result = []
if tree.left != None:
result = result + inorder(tree.left)
result.append(tree.index)
if tree.right != None:
result = result + inorder(tree.right)
return result
def postorder(tree) :
result = []
if tree.left != None:
result = result + postorder(tree.left)
if tree.right != None:
result = result + postorder(tree.right)
result.append(tree.index)
return result
BFS (너비 우선 탐색)
방문 순서 : 1 - 2 - 3 - 4 - 5 - 6 - 7
BFS는 큐 자료구조를 이용하여 구현한다.
현재 정점과 이웃한 정점일수록 먼저 방문해야 하므로 FIFO 자료구조인 큐를 이용해야 한다.
BFS방식 구현
from queue import Queue
def BFS(tree) :
q = Queue()
q.put(tree)
result = []
#q에 뭔가 들어있다면 계속 반복을 한다. -> 더이상 노드 없을 때 종료
while len(q.queue) > 0:
cur = q.get()
if cur == None :
continue
result.append(cur.index)
q.put(cur.left)
q.put(cur.right)
return result
이진 트리 구현
#Tree 클래스는 어떤 트리의 루트 노드에 대한 정보를 갖고 있다.
#루트 노드를 통해 하위 노드에 접근할 수 있으므로 전체 트리에 접근할 수 있음!
class Tree:
def __init__(self, i, l, r) :
self.index = i
self.left = l
self.right = r
#재귀적으로 동작한다.
#새로운 노드가 현재 노드의 자식으로 추가되어야 하는 경우
# -> 바로 추가
#그렇지 않다면, 자기 자식중에 새로운 노드를 받을 수 있는 노드를 탐색한다
# -> 재귀 알고리즘 도입
def addNode(self, i, l, r) :
'''
트리 내의 정점 i에 대하여 왼쪽자식을 l, 오른쪽 자식을 r로
설정해주는 함수를 작성하세요.
'''
#루트 노드에 대한 처리
if self.index == None or self.index == i:
self.index = i
self.left = Tree(l, None, None) if l != None else None
self.right = Tree(r, None, None) if r != None else None
return True
else:
flag = False
if self.left != None:
flag = self.left.addNode(i, l, r)
if flag == False and self.right != None:
flag = self.right.addNoade(i, l, r)
return flag
🌳 트리의 활용 - 이진 탐색 트리
- 컴퓨터에서 트리를 활용하는 예시는 대표적으로 이진 탐색 트리가 있다.
- 정렬된 상태를 유지하는 배열의 추가, 삭제 연산은 O(N)의 시간 복잡도를 가진다.
- but 정렬된 자료구조에서 사용할 수 있는 탐색 알고리즘인 이진 탐색을 이용하면 정렬된 배열 내에서의 자료 탐색을 O(logn)만에 수행 가능
- 이진 탐색 : 정렬된 배열의 중간 값과 찾는 값을 비교햇 좌측, 우측 다시 탐색하는 알고리즘
- 이진 탐색 트리는 항상 정렬된 상태를 유지하는 자료구조이며, 어떤 정점의 왼쪽 서브 트리는 그 정점보다 같거나 작은 정점들로만, 오른쪽 서브 트리는 그 정점의 값보다 큰 정점들로만 이루어져 있다 !
- 이진 탐색 트리에서 각 요소를 오름차순으로 탐색하기 위해서 중위 순회를 이용할 수 있다.
- 삽입, 삭제 시간 복잡도는 트리의 높이에 비례
트리의 높이 & 너비
- 높이
트리를 DFS로 순회하다 보면 언젠가 리프 노드에 도달하게 되는데,
이때 각 노드가 루트 노드로부터 얼마나 떨어져 있는지 계산할 수 있다
모든 리프 노드에 대해 깊이를 구하고, 가장 큰 값에 1을 더해 출력해주면 된다.
- 너비
주어진 트리의 너비가 가장 큰 레벨과 그 레벨의 너비를 계산해야 한다.
레벨이란, 깊이가 같은 노드들의 집합을 의미하며 루트 노드부터 1로 시작한다.
같은 레벨의 노드는 같은 행에 위치해야 하고, 한 열에는 하나의 정점만 위치해야 한다.
img출처: 엘리스AI트랙
이때 가장 너비가 긴 레벨은 2이고, 그 너비는 4이다.
정점의 행은 각 정점의 깊이를 구하면서 구할 수 있다.
그렇다면 열은 ?
어떤 정점 A의 왼쪽 서브 트리의 정점들의 열이 모두 확정되었다면 비로소 A의 열도 확정지을 수 있다.
- 왼쪽 정점 0 ~ 7 열 차지했다하면, 정점 A는 8번째 열에 넣으면 된다.
- 오른쪽 정점은 8 ~ n번째에 들어간다
- 왼쪽 서브 트리를 먼저 확정 짓는다 = 왼쪽 서브 트리를 먼저 방문한다.
즉, 중위 순회를 이용하여 트리의 너비를 구할 수 있다.
트리 높이 구하기
def getHeight(myTree) :
#루트 노드를 포함해서, 왼쪽 서브트리와 오른쪽 서비트리를 모두 포함
#왼쪽 서브트리의 높이를 구해보고,
#오른쪽 서브트리의 높이를 구해보고,
#두 높이를 비교 => 더 높은 서브트리의 높이 + 1(루트 노드)
if myTree == None:
return 0
else:
return 1 + max(getHeight(myTree.left), getHeight(myTree.right))
트리의 너비 구하기
def inorder(tree, depth):
result = []
if tree.left != None:
result += inorder(tree.left, depth+1)
tree.setDepth(depth)
result.append(tree)
if tree.right != None:
result += inorder(tree.right, depth+1)
return result
def getWidth(myTree) :
# 반환값 형식 : (l, w)
result = inorder(myTree, 1)
# print('result:', result)
n = len(result)
#정점의 개수는 1000개 이하이다 (입력 조건)
# 깊이의 최댓값은 1000 이라고 가정
#left[i] = 깊이가 i인 모든 노드들 중에서, 가장 왼쪽에 있는 노드의 행
#right[i] = 깊이가 i인 모든 노드들 중에서, 가장 오른쪽에 있는 노드의 행
#어떤 깊이의 너비는 right[i] - left[i] 인 값
left = [1001 for i in range(1001)]
right = [-1 for i in range(1001)]
maxDepth = 0
for i in range(n):
d = result[i].depth
left[d] = min(left[d], i)
right[d] = max(right[d], i)
maxDepth = max(maxDepth, d)
ansDepth = 0
ans = 0
for i in range(1, maxDepth+1):
temp = right[i] - left[i] + 1
if ans < temp:
ansDepth = i
ans = temp
return (ansDepth, ans)*
트리 실습이 은근히 어렵다
다시 처음부터 차근차근 실습과 함께 공부해보자..!
Author And Source
이 문제에 관하여([자료구조/알고리즘] 4. 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@suhyun-guri/자료구조알고리즘-4.-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)