[자료구조와 알고리즘 | 파이썬] Trees (트리 자료구조)

Trees(트리 자료구조)

1. Terminology (용어)

트리 구조

 

• tree 자료구조: 저장할 data를 노드에 저장하면서 노드들이 트리형태로 나열된 형태.
• root node:위 그림에서 44번 노드
• parent node(ancestor;조상) / children node(desendant;후손)
  • 25번 노드의 ancestor -> 20, 39, 44 번 노드
  • 오른쪽 점선 네모 박스는 67의 desendant node들이지만 왼쪽 박스는 67의 desendant node가 아니다.

 

2. Binary trees (이진 트리)

Binary tree는 모든 노드가 두 자식을 최대로 갖는 구조입니다.(자식 노드가 최대 2개)

 

binary tree에서 노드들 배치는 왼쪽 서브 트리와 오른쪽 서브 트리의 형태로 조직화되어 있습니다.

아래 다이어그램은 다섯 개의 노드를 가진 이진트리의 예시이다.

• 루트 트리 T에서 노드 x의 자식 수는 x의 degree(차수)와 같다.
• 루트 r에서 노드 x까지의 단순한 경로의 길이는 트리에서 x의 depth(깊이)이다.
• 트리의 level은 동일한 depth의 모든 노드로 구성됩니다.
• 트리에서 노드의 height(높이)는 노드에서 leaf 노드(가장 말단 노드)까지 이어지는 가장 긴 단순한 아래쪽 경로의 edge 수이며,
• 즉, 트리의 height(높이)는 root의 높이이다.
• 트리의 height는 트리에서 특정 노드의 가장 깊은 depth와도 동일하다.

트리의 depth와 height

leaf 노드에 자식 노드를 하나 추가하게 되면 root node의 height가 3에서 4로 바뀌게 됩니다.

 

즉, 이것만 생각하면 됩니다. "해당 노드에서 leaf node까지 갈 수 있는 simple path 길이"

 

3. Tree traversal (트리 순회)

트리의 모든 노드를 방문하는 방법을 tree traversal(트리 순회)이라고 합니다. 이것은 깊이 우선 검색(DFS) 또는 폭 우선 검색(BFS) 중 하나로 수행될 수 있습니다.

 

• 모든 노드를 하나도 빠짐 없이 한 번씩만 방문한다는 특징을 가진다.

 

4. Depth-first traversal (깊이 우선 순회)

• 백트래킹(backtracking)하기 전에 루트 노드에서 시작하여 가능한 한 멀리 탐색합니다.
• 깊이 우선 순회는 재귀 알고리즘에 의해 구현될 수 있습니다.
• 깊이 우선 순회에서 순서에 따라 세 개의 방식으로 나누어집니다.
  
  • [preorder] root → left subtree → right subtree
  • [inorder] left subtree → root → right subtree
  • [postorder] left subtree → right subtree → root

 

 

5. Example 1

• Inorder → G-D-H-B-E-A-C-F
• Preorder → A-B-D-G-H-E-C-F
• Postorder → G-H-D-E-B-F-C-A
• Breadth-first → A-B-C-D-E-F-G-H

 

6. Example 2

 

 

7. Tree nodes (트리 노드)

트리는 비선형적 자료구조 입니다.

 

또한 데이터를 배열, 목록, 스택 및 큐와 같은 다른 선형 데이터 구조와는 조금 다르게 저장합니다.

 

class Node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None
    def inorder(node): 
        if node:
            inorder(node.left)
            print(node.data, end=' ')
            inorder(node.right)

    def preorder(node): 
        if node:
            print(node.data, end=' ')
            preorder(node.left)
            preorder(node.right)

    def postorder(node):
        if node:
            postorder(node.left)
            postorder(node.right)
            print(node.data, end=' ')

root = Node('A') 
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

print("inorder: ") 
inorder(root)
print("\npreorder: ")
preorder(root)
print("\npostorder: ")
postorder(root)

 

 

inorder: 
D B E A C 
preorder: 
A B D E C 
postorder: 
D E B C A

 

 

