[파이썬으로 배우는 자료구조] 트리(Tree)

트리(Tree)란?

 

트리는 노드(Node)와 엣지(Edge)로 구성되어 있습니다. 위 그림에서 원이 노드, 선이 엣지이고, 이를 이용해서 사이클(순환 구조)을 이루지 않도록 구성한 구조를 마치 나무 같다 하여 트리라고 불립니다. 사이클이 없어서 아래로만 뻗어나가고 계층적으로 표현됩니다.

 

용어

• 노드(Node): 트리에서의 개별 데이터
• 루트(Root): 트리 시작점에 있는 노드(최상위)
• 깊이(Depth): 루트를 기준으로 특정 노드까지의 깊이를 의미. 루트는 깊이가 0
• 높이(Height): 리프 노드를 기준으로 특정 노드까지의 높이를 의미. 리프 노드는 높이가 0
• 계층(Level): 트리에서 같은 깊이에 있는 노드들을 같은 계층에 있다고 함.
• 부모 노드(Parent Node): 어떤 노드와 이전 계층에서 연결된 노드
• 자식 노드(Child Node): 어떤 노드의 다음 계층에서 연결된 노드
• 리프 노드(Leaf Node): 자식 노드를 갖고 있지 않은 노드(최하위)
• 형제 노드(Sibling Node): 같은 부모 노드를 갖고 있는 노드
• 서브 트리(Sub Tree): 큰 트리 내부에서의 또다른 작은 트리 구조

 

특징

• 노드의 수에서 1을 뺀 값이 엣지의 수와 같음
• 사이클이 존재하지 않음
• 모든 노드는 서로 연결되어 있음
• 어떤 노드에서 다른 노드로 가는 경로는 유일함

 

---

이진트리(Binary Tree)

 

이진트리란 자식 노드가 최대 2개인 트리를 의미합니다. 위에 트리를 정의한 그림에서의 트리가 이진트리의 모습입니다. 재귀 호출의 특징을 사용하여 이진트리를 순회할 수 있습니다. 순회는 모든 노드를 체계적으로 방문하는 과정을 의미합니다. 기본적으로 트리의 순회는 왼쪽 자식 노드부터 뻗어나가는데 처리 순서에 따라서 전위 순회, 중위 순회, 후위 순회로 나뉩니다. 

 

순회

전위순회(preorder)

 

노드 처리 -> 왼쪽 자식 노드 탐색 -> 오른쪽 자식 노드 탐색

위 그림에서 보면 맨 처음 루트 노드에서의 본연의 일을 수행한 뒤 재귀 호출을 사용하여 그 후 왼쪽 자식 노드를 탐색하고, 왼쪽 자식 노드에서도 마찬가지로 일을 수행한 후 왼쪽 자식 노드를 탐색합니다. 이때 탐색된 노드는 1번 노드로 리프 노드가 됩니다. 리프 노드도 일을 수행한 후 마찬가지로 왼쪽 자식 노드를 탐색하는데 왼쪽 자식 노드가 없으므로 생략하고, 오른쪽 자식 노드를 탐색합니다. 하지만 오른쪽 자식 노드 또한 갖고 있지 않기 때문에 탐색은 끝나게 됩니다.  1번 노드에서 수행해야 할 일이 끝났으므로 메모리 스택에서 해당 함수는 없어지고, 리턴 주소로 돌아가게 됩니다.

 

