<코딩테스트 Level1> 11일차 - 트리

📌 트리

이전까지 배웠던 배열과 스택, 큐 등은 모두 데이터가 일렬로 나열되는 선형 자료구조였다.

하지만 모든 데이터가 일직선으로 연결된 구조는 아니다. 비선형 자료구조도 존재한다. 아래와 같은 조직도를 예로 들 수 있다.

위와 같은 계층 구조로 표현하기 위한 비선형 자료구조가 바로 트리이다.

이처럼 나무를 거꾸로 그린 형태를 띄기 때문에 트리라는 이름이 붙여졌다.

📌 트리 관련 용어

1. 노드와 엣지
   

첫 번째로 A, B, C, D와 같이 트리를 구성하는 요소들을 노드 혹은 정점이라고 부르고, 이러한 노드와 노드를 잇는 연결 선을 Edge, 간선이라고 부른다.

2. 트리의 레벨과 깊이
   

뜨리의 각 층 별로 숫자를 매겨 level이라고 이름을 붙였다. 이 때 level 0에 존재하는, 즉 최 상단의 노드를 Root Node라고 부른다.

또한 최 하단의 노드에 접근하기 위해 거쳐야 하는 Edge의 수를 Height 트리의 높이 라고 한다.

위의 트리는 A가 Root Node이고, 트리의 높이는 2이다.

3. 노드간의 관계
   

전체 트리가 아닌 한 노드와 연결된 노드들을 살펴볼 때, 윗 레벨에 존재하는 노드를 부모 노드 (Parent Node), 부모 노드와 연결된 노드들을 자식 노드 (Child Node)라고 한다. 또한 같은 부모 노드를 갖는 여러 자식 노드들을 형제 노드 (Sibling Node)라고 한다.

위의 예시에선 B가 부모 노드, D와 E는 형제 노드이자 B의 자식 노드이다.

📌 트리의 특성

트리를 왜 사용하는 걸까 ❓
위에서 사용했던 트리를 자세히 살펴보자.

여기서 A 노드는 B 노드와 C 노드에 연결되어 있다.
B 노드를 분리해서 살펴보자.

부모 노드에서 분리한 자식 노드들도 트리의 형태를 지니고 있다.

즉, 한 노드에서 자식 노드들을 타고 내려가더라도 그 자식 노드를 부모 노드로 하는 트리 구조가 존재하는 것이다.

이 때, 한 노드 X와 그 자식 노드로 구성된 트리를 X를 루트 노드로 하는 서브 트리(Sub-Tree)라고 한다.

📌 이진 트리

알고리즘에서는 일반적으로 트리를 구현하기 위해, 자식 노드의 수가 2개로 제한된 이진 트리를 사용한다.

도입부에서 설명한 조직도가 일반 트리이고, 트리 구성 요소에서 예시로 보여준 트리가 이진 트리라고 볼 수 있다.

📌 이진 트리 노드 구현

이진 트리의 노드만 구현해보자.
이진 트리는 하나의 노드가 최대 두 개의 자식 노드를 갖는 트리이다.

바로 링크드 리스트와 같은 구조로 노드를 구성한다.

다만, 링크드 리스트는 하나의 포인터만 가졌다면, 이진 트리는 두 개의 포인터를 가진다는 차이점이 존재한다.

left, right 라는 두 개의 포인터를 갖는 노드를 구현하고, 아래와 같은 트리 구조를 만들어 보자.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

root = Node(1)
node_2 = Node(2)
node_3 = Node(3)
root.left = node_2
root.right = node_3

node_4 = Node(4)
node_5 = Node(5)
node_2.left = node_4
node_2.right = node_5

print("루트 노드 :", root.data)
print("루트 노드의 자식:", root.left.data, root.right.data)
print("루트 노드 왼쪽 자식의 자식들:", root.left.left.data, root.left.right.data)

📌 트리의 탐색

