[자료구조/알고리즘] 4. 트리

GURI·2021년 10월 29일
엘리스AI트랙자료구조
0

자료구조/알고리즘

목록 보기
4/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)라고 한다.
    • 가장 아래에 있는 노드

트리는 계층적인 구조로 되어 있는 자료구조이다.
운영체제에서 파일을 분류하기 위해 사용하는 디렉토리가 트리 구조의 대표적인 예시 !

➕ 이진 트리

  • 각 정점들이 자식 노드를 최대 2개까지만 갖는 트리
  • 이진 탐색 트리 등 유용하게 활용되는 트리 중에는 대부분 이진 트리를 응용한 것

➕ 포화 이진 트리

  • 리프 노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있고
  • 모든 리프 노드의 깊이가 동일한 트리
  • 트리의 높이를 h라고 하면, 정점의 개수는 2^h - 1개 이다.

➕ 완전 이진 트리

  • 마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며, 마지막 깊이의 정점들은 가능한 한 왼쪽에 있는 트리를 가리키는 것
  • 포화 이진 트리에서 마지막 깊이의 정점이 오른쪽에서부터 일부 제거된 트리라고 볼 수 있다.
  • 높이가 h일 때, 정점의 개수는 2^(h-1) 이상 2^h -1 이하이다.

➕ 정 이진 트리

  • 리프 노드를 제외한 모든 노드들이 두 개의 자식을 갖고 있는 트리이다.
  • 즉, 모든 정점은 0개 또는 2개의 자식 노드를 가진다.

🌳♻ 트리의 순회

  • 트리의 순회란, 트리의 모든 노드를 방문하는 것이다.
  • 트리에 들어있는 자료에 접근하기 위해 순회한다.
  • 배열, 연결 리스트 등 선형 구조는 각 자료가 순서를 갖지만, 비선형 구조(트리 등)는 정해진 순서가 존재하지 않는다.
  • 트리의 모든 노드를 방문하는 순서는 크게 두 가지가 있다. 이는 그래프 순회에도 동일하게 적용된다.

    위 트리를 기준으로 순회를 해보겠다.

DFS (깊이 우선 탐색)

  1. 전위 순회 : root -> left -> right
    • 1 - 2 - 4 - 5 - 3 - 6 - 7
  2. 중위 순회 : left -> root -> right
    • 4 - 2 - 5 - 1 - 6 - 3 - 7
  3. 후위 순회 : 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)*

트리 실습이 은근히 어렵다
다시 처음부터 차근차근 실습과 함께 공부해보자..!

profile
GURI
Done is better than Perfect.
이전 포스트

[자료구조/알고리즘] 3. 스택과 큐

0개의 댓글