My Profile Photo

DongChanS's blog

수학과 학생의 개발일지

• on data structure, algorithm, tree, recursive

파이썬 자료구조 (3) Tree

아래 포스트는 Data Structure and Algorithmic Thinking with Python을 참고하여 작성되었습니다.

1) Tree and Binary Tree

1-1. What is a Tree?

앞서 배웠던 array, linked list, stack, queue는 대표적인 선형자료구조입니다. 이번에 배울 tree는 비선형 자료구조의 대표라고 할 수 있습니다.

구조는 간단합니다. 각 노드마다 next node에 대한 포인터가 여러 개인 구조입니다. 이러한 노드들이 계층을 이루기 때문에 Graphical form으로 구성된 자연을 표현하기 좋은 방법이라고 합니다.

1

신기하게도 트리에서는 원소가 들어온 순서는 크게 중요하지 않습니다. 왜냐하면비선형 자료구조이므로 원소의 위치를 따로 배당하는 작업이 필요하기 때문입니다. 이러한 작업을 위해서 이전에 배웠던 선형자료구조들을 사용합니다.


그래프론적으로 접근하면 Tree는 connected이며 acyclic인 그래프로 정의할 수 있는데, 그냥 Tree는 가지를 치면서 연결되어있는 그래프이구나! 라고 생각하셔도 무방합니다.

1-2. Glossary(용어)

선형자료구조들은 ‘다섯번째 원소’ 와 같이 원소를 직접적으로 표현할 수 있지만, Tree는 비선형 자료구조이기 때문에 어떤 원소를 직접적으로 표현하기 어렵습니다.

그래서 다른 원소들과의 관계(예: root트리에서 한 단계 밑에 있는 노드)를 통해서 원소를 표현하는데, 그렇기 때문에 이러한 관계를 정의하기 위한 용어들이 몇 가지 있습니다.

그렇지만 이러한 용어들에 너무 매몰되어 매우 지루했던 수업을 들은 적이 있어서 용어에 대한 설명은 최대한 짧게 하겠습니다.

  • Root : 가장 위의 노드 (보통 트리마다 한개있음)
  • Leaf : 가장 아래의 노드
  • child(자식, 나보다 한 단계 밑의 노드),Parent(부모, 나보다 한 단계 위의 노드), descendant(후손, 나보다 밑에 있는 노드), ancestor(조상, 나보다 위에있는 노드)
  • The depth of a node: node에서 Root노드까지의 거리
  • The Height of a node : node에서 Leaf노드까지의 거리
  • Level of the tree : The set of all nodes at given depth.
  • Size of a node : the number of descendants (자기자신 포함)


1-3. Binary Tree

Binary tree(이진트리)는 각 노드의 자식이 0~2개 사이인 Tree를 말합니다.

그렇기 때문에 이진트리에서는 각 노드의 자손을 Left node, Right node로 정의할 수 있습니다.

3

구현을 위해서는 Left node와 Rignth node의 주소를 가리키는 포인터를 정의하여 노드클래스를 정의할 수 있습니다. (Doubly Linked List와 비슷해 보입니다.)


Binary tree의 가장 큰 특성은, 이진트리를 left node와 right node로 쪼개어도 각각은 이진트리의 성질을 만족한다는 점입니다.

이러한 성질 때문에 이진트리는 greedy하게 level을 기준으로 한 재귀함수를 많이 사용할 수 있다는 장점이 있습니다. (level이 하나 낮춰도 똑같은 함수 계속 적용할 수 있기 때문)

2


1-4. Types of Binary Trees

이 부분은 안다루려고 했는데, 후에 등장할 이진힙같은 개념에서 필요한 개념이라 간단하게 언급하겠습니다.

  • Strict binary tree : 각 노드의 child node가 0개거나 2개거나
  • Full binary tree :각 노드의 child node가 2개
  • Complete binary tree : Leaf node들을 제외한 나머지 노드들은 fully binary tree의 특성을 따름.

예를 들면, 왼쪽이 Full binary tree이며, 오른쪽이 Complete binary tree입니다.

