[자료구조] Python으로 구현하는 자료구조 (3) Tree

이번에는 Tree와 BinaryTree에 대해서 알아보자.

출처 : 프로그래머스 어서와! 자료구조와 알고리즘은 처음이지?

 

Tree의 기본 용어

Tree는 그래프의 특이한 형태 중 하나이다. 수학적으로 정의하면 회로, 즉 순환되는 부분이 없고 두 노드를 연결하는 간선이 많아야 1개인 구조이다. 

사진을 통해 Tree의 예시 및 용어를 확인해보자.

설명을 위해 위키피디아의 트리 사진에 약간의 붙임을 달았다.

- A : 최상단의 노드로, 트리의 루트 라고 부른다.
- B와 C : B와 C를 부모 자식 관계라고 본다. B는 C의 부모 노드이다. C는 B의 자식 노드 중 하나이다.
- 노드의 차수란, 가지고 있는 자식의 수이다. A와 B의 경우는 차수가 2인 것이다.
- 자식이 하나도 없는 C의 경우는 말단 노드로 불린다.
- 트리의 레벨이 존재한다. 최상단 루트가 0으로 시작, 자식으로 갈때마다 레벨이 1씩 증가한다.
- 트리의 깊이는 최대 레벨 + 1이다.
- 트리의 크기는 전체 노드의 수이다.

 

이진트리(Binary Tree)

여러 트리가 있지만, 가장 간단하고 대표적인 예시 중 하나인 Binary Tree 에 대해 알아보고, 그 구현을 확인해보자.

Binary Tree란, 이진트리라는 말에서 보듯 각 노드별로 자식이 최대 2개가 존재하는 형태의 트리이다. 상단의 사진도 이진 트리의 하나의 예시가 된다.

이진트리에서 생각할 연산은 다음과 같다.

- 트리의 size를 반환한다.
- 트리의 depth를 반환한다.
- 트리 전체를 순회(traversal) 한다. 

기본 구조는 다음과 같다.

class Node:
	def __init__(self, item):
    	self.data = item
    	self.left = None
    	self.right = None
    
class BinaryTree:
    def __init__(self, r):
    	self.root = r

 

이진트리의 size 및 depth 연산

size와 depth의 경우는 재귀적으로 구현할 수 있다.

그 이유는, 한 노드에서 자식노드만 따라가 그 부분을 떼어 일부를 보면 다시 이진트리가 되는 재귀적 구조를 가지고 있기 때문이다.

size의 경우는, 좌측 자식과 우측 자식의 size를 더한 후 자기 자신도 더해야 하므로 1을 더하면 그만이고,
깊이의 경우는 최대 깊이를 따져야 하므로 더 깊이가 깊은 자식에 자기 자신, 즉 1을 더해서 구현한다.

BinaryTree class에서는 root가 있는지 없는지에 따라 이를 나눠서 구별하여 초기값을 지정하면 된다.

class Node:

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1


    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l, r) + 1


class BinaryTree:

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

 

이진트리의 순회

순회란, 트리 전체를 탐색하여  트리 내 전체 원소를 반환하는 연산이다. 트리의 순회는 크게 3가지이다.

(1) 전위 순회 : 자기 자신 -> 좌측 자식 -> 우측 자식 
(2) 중위 순회 : 좌측 자식 -> 자기 자신 -> 우측 자식
(3) 후위 순회 : 좌측 자식 -> 우측 자식 -> 자기 자신

트리의 예시를 통해 순회의 결과를 확인하자.

 

전위 : A B D G E H C F I J

중위 : G D B H E A C I F J

후위 : G D H E B I J F C A

트리를 통해 이를 탐사하는 코드를 알아보자.

알고리즘은 간단하다. 말 그대로, 좌측으로 들어가야 하는 경우는 자신의 좌측 자식이 있을 경우 traversal을 호출,
우측의 경우도 같은 방식으로 하면 되고 자기 자신을 보는 경우는 그대로 traversal의 기록에 append 시키면 그만이다.

이를 루트에서 출발시키면 된다.

예시로, 전위 순회에 대해서만 확인해보자.

