[자료구조와 알고리즘] Trees

8. Trees

Terminology

• tree 자료구조: 저장할 data를 노드에 저장하면서 노드들이 트리형태로 나열된 형태.

• root node:44번 노드

• parent node(ancestor;조상) / children node(desendant;후손)

  • 25번 노드의 ancestor -> 20, 39, 44 번 노드

  • 오른쪽 네모 박스는 67의 desendant node이지만 왼쪽 박스는 67의 desendant node가 아니다.

Binary trees

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

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

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

The number of children of a node x in a rooted tree T equals the degree of x.

The length of the simple path from the root r to a node x is the depth of x in T.

A level of a tree consists of all nodes at the same depth.

The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf, and the height of a tree is the height of its root.

• The height of a tree is also equal to the largest depth of any node in the tree.

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

keyword: 해당 노드에서 leaf node까지 갈 수 있는 simple path 까지의 높이

Tree traversal

The method to visit all the nodes in a tree is called tree traversal. This can be done either depth-first search (DFS) or breadth-first search (BFS).

• 모든 노드를 하나도 빠짐 없이 한 번씩만 방문

---

08-6

Depth-first traversal

• Start at the root and explore as far as possible before backtracking
• Depth-first traversal can be implemented by recursive algorithms
• Orders in depth-first traversal
  • [preorder] root → left subtree → right subtree
  • [inorder] left subtree → root → right subtree
  • [postorder] left subtree → right subtree → root

---

08-7

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

---

08-8

Example 2

---

08-9

Tree nodes

• The trees are the non-linear data structure; they store the data differently from other linear data structures such as arrays, lists, stacks, and queues.

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

---

AL08-10

def inorder(node): #8
    if node:
        inorder(node.left)
        print(node.data, end=' ')
        inorder(node.right)
        
def preorder(node): # 15
    if node:
        print(node.data, end=' ')
        preorder(node.left)
        preorder(node.right)
        
def postorder(node): # 22
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end=' ')

---

AL08-11

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

print("inorder: ") # 35
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 

---

AL08-12

Breadth-first traversal

This mode of traversal is implemented using a queue data structure. Starting with the root node, we push it into a queue.

The node at the front of the queue is accessed (dequeued) and either printed or stored for later use.

def breath_first(node): # 11
    queue = deque()
    queue.append(node)
    
    while len(queue): # 15
        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 

---

AL08-13

Binary search trees(BST)

• All items in the left subtree are less than the root
• All items in the right subtree are greater than or equal to the root
• Each subtree is itself a binary search tree(재귀적 구조)
• 노드의 이름: key
• 노드의 갯수가 n일 때, 원하는 값을 찾는데 걸리는 time complexity는 O(logn)이다.
  • binary search도 O(logn)을 갖지만 BST가 데이터를 insert하고 delet하는 속도가 압도적으로 빠르다.
    • 데이터를 한 칸씩 미는 과정이 없기 때문
    • insert하는데 걸리는 시간은 O(1) : 항상 맨 밑(leaf node)에 집어넣게 되어있기 때문
  • 사실상 최악의 경우는 n의 경우 n번만에 찾을 수도 있기 때문에 O(n)이긴 하지만 그 경우를 제외하고는 모두 O(logn)이기 때문에 이를 감안한다.

---

AL08-14

A binary search tree(BST) is a tree that is structurally a binary tree, and stores data in its nodes very efficiently.

It provides very fast search operations, and other operations such as insertion and deletion are also very easy and convenient.

Queries on a binary search tree.

To search for the Key 13 in the tree, we follow the path 15 → 6 → 7 → 13 from the root.

The minimum key in the tree is 2, which is found by following left pointers from the root.

The maximum key 20 is found by following right pointers from the root.

---

AL08-15

BST traversal

• 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!

---

AL08-16

Binary search tree implementation

Let’s begin the implementation of a BST in Python.

We need to keep track of the root node of the tree, so we start by creating a Tree class that holds a reference to the root node:

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

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

---

AL08-17

	def find_min(self): #12
        node = self.root
        while node.left:
            node = node.left
        return node
    
    def find_max(self): #18
        node = self.root
        while node.right:
            node = node.right
        return node

---

AL08-18

BST 구조를 만들기 위해서는 한 노드씩 순서대로 삽입을 진행해야 한다.

그런데 처음 root node를 무엇으로 하느냐에 따라 다른 BST가 만들어 질 수 있다.

Inserting nodes

• All BST insertions take place at a leaf node
  • 노드 하나 추가는 항상 leaf node에서만 일어난다.

Inserting an item with key 13 into a binary search tree.

---

AL08-19

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

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

---

AL08-20

	def insert(self, data): #24
        node = Node(data)
        parent = None #파란색 포인터
        current = self.root # 빨간색 포인터
        
        while current: # 29
            parent = current
            if node.data < current.data:
                current = current.left
            else: # 추가할 노드가 더 크거나 같은 경우
                current = current.right
                
                ...

---

AL08-21

cont.

	def insert(self, data): #24
        node = Node(data) # 삽입할 노드 생성
        parent = None # 파란색 포인터
        current = self.root # 빨간색 포인터
        
        while current: # 29
            paraent = current
            if node.data < current.data:
                current = current.left
            else: 
                current = current.right
                
        if parent is None: # 36 ; original tree가 비어있던 경우
            self.root = node
        elif node.data < parent.data:
            parent.left = node
        else:
            parent.right = node

---

AL08-22

Searching the tree

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

---

AL08-23

In-order traversal

	def inorder(self): #55
        self._inorder(self.root)
        
    def _inorder(self, node): #58
        if node:
            self._inorder(node.left)
            print(node.data, end=' ')
            self._inorder(node.right)
            
    def reverse_inorder(self): # 64
        self._reverse_inorder(self.root)
        
    def _reverse_inorder(self, node): # 67
        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)
    

• 두 개로 만드는 경우

  • 	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 변수가 자동으로 생성되는 것을 명심

---

AL08-24

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

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

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

min: 1
max: 9
1: 1
2: 2
3: None
4: None
5: 5
6: None
7: 7
8: None
9: 9
1 2 5 7 9 
9 7 5 2 1 

---

AL08-25

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

---

AL08-26

코드 작성해 보기

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


class Node: #5
    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()) # 47
name_list = []
tree = Tree()

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

• sys.stdin.readline()을 하면 input()과 다른게 맨 마지막의 \n 까지 그대로 받기 때문에 \n은 제거해 주는 것이다.
• 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):  # 24
        node = Node(data, num)
        parent = None  # 파란색 포인터
        current = self.root  # 빨간색 포인터

        while current:  # 29
            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

---

AL08-27

백준 17219번 비밀번호 찾기

---

AL08-28

사이트 이름 = 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):  # 24
        node = Node(data, num)
        parent = None  # 파란색 포인터
        current = self.root  # 빨간색 포인터

        while current:  # 29
            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

---

#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;
}