8. Breadth-first traversal (너비 우선 순회)

이 순회 방식은 큐 데이터 구조를 사용하여 구현됩니다. 루트 노드를 시작으로 큐에 넣습니다(enqueue).

큐에서 맨 앞에 있는 노드에 액세스(dequeue를 통한)하여 나중에 사용할 수 있도록 print하거나 저장합니다.

 

 

def breath_first(node): 
    queue = deque()
    queue.append(node)

    while len(queue):
        visit = queue.popleft()
        print(visit.data, end=' ')
        if visit.left:
            queue.append(visit.left)
        if visit.right:
            queue.append(visit.right)

A B C D E

 

 

9. Binary search trees(BST) - 이진 탐색 트리

• left subtree에 모든 item들이 루트 값보다 작다.
• right subtree에 모든 item들이 루트 값보다 크거나 같다.
• 각 subtree는 그 자체로 이진 탐색 트리 구조이다. (재귀적 구조)
• 노드의 이름: key
• 노드의 갯수가 n개일 때, 원하는 값을 찾는데 걸리는 시간복잡도는 O(logn)이다.
  • 리스트의 binary search 알고리즘도 O(logn)을 갖지만 BST가 데이터를 insert하고 delete하는 속도가 압도적으로 빠르다.
    • BST에는 데이터를 한 칸씩 미는 과정이 없기 때문
    • insert하는데 걸리는 시간은 O(1) : 항상 맨 밑(leaf node)에 집어넣게 되어있기 때문
  • 사실상 최악의 경우는 n의 경우 n번만에 찾을 수도 있기 때문에 O(n)이긴 하지만 그 경우를 제외하고는 모두 O(logn)이기 때문에 이를 감안했을 때 굉장히 좋은 탐색 방식 중 하나임.

 

이진 탐색 트리는 구조적으로 이진 트리인 트리 구조이고, 각 노드에 데이터를 매우 효율적으로 저장합니다.

매우 빠른 탐색 연산을 제공하며, 삽입과 삭제같은 다른 연산 또한 다른 탐색 방식에 비해 매우 쉽고 편리합니다.

 

이진 탐색 트리에 대한 쿼리입니다.

트리에서 key 13을 찾기 위해서 우리는 루트에서부터 15 → 6 → 7 → 13 경로를 따라가야 합니다.

 

트리에서 최소값을 가지는 key는 2인데, 이는 루트로부터 left pointer들을 따라감으로써 찾을 수 있는 값입니다.

반면 최대값을 가지는 key는 20인데, 이는 루트로부터 right pointer들을 따라감으로써 찾을 수 있는 값입니다.

 

 

BST traversal (BST 순회)

• Preorder: 40 -> 20 -> 10 -> 30 ->  50 -> 60
• Inorder: 10 -> 20 -> 30 -> 40 ->  50 -> 60 (ascending sort)
• Postorder: 10 -> 30 -> 20 -> 60 -> 50 -> 40
• Reverse inorder: 60 -> 50 -> 40 ->30 ->20 ->10 (descending sort)
  • Right -> Root -> Left
  • 혹은 -를 붙이는 idea!

보시면 아시겠지만 BST에서 inoder 방식의 순회를 하면 값을 오름차순으로 탐색할 수 있게 됩니다.

 

Binary search tree implementation (BST 구현)

파이썬으로 BST의 구현을 해보겠습니다.

트리의 루트 노드를 추적해야 하므로 루트 노드에 대한 참조를 포함하는 tree 클래스를 만드는 것으로 시작합니다:

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


class Tree: 
    def __init__(self):
        self.root = None
    def find_min(self):
        node = self.root
        while node.left:
            node = node.left
        return node

    def find_max(self):
        node = self.root
        while node.right:
            node = node.right
        return node

 

 

BST 구조를 만들기 위해서는 한 노드씩 순서대로 삽입을 진행해야 합니다. 그런데 처음 root 노드를 무엇으로 하느냐에 따라 다른 BST가 만들어질 수 있음을 유의해야 합니다.

 

 