class Node:

    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal


class BinaryTree:

    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

 

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는, 이진 탐색에 기반하여 만들어진 트리입니다. 이진 탐색 트리의 기본 전제조건은 다음과 같다.

(1) 모든 노드에 대해
    - 자신의 왼쪽 서브트리에 있는 모든 데이터는 자신의 데이터보다 작아야 한다.
    - 자신의 오른쪽 서브트리에 있는 모든 데이터는 자신의 데이터보다 커야 한다.

(2) 그러면서 당연히, 이진트리여야 한다.

(3) 중복된 값은 존재하지 않는다.

이를 항상 유지시켜줘야 한다.

이진탐색트리의 예시는 다음과 같다.  (그림판 재활용)

 

이진 탐색 트리에서 생각할 수 있는 연산들은 다음과 같다.

- lookup : 특정 원소가 있는지 검색한다.
- inorder : 키의 순서대로 데이터 원소를 나열한다.
- insert : 트리에 원소를 추가한다.
- remove : 트리에 원소를 삭제한다.

 

이진탐색 트리의 초기화

이진탐색 트리에 키와 데이터가 있다라고도 가정할 수 있을 것이다.
정확히는 data set이 키와 키에 할당하는 데이터가 들어가 있고, 키를 기준으로 탐색하는 것을 목적으로 한 자료를 고려해볼 수 있다. 여기서는 해당 상황을 가정하고 초기화를 하려 한다.

class Node:

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

class BinSearchTree:

    def __init__(self):
        self.root = None

 

이진탐색 트리의 삽입 연산

이진 탐색 트리의 삽입과 삭제는 그리 간단하지 않다. 그 이유는, 삽입과 삭제 후에도 가정을 유지시켜줘야 한다는 문제가 있기 때문이다.

이 말을 바꿔 말한다면, 삽입을 원하는 위치에 하는 것이 아니라, 알맞은 위치에 들어가도록 삽입해야 한다는 것이다.

삽입하는 방법에 대해 고려해보자.

(1) 루트 노드가 없으면 루트로 한다.

(2) 루트가 있으면 루트랑 비교, 삽입하려는 값이 더 크면 우측, 작으면 좌측으로 보낸다. 거기에 자식이 없는 상태면 그대로 삽입한다.

(3) 자식이 있으면 (2)의 과정을 다시 진행하여, 자식이 없는 자리가 나올 경우 그 자리에 넣고 이를 반복해도 자식이 다 있어서 넣을 수 없으면 입력할 수 없는 것이다.

코드를 통해 내용을 확인하면 다음과 같다.

class Node:

    def insert(self, key, data):
        if key < self.key:  # 입력값이 더 작아서
            if not self.left: # 좌측이 없으면
                self.left = Node(key, data) # 입력 끝
            else: # 있으면 좌로 가서 다시 insert 시도
                self.left.insert(key, data)
        elif key > self.key: # 입력값이 더 커서
            if not self.right: # 우측이 없으면
                self.right = Node(key, data) # 끝
            else: # 있으면 재시도
                self.right.insert(key, data)
        else:
            raise KeyError

class BinSearchTree:

    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else: # 하나도 없으면 루트로 넣어버린다.
            self.root = Node(key, data)

 

이진탐색 트리의 삭제 연산

삭제는 훨씬 어렵고 복잡하다. 프로그래머스 과정에서 과제로 나온 코드의 상세 주석으로 설명을 대신한다.

class Node:

def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent

    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None


    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if parent.left == node:
                        parent.left = None
                    elif parent.right == node:
                        parent.right = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
            # When the node has only one child
            elif nChildren == 1: 
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    target = node.left
                elif node.right:
                    target = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left == node:
                        parent.left = target
                    if parent.right == node:
                        parent.right = target
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = target
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right # 가장 근소한게 큰거 찾으려고 일단 옴
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:
                    parent = successor
                    successor = successor.left
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                if parent.left == successor:
                    parent.left = successor.right
                if parent.right == successor:
                    parent.right = successor.right

            return True

        else:
            return False


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0