지금은 단순히 출력을 위해 위처럼 직접 left, right 를 사용해 자식 노드에 접근했지만, 사실 위의 방법을 실제 문제를 풀 때 사용하기는 어렵디.

문제에서 주어지는 트리의 구조도 모르고, 트리의 깊이가 얼마나 될 지도 모르기 때문이다. 이러한 문제를 해결하기 위해, 우리는 트리를 탐색하는 방법을 알아봐야 한다.

물론 그냥 탐색하는 것이 아닌 각각의 노드를 정확히 한번만, 또 체계적으로 방문해야 한다.

트리에서 노드를 탐색하는 방법은 크게 세 가지,
전위 순회와 중위 순회, 후위 순회로 나뉘어요.

📌 전위 순회, Preorder

전위 순회는 기본적으로 루트 노트부터 시작해, 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 트리를 방문하는 방법이다.

위 트리를 기준으로 1 -> 2 -> 4 -> 5 -> 3의 순서로 노드를 탐색한다. 트리 탐색 방법 중에서 가장 쉽고 자주 사용되는 방식이다.

트리에 대해 학습할 때 각각의 자식 노드는 각자 Sub-Tree를 구성한다고 했다. 즉, 트리는 재귀적인 구조를 지닌 자료라는 사실을 이용해 전위 순회도 재귀로 구현한다.

👉 전위 순회 알고리즘

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def get_tree():
    root = Node(1)
    node_2 = Node(2)
    node_3 = Node(3)
    root.left = node_2
    root.right = node_3

    node_4 = Node(4)
    node_5 = Node(5)
    node_2.left = node_4
    node_2.right = node_5

    return root

def pre_order(node):
    if node == None:
        return

    print(f"{node.data}  ", end="")
    pre_order(node.left)
    pre_order(node.right)

root = get_tree()
pre_order(root)

실제로 어떻게 탐색을 진행하는지 한 줄 한 줄 따라가 보자.

첫 번째로, 루트 노드를 전위 순회 함수에 넣어준다.
이를 통해 pre_order 함수가 호출되고, 코드들이 하나 씩 실행된다.

전위 순회는 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 탐색하기 때문에, 우선 부모 노드 데이터를 먼저 출력한다.

두 번째로 pre_order 함수를 호출하면서 재귀함수 구조를 만든다.

부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서를 지키기 위해 왼쪽 자식 노드를 pre_order 함수에 넣어준 것이다.

원래라면 세 번째 줄 코드인 pre_drder(root -> right)가 실행되어야 하지만, 3번에서 왼쪽 자식 노드로 전위 순회 함수를 다시 호출했기 때문에 루트 노드의 왼쪽 자식 노드 데이터가 먼저 출력된다.

즉, 2번 노드의 데이터가 출력된다.

4번과 마찬가지로 왼쪽 자식 노드를 전위 순회에 넣어준다. 4번 노드가 들어간다.

📌 중위 순회

중위 순회는 왼쪽 자식 노드부터 탐색을 시작해, 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 탐색을 진행한다.

전위 순회가 부모 노드부터 먼저 데이터를 출력했다면,
중위 순회는 왼쪽 자식 노드 먼저 데이터를 출력하는 것이다.

위의 트리 예시에선 4 -> 2 -> 5 -> 1 -> 3 순서로 데이터를 가져온다.

# ... 이전 코드
def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(f"{node.data}  ", end="")
    in_order(node.right)

root = get_tree()
in_order(root)

📌 후위 순회

전위 순회는 부모 -> 왼쪽 -> 오른쪽
중위 순회는 왼쪽 -> 부모 -> 오른쪽

후위 순회는 왼쪽 노드 -> 오른쪽 노드-> 부모노드순서로 탐색한다.

위 트리 예시에선 4 -> 5 -> 2 -> 3 -> 1 순서로 데이터를 가져온다.

# ... 이전 코드
def post_order(node):
    if node == None:
        return
    post_order(node.left)
    post_order(node.right)
    print(f"{node.data}  ", end="")

root = get_tree()
post_order(root)