트리(Tree)

2019-04-12

트리(Tree)

트리의 정의
- 트리는 connected(연결된) acyclic(순환되지 않는) gragh
- 루트(root) 노드를 반드시 가진다.(부모가 없는 노드)
- 트리는 하나의 루트 노드만을 가진다.
- 트리를 구성하는 노드 간에 단순 경로가 존재
  - 단순 경로(Simple Path) : 왔던 곳을 다시 거치지 않고 가는 것
- 1개 이상의 노드로 이루어진 유한 집합
- 나머지 노드들은 서브 트리로 분할 가능
관련 용어
- 차수(degree)
  - 해당 노드의 자식 노드 개수
- 트리의 차수(degree of a tree)
  - 트리에 있는 노드의 최대 차수
  - 차수 중에 최대 차수
- 리프 노드(leaf node)
  - 차수가 0인 노드, 즉 자식이 없는 노드
  - 단말 노드(terminal node)라고도 부름
- 레벨(level)
  - 루트의 레벨을 1로 하고 자식으로 내려가면서 하나씩 더함
  - 루트 레벨의 시작을 0으로 하기도 함
- 트리의 높이(height) or 깊이(depth)
  - 트리가 가지는 최대 레벨
- 포레스트(forest)
  - 루트 노드를 없앤 서브 트리들의 집합
- 에지(edge)
  - 노드와 노드를 잇는 간선
- 인터널 노드(internal node)
  - 리프 노드가 아닌 노드

노드와 에지의 관계

노드의 개수 = n
에지의 개수 = e

>> e = n - 1

이진 트리(binary tree)

어떤 노드의 자식 노드의 수가 최대 2개인 트리
루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 이루어진 유한 집합
서브 트리도 모두 이진 트리
특징
1. 레벨 a에서 최대 노드 수: 2^(a-1)
  1
  ex) Level 3에서의 최대 노드 수 : 2^(3-1) = 4
2. 높이가 h인 이진 트리의 최대 노드 수 : 2^h - 1
  1
  ex) 트리의 높이가 3이면 2^3 - 1 = 7
3. 높이가 h인 이진 트리의 최소 노드 수 : h개
  1
  ex) 트리의 높이가 3이면 최소 노드 수도 3
이진 트리의 종류
- 포화 이진 트리(full binary tree)
  - 모든 레벨이 꽉 차 있는 트리
- 완전 이진 트리(complete binary tree)
  - 위에서 아래로, 왼쪽에서 오른쪽으로 채워져있는 트리
- 편향 이진 트리(skewed binary tree)
  - 왼쪽이나 오른쪽 서브 트리만 가지는 트리

순회(traversal)

재방문을 허용하지 않고 트리를 구성하는 모든 노드에 다해서 반드시 한번씩 방문하는 것

Stack 계열의 알고리즘
- DFS(Depth First Search) : 깊이 우선 탐색
- 재귀(recursion)와 반복문, stack 자료구조를 통한 구현 - stack frame
  - 전위 순회(preorder traversal)
    - root -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
  - 중위 순회(inorder traversal)
    - 왼쪽 서브 트리 -> root -> 오른쪽 서브 트리
  - 후위 순회(postorder traversal)
    - 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> root
Queue 계열의 알고리즘
- BFS(Breadth First Search) : 너비 우선 탐색
  - 레벨 순서 순회(levelorder traversal)
    - root를 시작으로 다음 레벨 왼쪽부터 방문

Coding Practice

Linked List를 이용한 Stack과 Queue를 적용하여 이진 트리 및 BST 구현

Linked List를 이용한 Stack과 Queue

class Node:
    def __init__(self, data=None):
        self.__data = data
        self.__next = None
        
    @property
    def data(self):
        return self.__data
    
    @data.setter
    def data(self, data):
        self__data = data
        
    @property
    def next(self):
        return self.__next
    
    @next.setter
    def next(self, n):
        self.__next = n

# Linked List를 통한 Stack 구현

class LStack:
    def __init__(self):
        self.top = None
        
    def empty(self):
        if self.top is None:
            return True
        else:
            return False
        
    def push(self, data):
        new_node = Node(data)
        
        new_node.next = self.top
        self.top = new_node
    
    def pop(self):
        if self.empty():
            return
        
        cur = self.top
        
        self.top = self.top.next
        
        return cur.data
    
    def peek(self):
        if self.empty():
            return
        
        return self.top.data