Inserting nodes

모든 BST 삽입은 leaf node에서 일어납니다.

 

이진 탐색 트리로 key 13을 가진 item을 삽입하는 과정을 한번 보도록 하겠습니다.

빨간색 포인터(변수)를 loop로 계속 돌리다가 None이 되면 그곳에 매달면 됩니다.

그런데 빨간색이 None이 되어버리면 지금 현재 위치를 잃어버리기 때문에 그 전 위치를 항상 따라오는 파란색 포인터를 별도로 지정해 준다.

 

코드로 구현하면 아래와 같습니다.

    def insert(self, data): 
        node = Node(data) # 삽입할 노드 생성
        parent = None # 파란색 포인터
        current = self.root # 빨간색 포인터

        while current: 
            paraent = current
            if node.data < current.data:
                current = current.left
            else: 
                current = current.right

        if parent is None: # original tree가 비어있던 경우
            self.root = node
        elif node.data < parent.data:
            parent.left = node
        else:
            parent.right = node

 

 

Searching the tree (트리 탐색)

    def search(self, data): 
        node = self.root
        while True:
            if node is None:  # tree empty or data가 없음
                return node
            elif node.data == data:
                return data
            elif data < node.data:
                node = node.left
            else:
                node = node.right

BST의 특성인 왼쪽 하위 트리에는 루트보다 더 작은 값들이 담겨 있고 오른쪽 하위 트리는 그 반대인 것을 이용하여 그것에 해당하는 left 포인터 혹은 right 포인터를 통해 이동하면서 같은 data를 가진 노드를 찾아 return 합니다.

 

In-order traversal (In-order 방식 순회)

    def inorder(self): 
        self._inorder(self.root)

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.data, end=' ')
            self._inorder(node.right)

    def reverse_inorder(self): 
        self._reverse_inorder(self.root)

    def _reverse_inorder(self, node):
        if node:
            self._reverse_inorder(node.right)
            print(node.data, end=' ')
            self._reverse_inorder(node.left)

inorder vs. _inorder ??

 

• inorder 만을 사용한 코드

    def inorder(self, node):
        if node:
                self.inorder(node.left)
            print(node.data, end=' ')
            self.inorder(node.right)
t = Tree()
t.inorder(t.root)

 

• 두 개 모두(inorder, _inorder) 사용한 코드

    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.data, end=' ')
            self._inorder(node.right)
t = Tree()
t.inorder()

inorder 함수를 호출할 때 루트 노드를 인자로 넣어주지 않아도 되기 때문에 프로그래머 입장에서 번거롭게 느껴지지 않고 헷갈리지 않습니다.

• tree object를 생성할 때 root 변수가 자동으로 생성되는 것을 명심

 

 

tree = Tree() 
tree.insert(5)
tree.insert(2)
tree.insert(7)
tree.insert(9)
tree.insert(1)

print("min: %s" % tree.find_min().data) 
print("max: %s" % tree.find_max().data)

for i in range(1, 10):
    found = tree.search(i)
    print("{}: {}".format(i,found))

tree.inorder()
print()
tree.reverse_inorder()

 

---

 

 

1620번: 나는야 포켓몬 마스터 이다솜

 

 

import sys 
sys.stdin = open('bj1620_in.txt', 'r')


class Node: 
    def __init__(self, data=None, num=None):
        self.data = data # 노드의 이름 즉, key
        self.num = num # 노드에 해당하는 번호
        self.left = None
        self.right = None

n, m = map(int, input().split())
name_list = []
tree = Tree()

for i in range(1, n+1):
    name = sys.stdin.readline().rstrip('\n') # input speed를 위한 작업

• sys.stdin.readline()을 하면 input()과 다른 점이 맨 마지막의 \n 까지 그대로 받기 때문에 \n은 rstrip() 메소드를 통해 제거해 주어야 한다는 것이다.
• query[0].isalpha() 를 통해 숫자인지 string인지 판별하여 경우를 나눠서 구현할 수 있다.