재귀 호출 참고) 2022.07.05 - [알고리즘(파이썬)/개념] - [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

[파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

이때 리턴 주소는 3번 노드에서 1번 노드를 호출한 다음입니다. 3번 노드에서는 왼쪽 자식 노드 탐색이 끝났으므로 오른쪽 자식 노드를 탐색하고, 이 과정을 반복하면 전위 순회가 완료됩니다.

 

해당 트리에서 전위 순회에서의 처리 순서는 6 -> 3 -> 1 -> 5 -> 8 -> 7 -> 9

 

def preorder(node):
	if node != 0:
    	#본연의 일 여기서는 순서를 알기 위해 간단히 출력
    	print(node.value)
        #왼쪽 자식 노드 탐색
        preorder(node.left)
        #오른쪽 자식 노드 탐색
        preorder(node.right)

 

 

 

중위 순회(Inorder)

 

왼쪽 자식 노드 탐색 -> 노드 처리 -> 오른쪽 자식 노드 탐색

 

중위 순회는 자신 노드에서의 일을 수행하기 전에 왼쪽 자식 노드를 먼저 탐색하기 때문에 3번 노드를 이어 1번 리프 노드까지 탐색을 하게 됩니다. 1번 노드는 왼쪽 자식 노드를 갖고 있지 않으므로 생략하고, 일을 수행하게 됩니다. 오른쪽 자식 노드도 마찬가지로 자식 노드를 갖고 있지 않기 때문에 일 수행만 하고 탐색 없이 함수가 종료되고, 리턴 주소로 돌아가게 됩니다. 3번 노드는 왼쪽 자식 노드를 탐색한 후이기 때문에 자신 노드의 일을 한 후 오른쪽 자식 노드를 탐색합니다. 5번 노드도 리프 노드이므로 일을 한 후 함수가 종료되면 리턴 주소로 3번 노드로 가고 3번 노드도 탐색을 마쳤으므로 종료됩니다. 이 과정을 반복하면 중위 순회가 완료됩니다.

 

해당 트리에서 중위 순회에서의 처리 순서는 1 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9

 

def inorder(node):
	if node != 0:
        #왼쪽 자식 노드 탐색
        inorder(node.left)
        #본연의 일 여기서는 순서를 알기 위해 간단히 출력
    	print(node.value)
        #오른쪽 자식 노드 탐색
        inorder(node.right)

 

후위 순회(postorder)

 

왼쪽 자식 노드 탐색 -> 오른쪽 자식 노드 탐색 -> 노드 처리

 

후위 순회는 왼쪽 자식 노드 탐색과 오른쪽 자식 노드 탐색 후 자신 노드의 일을 합니다. 3번 노드가 처리되기 위해서는 1번 노드와 5번 노드를 탐색한 후에 자신의 일을 할 수 있습니다. 위의 그래프를 보고 전위 순회, 중위 순회와 마찬가지로 순서를 보면서 이해하면 빠를 겁니다!

 

해당 트리에서 후위 순회에서의 처리 순서는 1 -> 5 -> 3 -> 7 -> 9 -> 8 -> 6

 

def postorder(node):
	if node != 0:
        #왼쪽 자식 노드 탐색
        postorder(node.left)
        #오른쪽 자식 노드 탐색
        postorder(node.right)
        #본연의 일 여기서는 순서를 알기 위해 간단히 출력
    	print(node.value)

 

이진 트리 종류

 

• 완전 이진트리(Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있는 트리 구조입니다. 마지막 레벨에서의 노드 또한 완전히 채워져 있지 않아도 왼쪽에서 오른쪽의 순서로 노드가 채워져야 합니다.

 

• 전 이진트리(Full Binary Tree)

모든 노드가 0~2개의 자식 노드를 갖는 트리 구조입니다.

 

• 포화 이진트리(Perfect Binary Tree)

모든 레벨의 노드가 완전히 채워져 있는 트리 구조입니다. 트리의 높이를 h라고 한다면 노드 개수가 정확히 2^(h+1) - 1개입니다.

 

---

이진 탐색 트리

 

 이진 탐색 트리는 이진트리의 특수한 경우로 다음과 같은 조건을 갖고 있습니다.

• 왼쪽 자식 노드의 값이 자신 노드의 값보다 작음
• 오른쪽 자식 노드의 값이 자신 노드의 값보다 큼
• 중복된 값은 들어올 수 없음

이러한 조건으로 이진 탐색 트리는 보통 구조가 단순하면서 빠르게 탐색이 가능합니다. 이진 탐색 트리의 시간 복잡도는 트리의 높이에 비례하게 됩니다. 최대 루트 노드부터 리프 노드까지 탐색하기 때문이죠. 따라서 시간 복잡도는 O(h)이고, 최적인 상황인 포화 이진 탐색 트리에서 시간 복잡도는 노드의 개수를 N이라고 했을 때 O(logN)입니다.

 

---

이진 탐색 트리 구현

 

insert 함수

def insert(self, value):
        #루트
        if self.head is None:
            self.head = Node(value)
        else:
            #루트부터 검사
            node = self.head

            while True:
                # 값이 더 작은 경우 왼쪽 서브 트리로
                if value < node.getvalue():
                    # 노드의 왼쪽 자식 노드가 없으면
                    if node.getleft() is None:
                        # 왼쪽 자식 노드로 저장
                        node.setleft(Node(value))
                        break
                    # 노드의 왼쪽 자식 노드가 있으면
                    else:
                        # 현재 노드를 왼쪽 자식 노드로
                        node = node.left
                # 값이 더 큰 경우 오른쪽 서브 트리로
                else:
                    if node.getright() is None:
                        node.setright(Node(value))
                        break
                    else:
                        node = node.right

이진 탐색 트리에 노드를 추가하는 함수입니다. 왼쪽 서브 트리는 자신의 노드 값보다 작은 값을 가진 노드가 저장되고, 오른쪽 서브 트리는 자신의 노드 값보다 큰 값을 노드가 저장된다는 것을 이용하여 코드를 구현했습니다.

 

delete 함수

def delete(self, value):
        # 루트 노드가 없음
        if self.head is None:
            return False

        node = self.head
        parent = self.head
        check = False

        while node:
            if value == node.getvalue():
                check = True
                break
            else:
                parent = node
                if value < node.getvalue():
                    node = node.getleft()
                else:
                    node = node.getright()

        if not check:
            return False

        # Case1: 찾은 노드의 자식 노드가 없는 경우
        if node.getleft() is None and node.getright() is None:
            # 부모 노드의 값보다 작은 경우 부모 노드의 왼쪽 자식 노드이므로
            if value < parent.getvalue():
                parent.setleft(None)
            else:
                parent.setright(None)

        # Case2: 찾은 노드의 자식 노드가 한개일 경우
        # 왼쪽 자식 노드만 있는 경우
        elif node.getleft() and node.getright() is None:
            # 값이 부모 노드의 값보다 작으면 그 하위 노드들의 값도 부모 노드보다 작으므로 
            # 부모 노드의 왼쪽 자식 노드는 삭제 되는 노드의 왼쪽 자식 노드가 된다.
            if value < parent.getvalue():
                parent.setleft(node.getleft())
            else:
                parent.setright(node.getleft())
        # 오른쪽 자식 노드만 있는 경우
        elif node.getleft() is None and node.getright():
            if value < parent.getvalue():
                parent.setleft(node.getright())
            else:
                parent.setright(node.getright())

        # Case3: 찾은 노드의 자식 노드가 두개일 경우
        elif node.getleft() and node.getright():
            current, child = node, node.getright()
            
            # 삭제하고자 하는 노드 아래 오른쪽 서브트리에서 제일 왼쪽 자식 노드를 찾음
            # 제일 왼쪽 자식 노드는 삭제하고자 하는 노드의 왼쪽 서브트리의 모든 노드보다
            # 값은 크고 오른쪽 서브트리의 모든 노드보다 값이 작으므로
            # 삭제하고자 하는 노드 자리에 적합
            while child.getleft():
                current, child = child, child.getleft()
                
            # 삭제하고자 하는 노드에 값 저장
            node.setvalue(child.getvalue())

            if current != node:
                # 삭제된 자리에 이동한 노드의 오른쪽 자식 노드가 있으면
                # 원래의 부모 노드의 왼쪽 자식 노드로 설정
                if child.getright():
                    current.setleft(child.getright())
                else:
                    current.setleft(None)
            else:
                node.setright(child.getright())
        return True

 

특정 값을 가진 노드를 삭제하는 delete 함수입니다. 노드를 삭제하는데 크게 세 가지 경우로 나눌 수 있습니다.

 

Case 1) 삭제되는 노드의 자식 노드가 없는 경우

 삭제되는 노드의 자식 노드가 없는 경우에는 단순히 부모 노드에서 삭제되는 노드의 연결을 끊어주면 됩니다. 

 

Case2) 삭제되는 노드의 자식 노드가 한 개인 경우

 

 

삭제되는 노드의 자식 노드가 한 개인 경우에는 삭제되는 노드의 부모 노드와 자식 노드를 연결해줘야 합니다. 삭제되는 노드가 부모 노드의 오른쪽 자식 노드였을 경우 자식 노드를 오른쪽 자식 노드로 저장하고, 왼쪽 자식 노드였을 경우도 마찬가지로 적용합니다.

 

Case3) 삭제되는 노드의 자식  노드가 두 개인 경우