4

Full binary tree이면 원소가 n개일 때, tree의 높이는 log(n)에 가깝습니다.


2) Applications of Binary Trees

2-1. Expression trees are used in compilers

수식트리는 말그대로 사칙연산자와 피연산자(숫자)를 표현해놓은 트리입니다.

사칙연산자는 모두 이항연산자이기 때문에 이러한 연산을 Binary tree로 표현할 수 있습니다.

물론 일항연산인 unary operation도 이 트리를 통해서 표현할 수 있다고 합니다. (ex: unary minus, 3 - (-5) 에서 두번째 -는 unary minus입니다.)


5

우리는 사칙연산을 1 + 2 = 3 와 같이 중위연산자로 이해하지만, 컴퓨터에서는 1 2 + = 3 과 같이 후위연산으로 파악합니다.

그래서 후위연산 트리를 구현하기 위해서 Stack 자료구조를 이용하는데, 원리는 간단합니다.

  1. 피연산자와 연산자를 순서대로 stack에 넣는다.
  2. 다음 input이 연산자일 때, 이미 들어온 두개의 Expression tree(피연산자 하나도 expression tree로 생각)를 pop연산을 통해서 꺼낸다.
  3. 연산자를 root로 하고 첫번째로 pop된 원소를 left subtree, 두번째로 pop된 원소를 right subtree로 하는 새로운 tree를 만들어서 스택에 push한다.


2-2. Huffman coding trees that are used in data compression algorithms.

Huffman coding(허프만 부호화)은 여러 원소들을 bit 표현으로 대응시키고 싶을 때, 효율적으로 대응시키기 위해서 빈도 기반으로 대응시키는 방식입니다.

(많이 등장하는 원소 : 짧은 코드, 적게 등장하는 원소 : 긴 코드)

그렇게 빈도기반으로 대응시키면 전체 코드 길이를 짧게 만들 수 있기 때문입니다.


예를 들어봅시다.

“A_DEAD_DAD_CEDED_A_BAB_BABE_A_BEADED_ABACA_BED” 라는 문자열을 그냥 만들면 아스키코드(내지는 유니코드)를 사용해야 하기 때문에 개당 8비트가 소모됩니다.

그건 너무 비효율적이기 때문에 Huffman coding을 이용해서

  • _ : 00
  • D : 01
  • A : 10
  • E : 110
  • C : 1110
  • B : 1111

의 식으로 표현한다면 문자열의 길이를 훨씬 길이를 짧게 만들 수 있을 것입니다.

이러한 이유 때문에 Data compression을 위해서 허프만 코딩을 사용합니다.

허프만 코딩을 위해서는 Huffman coding tree를 만들어야 하는데요, 이 트리를 만드는 예시는 아래에 있습니다.


6

허프만 코딩에서 중요한 점은 해석의 유일성입니다.

만약 B를 11이라고 표현하게 된다면, C ( = 1110)과 BA( = 11 + 10)을 구분할 수 없게 됩니다. 이러한 해석의 유일성을 위해서 비트를 구성하는 모든 경우의 수를 사용하지는 않는데요. 허프만 트리를 만들 때 이러한 점을 반영한 것으로 보입니다.

구현은 나중에 배울 우선순위큐를 이용하기 때문에 다음에 알아보도록 하겠습니다. (아래 사진 : 위키피디아)

7


2-3 기타

  • Binary Search Tree(4편 예정) : 효율적으로 검색, 삭제, 삽입을 구현하기 위한 트리구조. 무려 평균적으로 logn의 시간복잡도를 가진다고 한다!
  • Priority Queue(5편 예정) : 최소의 원소를 검색하고 삭제하는데 logn (최악일 때)의 시간복잡도를 가진다고 합니다.


3) Traverse of Binary tree

이번 시간에는 간단하게 Binary tree의 원소들을 순회하는 세 가지 방법에 대해서 소개하도록 하겠습니다.

3-1. Construct

트리의 노드는 doubly linked list와 비슷하게 left node를 가리키는 포인터 + data + right node를 가리키는 포인터로 이루어져 있습니다.