# Linked List를 통한 Queue 구현

class LQueue:
    def __init__(self):
        self.front  = None
        self.rear = None
        
    def empty(self):
        if self.front is None:
            return True
        else:
            return False
        
    def enqueue(self, data):
        new_node = Node(data)
        
        if self.empty():
            self.front = new_node
            self.rear = new_node
            return
        
        self.rear.next = new_node
        self.rear = new_node
        
    def dequeue(self):
        if self.empty():
            return
        
        if self.front is self.rear:
            self.rear = self.rear.next
            
        cur = self.front
        self.front = self.front.next
        return cur.data
    
    def peek(self):
        if self.empty():
            return
        
        return self.front.data

Binary Tree 구현

class TreeNode:
    def __init__(self, data):
        self.__data = data
        self.__left = None  # 노드의 왼쪽
        self.__right = None # 노드의 오른쪽
        
    @property
    def data(self):
        return self.__data
    
    @data.setter
    def data(self, data):
        self.__data = data
    
    @property
    def left(self):
        return self.__left
    
    @left.setter
    def left(self, left):
        self.__left = left
    
    @property
    def right(self):
        return self.__right
    
    @right.setter
    def right(self, right):
        self.__right = right
        

# DFS
# recursion을 통한 구현
# 전위 순회
def preorder(cur):
    # base case
    if not cur:
        return
    
    # 방문했다는 것을 데이터로 출력하여 표현
    # root node부터 cur 방문
    print(cur.data, end = ' ')
    preorder(cur.left)
    preorder(cur.right)
    
# 중위 순회
def inorder(cur):
    # base case
    if not cur:
        return
    
    # root node를 중간에 방문
    inorder(cur.left)
    print(cur.data, end = ' ')
    inorder(cur.right)
    
# 후위 방문
def postorder(cur):
    # base case
    if not cur:
        return
    
    # root node를 끝에 방문
    postorder(cur.left)
    postorder(cur.right)
    print(cur.data, end = ' ')
    

# 반복문 + stack을 통한 구현
# 전위 순회
def iter_preorder(cur):
    stack = LStack()
    
    while True:
        while cur:
            print(cur.data, end = ' ')
            stack.push(cur)
            cur = cur.left
        cur = stack.pop()
        if not cur:
            break
        cur = cur.right
        
# 중위 순회
def iter_inorder(cur):
    stack = LStack()
    
    while True:
        while cur:
            stack.push(cur)
            cur = cur.left
        cur = stack.pop()
        if not cur:
            break
        print(cur.data, end = ' ')
        cur = cur.right
        
# 후위 순회
def iter_postorder(cur):
    s1 = LStack()
    s2 = LStack()
    
    s1.push(cur)
    while not s1.empty():
        cur = s1.pop()
        s2.push(cur)
        
        if cur.left:
            s1.push(cur.left)
            
        if cur.right:
            s1.push(cur.right)
            
    while not s2.empty():
        cur = s2.pop()
        print(cur.data, end = ' ')
        
# BFS
# Queue를 이용한 구현
def levelorder(cur):
    queue = LQueue()
    
    queue.enqueue(cur)
    while not queue.empty():
        cur = queue.dequeue()
        print(cur.data, end = ' ')
        
        if cur.left:
            queue.enqueue(cur.left)
            
        if cur.right:
            queue.enqueue(cur.right)


if __name__ == '__main__':

    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n6 = TreeNode(6)
    n7 = TreeNode(7)
    
    n1.left = n2; n1.right = n3
    n2.left = n4; n2.right = n5
    n3.left = n6; n3.right = n7
    
    print('preorder :')
    preorder(n1)
    print("\n")

    print('inorder :')
    inorder(n1)
    print("\n")

    print('postorder :')
    postorder(n1)
    print("\n")

    print('iter_preorder :')
    iter_preorder(n1)
    print("\n")

    print('iter_inorder :')
    iter_inorder(n1)
    print("\n")

    print('iter_postorder :')
    iter_postorder(n1)
    print("\n")

    print('levelorder :')
    levelorder(n1)