가장 까다로운 두 개의 자식 노드를 갖고 있는 노드를 삭제하는 경우입니다. 삭제되는 노드의 오른쪽 서브 트리에서 제일 왼쪽 자식 노드가 삭제되는 노드의 왼쪽 서브 트리에 있는 노드의 값보다 크고 오른쪽 서브 트리에서는 제일 작으므로 이 노드 값을 삭제되는 노드 자리에 저장해줍니다.

 

show, print_tree 함수

def show(self, node, option):
        if node is None:
            return
        # 전위 순회
        if option == 1:
            print(node.value, end =' ')
            self.show(node.getleft(), option)
            self.show(node.getright(), option)
        # 중위 순회
        elif option == 2:
            self.show(node.getleft(), option)
            print(node.value, end =' ')
            self.show(node.getright(), option)
        # 후위 순회
        else:
            self.show(node.getleft(), option)
            self.show(node.getright(), option)
            print(node.value, end =' ')

def print_tree(self, option = 1):
        if option == 1:
            print('preorder:', end=' ')
        elif option == 2:
            print('inorder:', end=' ')
        else:
            print('postorder:', end=' ')
        self.show(self.head, option)
        print()

트리를 option에 따라 전위 순회, 중위 순회, 후위 순회하여 출력할 수 있습니다.

 