class Node:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None
    def setData(self,data):
        self.data = data
    def setLeft(self,left):
        self.left = left
    def setRight(self,right):
        self.right = right
    def getData(self):
        return self.data
    def getLeft(self):
        return self.left
    def getRight(self):
        return self.right

그리고 Tree 클래스는 간단하게 구현했습니다. 데이터를 삽입하는 과정을 명시적으로 정의했습니다. (자동으로 삽입되는 장치는 다음 포스트인 Binary Search Tree에서 알아보겠습니다.)

class BinTree:
    def __init__(self,data):
        self.root = Node()
        self.root.setData(data)
    def append(self,data,direction,base):
        NewNode = Node()
        NewNode.setData(data)
         
        if direction == "->":
            base.setRight(NewNode)
            return base.getRight()
        elif direction == "<-":
            base.setLeft(NewNode)
            return base.getLeft()

tree = BinTree(1)
second = tree.append(2,"<-",tree.root)
third = tree.append(3,"->",tree.root)
fourth = tree.append(4,"<-",second)
fifth = tree.append(5,"->",second)

이렇게 트리 인스턴스를 선언하면 요런 모양의 트리가 만들어집니다.

3-2. Types of Traverses

대표적인 트리의 순회방식은 네 가지입니다.

  • Preorder Traversal : current node data -> left subtree -> right subtree
  • Inorder Traversal : left subtree -> current node data -> right subtree
  • Postorder Traversal : current node data -> right subtree -> left subtree
  • Level Order Traversal : Breath first search

Binary tree의 좋은 성질을 이용해서 level에 따른 재귀함수를 구성하는데, 이 경우에는 tree에 대한 재귀함수는 left subtree에 대한 재귀함수와 right subtree에 대한 재귀함수를 낳을 수 있습니다.

이러한 과정에서 root 데이터를 처리하는 순서만 다르다고 생각하시면 됩니다.

예를 들어서 Preorder Traversal은 current node data를 우선시하기 때문에 먼저 root를 프린트하고 그 다음에 left subtree에 대한 재귀함수를 쭈욱 호출한 다음에 right subtree에 대한 재귀함수를 쭉 호출하는 형식으로 이루어집니다.

함수는 매우 정직하기 때문에 먼저 만나는 함수가 끝날 때 까지 다음 함수를 실행하지 않습니다. 이러한 방식은 Stack의 FIFO(First In First Out) 방식과 매우 비슷하기 때문에 재귀함수의 논리를 스택으로 변환하기도 매우 쉽습니다.

(ex: Preorder Traversal, 1. root를 먼저 저장한다. 2. left child를 저장한다. 3. right child를 저장한다 4. 모두 끝나면 차례대로 들어올린다)


3-3 Implementation

def preorder(tree,base):
    print(base.getData(), end=" ")
    if base.getLeft():
        preorder(tree,base.getLeft())
    if base.getRight():
        preorder(tree,base.getRight())     

preorder(tree,tree.root)
>>> 1 2 4 5 3

def inorder(tree, base):
    if base.getLeft():
        inorder(tree,base.getLeft())
    print(base.getData(),end=" ")
    if base.getRight():
        inorder(tree,base.getRight())

inorder(tree,tree.root)
>>> 4 2 5 1 3

def postorder(tree, base):
    print(base.getData(),end=" ")
    if base.getRight():
        postorder(tree,base.getRight())  
    if base.getLeft():
        postorder(tree,base.getLeft())

postorder(tree,tree.root)
>>> 1 3 2 5 4

Level order Traversal은 BFS와 동일하므로 생략하겠습니다.

(Queue를 이용해서 같은 level의 원소를 순서대로 Enqueue하고 Dequeue할 때 마다 left subnode와 right subnode들을 다시 Enqueue하는 재귀함수로 쉽게 구성할 수 있습니다.

위의 알고리즘들과는 달리 child만 알고 있으면 되기 때문에 서브트리 전체를 필요로 하지 않습니다.)

comments powered by Disqus