>> preorder :
   1 2 4 5 3 6 7

   inorder :
   4 2 5 1 6 3 7

   postorder :
   4 5 2 6 7 3 1

   iter_preorder :
   1 2 4 5 3 6 7

   iter_inorder :
   4 2 5 1 6 3 7

   iter_postorder :
   4 5 2 6 7 3 1

   levelorder :
   1 2 3 4 5 6 7

BST 구현

class TreeNode:
    def __init__(self, key):
        self.__key = key  # data가 아닌 key 값을 기준으로 함
        self.__left = None
        self.__right = None

    def __del__(self):
        print(f'deleted data : {self.__key}')

    @property
    def key(self):
        return self.__key

    @key.setter
    def key(self, key):
        self.__key = key

    @property
    def left(self):
        return self.__left

    @left.setter
    def left(self, left):
        self.__left = left

    @property
    def right(self):
        return self.__right

    @right.setter
    def right(self, right):
        self.__right = right
        

class BST:
    def __init__(self):
        self.root = None
        
    def get_root(self):
        return self.root
    
    def preorder(self, cur, func):   # 전위 순회를 사용
        if not cur:
            return
        
        func(cur)
        self.preorder(cur.left, func)
        self.preorder(cur.right, func)
        
    def insert(self, key):
        new_node = TreeNode(key)
        
        cur = self.root
        
        if not cur:
            self.root = new_node
            return
        
        while True:
            par = cur
            if key < cur.key:
                cur = cur.left
                if not cur:
                    par.left = new_node
                    return
                
            else:
                cur = cur.right
                if not cur:
                    par.right = new_node
                    return
                
    def search(self, target):
        cur = self.root
        
        while cur:
            if target == cur.key:
                return cur
            elif target < cur.key:
                cur = cur.left
            else:
                cur = cur.right
                
        return cur
    
    def __remove_recursion(self, cur, target):
        # base case 1
        if not cur:
            return None, None
        elif target < cur.key:
            cur.left, rem = self.__remove_recursion(cur.left, target)
        elif target > cur.key:
            cur.right, rem = self.__remove_recursion(cur.right, target)
        # 지우려는 노드를 찾음
        else:
            # 삭제 노드가 리프 노드일 때
            if not cur.left and not cur.right:
                rem = cur
                cur = None
            # 삭제 노드가 자식이 하나일 때 : 왼쪽 자식이 있을 때
            elif not cur.right:
                rem = cur
                cur = cur.left
            # 삭제 노드가 자식이 하나일 때 : 오른쪽 자식이 있을 때
            elif not cur.left:
                rem = cur
                cur = cur.right
            # 삭제 노드가 자식이 둘일 때:
            else:
                replace = cur.left
                while replace.right:
                    replace = replace.right
                # 삭제 노드의 키와 대체 노드의 키를 교환
                cur.key, repplace.key = replace.key, cur.key
                cur.left, rem = self.__remove_recursion(cur.left, replace.key)
        return cur, rem
    
    def remove(self, target):
        self.root, removed = self.__remove_recursion(self.root, target)
        
        if removed:
            removed.left = removed.right = None
        return removed

if __name__ == '__main__':

    print('*'*100)
    
    bst = BST()
    
    bst.insert(6)
    bst.insert(3)
    bst.insert(2)
    bst.insert(4)
    bst.insert(5)
    bst.insert(8)
    bst.insert(10)
    bst.insert(9)
    bst.insert(11)
    
    f=lambda x: print(x.key, end='  ')

    bst.preorder(bst.get_root(), f)

    print()

    print('searched key : {}'.format(bst.search(8).key))

    bst.remove(9)
    #bst.remove(8)
    #bst.remove(6)

    bst.preorder(bst.get_root(), f)

    print()

    print('*'*20)

>> ******************************
   6  3  2  4  5  8  10  9  11
   searched key : 8
   deleted data : 6
   5  3  2  4  8  10  9  11
   ******************************
   deleted data : 5
   deleted data : 3
   deleted data : 2
   deleted data : 4
   deleted data : 8
   deleted data : 10
   deleted data : 9
   deleted data : 11

지눅쿠의 개발 블로그

StudyPython and CE

트리(Tree)

트리(Tree)

이진 트리(binary tree)

순회(traversal)

Coding Practice