전체 코드

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

    def setleft(self, node):
        self.left = node

    def setright(self, node):
        self.right = node

    def setvalue(self, value):
        self.value = value

    def getleft(self):
        return self.left

    def getright(self):
        return self.right

    def getvalue(self):
        return self.value

class BinarySearchTree:
    def __init__(self):
        #루트
        self.head = None
            
    def search(self, value):
        if self.head is None:
            return False, None

        # 해당 값이 있는 노드의 깊이
        depth = 0
        node = self.head

        while node:
            if value == node.getvalue():
                return True, depth
            else:
                if value < node.getvalue():
                    node = node.getleft()
                else:
                    node = node.getright()
            depth += 1

        return False, None

    def show(self, node, option):
        if node is None:
            return
        # 전위 순회
        if option == 1:
            print(node.value, end =' ')
            self.show(node.getleft(), option)
            self.show(node.getright(), option)
        # 중위 순회
        elif option == 2:
            self.show(node.getleft(), option)
            print(node.value, end =' ')
            self.show(node.getright(), option)
        # 후위 순회
        else:
            self.show(node.getleft(), option)
            self.show(node.getright(), option)
            print(node.value, end =' ')

    def print_tree(self, option = 1):
        if option == 1:
            print('preorder:', end=' ')
        elif option == 2:
            print('inorder:', end=' ')
        else:
            print('postorder:', end=' ')
        self.show(self.head, option)
        print()

    def insert(self, value):
        #루트
        if self.head is None:
            self.head = Node(value)
        else:
            #루트부터 검사
            node = self.head

            while True:
                # 값이 더 작은 경우 왼쪽 서브 트리로
                if value < node.getvalue():
                    # 노드의 왼쪽 자식 노드가 없으면
                    if node.getleft() is None:
                        # 왼쪽 자식 노드로 저장
                        node.setleft(Node(value))
                        break
                    # 노드의 왼쪽 자식 노드가 있으면
                    else:
                        # 현재 노드를 왼쪽 자식 노드로
                        node = node.left
                # 값이 더 큰 경우 오른쪽 서브 트리로
                else:
                    if node.getright() is None:
                        node.setright(Node(value))
                        break
                    else:
                        node = node.right

    def delete(self, value):
        # 루트 노드가 없음
        if self.head is None:
            return False

        node = self.head
        parent = self.head
        check = False

        while node:
            if value == node.getvalue():
                check = True
                break
            else:
                parent = node
                if value < node.getvalue():
                    node = node.getleft()
                else:
                    node = node.getright()

        if not check:
            return False

        # Case1: 찾은 노드의 자식 노드가 없는 경우
        if node.getleft() is None and node.getright() is None:
            # 부모 노드의 값보다 작은 경우 부모 노드의 왼쪽 자식 노드이므로
            if value < parent.getvalue():
                parent.setleft(None)
            else:
                parent.setright(None)

        # Case2: 찾은 노드의 자식 노드가 한개일 경우
        # 왼쪽 자식 노드만 있는 경우
        elif node.getleft() and node.getright() is None:
            # 값이 부모 노드의 값보다 작으면 그 하위 노드들의 값도 부모 노드보다 작으므로 
            # 부모 노드의 왼쪽 자식 노드는 삭제 되는 노드의 왼쪽 자식 노드가 된다.
            if value < parent.getvalue():
                parent.setleft(node.getleft())
            else:
                parent.setright(node.getleft())
        # 오른쪽 자식 노드만 있는 경우
        elif node.getleft() is None and node.getright():
            if value < parent.getvalue():
                parent.setleft(node.getright())
            else:
                parent.setright(node.getright())

        # Case3: 찾은 노드의 자식 노드가 두개일 경우
        elif node.getleft() and node.getright():
            current, child = node, node.getright()
            
            # 삭제하고자 하는 노드 아래 오른쪽 서브트리에서 제일 왼쪽 자식 노드를 찾음
            # 제일 왼쪽 자식 노드는 삭제하고자 하는 노드의 왼쪽 서브트리의 모든 노드보다
            # 값은 크고 오른쪽 서브트리의 모든 노드보다 값이 작으므로
            # 삭제하고자 하는 노드 자리에 적합
            while child.getleft():
                current, child = child, child.getleft()
                
            # 삭제하고자 하는 노드에 값 저장
            node.setvalue(child.getvalue())

            if current != node:
                # 삭제된 자리에 이동한 노드의 오른쪽 자식 노드가 있으면
                # 원래의 부모 노드의 왼쪽 자식 노드로 설정
                if child.getright():
                    current.setleft(child.getright())
                else:
                    current.setleft(None)
            else:
                node.setright(child.getright())
        return True

if __name__ == "__main__":
    bst = BinarySearchTree()
    bst.insert(6)
    bst.insert(3)
    bst.insert(8)
    bst.insert(5)
    bst.insert(1)
    bst.insert(7)
    bst.insert(9)
    bst.print_tree(1)
    bst.print_tree(2)
    bst.print_tree(3)

    v = 7
    r = bst.search(v)
    if r[0]:
        print('depth of', str(v)+':', r[1])
    else:
        print('There is no', v)

    v = 6
    r = bst.delete(v)
    if r:
        print(v, 'is deleted')
    else:
        print('There is no', v)

    bst.print_tree()

실행 결과

---