# 정답 코드
import sys
sys.stdin = open("bj1620_in.txt", 'r')


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


class Tree:
    def __init__(self):
        self.root = None

    def insert(self, data, num):
        node = Node(data, num)
        parent = None  # 파란색 포인터
        current = self.root  # 빨간색 포인터

        while current: 
            parent = current
            if node.data < current.data:
                current = current.left
            else:
                current = current.right

        if parent is None:
            self.root = node
        elif node.data < parent.data:
            parent.left = node
        else:
            parent.right = node

    def search(self, data=None):
        node = self.root

        while True:
            idx = node.num
            if node is None:
                return node
            elif node.data == data:
                return idx
            elif data < node.data:
                node = node.left
            else:
                node = node.right


n, m = map(int, input().split())
name_list = []
tree = Tree()

for i in range(1, n+1):
    name = sys.stdin.readline().rstrip('\n')
    tree.insert(name, i)
    name_list.append(name)

for i in range(0, m):
    query = sys.stdin.readline().rstrip('\n')

    if query[0].isalpha():
        print(tree.search(query))
    else:
        print(name_list[int(query)-1])

• 실행 결과

Pikachu
26
Venusaur
16
14

 

 

---

17219번: 비밀번호 찾기

 

 

사이트 이름 = key 값

비밀 번호 = value

으로 하는 노드를 생성하도록 한다.

import sys
sys.stdin = open('bj17129_in.txt')


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


class Tree:
    def __init__(self):
        self.root = None

    def insert(self, data, num):
        node = Node(data, num)
        parent = None  # 파란색 포인터
        current = self.root  # 빨간색 포인터

        while current:
            parent = current
            if node.data < current.data:
                current = current.left
            else:
                current = current.right

        if parent is None:
            self.root = node
        elif node.data < parent.data:
            parent.left = node
        else:
            parent.right = node

    def search(self, data=None):
        node = self.root

        while True:
            pd = node.pd
            if node is None:
                return node
            elif node.data == data:
                return pd
            elif data < node.data:
                node = node.left
            else:
                node = node.right


n, m = map(int, input().split())
tree = Tree()

for i in range(n):
    site, password = sys.stdin.readline().split()
    tree.insert(site, password)

for i in range(m):
    query = sys.stdin.readline().rstrip('\n')
    print(tree.search(query))

THEKINGOD
UAENA
IU
ADREAMER

 

하지만 파이썬에서는 딕셔너리를 통해 key, value 값을 다룰 수 있어 트리를 구현하지 않고도 굉장히 간단히 구현할 수 있습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
add = {}

for _ in range(N):
    site, ps = input().split()
    add[site] = ps

for _ in range(M):
    print(add[input().rstrip()])

 

 

C 코드로 구현

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int myFork(int i, int me, int max_depth)
{
  pid_t psid = fork();

  if (psid == -1) {
    return -1;
  }
  else if (psid == 0) {
    // 자식 프로세스
    printf("[%d]: i=%d (depth %d)\n", getpid(), i, me);

    if (me < max_depth) {
      myFork(2*i+1, me+1, max_depth); // 재귀 호출
      myFork(2*i+2, me+1, max_depth);
    }

    exit(-1);
  }
  else {
    // 부모 프로세스
    pid_t pid;
    int status;
    pid = waitpid(psid, &status, 0);

    if (pid == -1)
        printf("fork error\n");
        return -1;
  }
}

int main(int argc, char *argv[])
{
  int depth;

  if (argc != 2) { // 인자로 depth 하나만을 반드시 받아야 프로그램 실행이 됨
    fprintf(stderr, "Usage: ./%s depth\n", argv[0]);
    return -1;
  }

  depth = atoi(argv[1]); // 인자로 숫자를 받아도 string 이기 때문에 int형으로 변환

  if (depth < 0) { // depth는 반드시 0 이상의 자연수이어야 함.
    fprintf(stderr, "%s: negative depth error\n", argv[0]);
    return -1;
  }

  myFork(0, 0, depth);

  return 0;
}