[Tree] 이진 탐색 트리 구현하기 - 1

이진 탐색 트리의 자세한 개념은 이 블로그를 참고하자. 구현은 이 블로그, 블로그를 참고했다.

이진트리 개념을 익히고 실제로 내가 설계를 해서 직접 구현까지 해야 할 예정이다. 이번 포스팅은 개념을 익히기 위한 포스팅이다.

1. Node Class

Node 클래스의 구현 코드는 다음과 같다

class Node:
    def __init__(self, value):
        # double linked list
        self.value = value
        self.left = None
        self.right = None

이진 탐색 트리의 노드는 Linked List 속성을 지니고 있으므로 현재 노드를 기준으로 왼쪽과 오른쪽 자식 노드를 가진다.

2. 이진 탐색 트리

2.1 삽입

class NodeMgmt:
    def __init__(self, head):
        self.head = head  # 루트노드

    # 삽입
    def insert(self, value):
        self.current_node = self.head
        while True:
        	if value == self.current_node.value:  # 추가하려는 노드가 있다면 즉시 중단
                    break
            if value < self.current_node.value:
                if self.current_node.left != None:  # 이미 가지고 있다면
                    self.current_node = self.current_node.left  # 비교대상을 바꾼다.
                else:
                    self.current_node.left = Node(value)  # 없다면 새로 만들어 연결시킨다.
                    break
            else:
                if self.current_node.right != None:  # 이미 가지고 있다면
                    self.current_node = self.current_node.right  # 비교대상을 바꾼다.
                else:
                    self.current_node.right = Node(value)
                    break

    # 이진 탐색 트리 출력
    def search(self, value):
        self.current_node = self.head

        while self.current_node:
            if self.current_node.value == value:  # 찾았다
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left  # 비교대상 바꾸기
            else:
                self.current_node = self.current_node.right  # 비교대상 바꾸기
        return False  # 다 찾아봤는데 없다.

2.2 삭제

    def delete(self, value):
        # 삭제할 노드 탐색
        self.current_node = self.head  # 삭제할 노드
        self.parent = self.head  # 삭제할 노드의 부모 노드

        # 일단 해당 노드가 있는지를 찾는다
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.curent_node = self.current_node.left  # 비교대상 변경
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right  # 비교대상 변경

        if searched == False:  # 그런 값을 가진 노드가 없다 = 삭제할 노드가 없다
            return False

        ## 해당노드를 찾았다. 이제 삭제를 하자!
        # case1
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        # case2
        # 왼쪽 노드만 가지고 있다.
        elif self.current_node.left != None and self.current_node.right == None:
            # 삭제할 노드가 parent의 오른쪽에 있냐 왼쪽에 있냐
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        # 오른쪽 노드만 가지고 있다.
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

        # case3 : 삭제할 노드가 두개의 자식을 가진다
        if self.current_node.left != None and self.current_node.right != None:

            # case3-1 : 삭제할 노드가 부모 노드의 왼쪽에 있다
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right

                # 가장 작은값은 무조건 left에 있다 = 일단 left 끝까지 가게
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                self.change_node = self.change_node.left

                # 3-1-2
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-1-1
                    self.change_node_parent.left = None

                # 위로 옮기기
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            # case3-2 : 삭제할 노드가 부모 노드의 오른쪽에 있다
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.chage_node = self.change_node.left  # 비교 대상 변경
                # 3-2-2
                if self.chage_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-2-1
                    self.change_node_parent.left = None

                # 위로 옮긴다.
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.chage_node.right = self.current_node.right

2.3 순회

트리 순회란 트리의 노드를 지정한 순서대로 방문하는 것을 뜻한다. 이진 트리를 순회하는 방법은 대표적으로 3 가지이다. 여기에 한 가지를 더해 총 4 가지를 구현해보자

전위 순회 (Preorder)
후위 순회 (Postorder)
중위 순회 (Inorder)
레벨 순회 (Levelorder)

트리를 읽을 때에 대전제는 왼쪽부터 오른쪽으로 읽는다는 것이다. 오른쪽에서부터 왼쪽으로는 읽지 않는다. 여기서 “방문”은 자신의 번호를 출력하는 print() 함수로 표현한다. 이 출력 함수의 위치에 따라서 트리를 순회하는 방법을 구분하는 것이다

2.3.1 전위 순회(Pre Order)

자기 자신을 먼저 출력하고 자식 노드를 호출한다. 순서는 다음과 같다.

자기 자신 출력
왼쪽 서브트리 호출
오른쪽 서브트리 호출

    # 전위 순회
    def preorder(self, n):
        if n != None:
            print(n.item, '', end='') # 노드 방문
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

2.3.2 중위 순회(In Order)

자기 자신 출력이 중간에 있다.

왼쪽 서브트리 호출
자기 자신 호출
오른쪽 서브트리 호출

    # 중위 순회
    def inorder(self, n):
        if n != None:
            if n.left:
                self.inorder(n.left)
            print(n.item, '', end='') # 노드 방문
            if n.right:
                self.inorder(n.right)

2.3.3 후위 순회(Post Order)

자기 자신 출력을 가장 나중에 한다.

왼쪽 서브트리 호출
오른쪽 서브트리 호출
자기 자신 출력

    # 후위 순회
    def postorder(self, n):
        if n != None:
            if n.left:
                self.postorder(n.left)
            if n.right:
                self.postorder(n.right)
            print(n.item, '', end='') # 노드 방문

2.3.4 레벨 순회 (Level Order)

레벨 순회는 깊이(레벨) 단위로 출력하는 것이다. 그 순서는 깊이가 낮은 순서이다.

우리가 흔히 생각하는 10 20 30 40 50 60 70 80 순으로 출력하고 싶다면 어떻게 해야할까?

호출될 때마다 자식 노드를 따로 저장하는 것이다.

선입선출 구조인 큐로 구현한다.

    # 레벨 순회
    def levelorder(self, n):
        q = []
        q.append(n)
        while q:
            t = q.pop(0)
            print(t.item, '', end='')
            if t.left != None:
                q.append(t.left)
            if t.right != None:
                q.append(t.right)

전체 코드

class Node:
    def __init__(self, value):
        # double linked list
        self.value = value
        self.left = None
        self.right = None


class NodeMgmt:
    def __init__(self, head):
        self.head = head  # 루트노드
        
    # 트리 높이
    def height(self, root):
        if root == None:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1

    # 삽입
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:  # 이미 가지고 있다면
                    self.current_node = self.current_node.left  # 비교대상을 바꾼다.
                else:
                    self.current_node.left = Node(value)  # 없다면 새로 만들어 연결시킨다.
                    break
            else:
                if self.current_node.right != None:  # 이미 가지고 있다면
                    self.current_node = self.current_node.right  # 비교대상을 바꾼다.
                else:
                    self.current_node.right = Node(value)
                    break

    # 이진 탐색 트리 출력
    def search(self, value):
        self.current_node = self.head

        while self.current_node:
            if self.current_node.value == value:  # 찾았다
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left  # 비교대상 바꾸기
            else:
                self.current_node = self.current_node.right  # 비교대상 바꾸기
        return False  # 다 찾아봤는데 없다.


    def delete(self, value):
        # 삭제할 노드 탐색
        self.current_node = self.head  # 삭제할 노드
        self.parent = self.head  # 삭제할 노드의 부모 노드

        # 일단 해당 노드가 있는지를 찾는다
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.curent_node = self.current_node.left  # 비교대상 변경
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right  # 비교대상 변경

        if searched == False:  # 그런 값을 가진 노드가 없다 = 삭제할 노드가 없다
            return False

        ## 해당노드를 찾았다. 이제 삭제를 하자!
        # case1
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        # case2
        # 왼쪽 노드만 가지고 있다.
        elif self.current_node.left != None and self.current_node.right == None:
            # 삭제할 노드가 parent의 오른쪽에 있냐 왼쪽에 있냐
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        # 오른쪽 노드만 가지고 있다.
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right

        # case3 : 삭제할 노드가 두개의 자식을 가진다
        if self.current_node.left != None and self.current_node.right != None:

            # case3-1 : 삭제할 노드가 부모 노드의 왼쪽에 있다
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right

                # 가장 작은값은 무조건 left에 있다 = 일단 left 끝까지 가게
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                self.change_node = self.change_node.left

                # 3-1-2
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-1-1
                    self.change_node_parent.left = None

                # 위로 옮기기
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left
            # case3-2 : 삭제할 노드가 부모 노드의 오른쪽에 있다
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.chage_node = self.change_node.left  # 비교 대상 변경
                # 3-2-2
                if self.chage_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:  # 3-2-1
                    self.change_node_parent.left = None

                # 위로 옮긴다.
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.chage_node.right = self.current_node.right
                
     # 전위 순회
    def preorder(self, n):
        if n != None:
            print(n.item, '', end='') # 노드 방문
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회
    
    # 후위 순회
    def postorder(self, n):
        if n != None:
            if n.left:
                self.postorder(n.left)
            if n.right:
                self.postorder(n.right)
            print(n.item, '', end='') # 노드 방문
    
    # 중위 순회
    def inorder(self, n):
        if n != None:
            if n.left:
                self.inorder(n.left)
            print(n.item, '', end='') # 노드 방문
            if n.right:
                self.inorder(n.right)

    # 레벨 순회
    def levelorder(self, n):
        q = []
        q.append(n)
        while q:
            t = q.pop(0)
            print(t.item, '', end='')
            if t.left != None:
                q.append(t.left)
            if t.right != None:
                q.append(t.right)

구현 확인해보기

1. 추가&삭제&검색 확인해보기

# 1부터 999 숫자 중에서 임의로 100개 추출하여 이진 트리에 입력/검색/삭제
import random

# 1~999중 100개의 숫자 랜덤 선택
bst_nums = set()  # 100개를 랜덤선택하다보면 중복이 있을 수 있는데 집합(set)으로 이를 방지
while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))  # 중복이라면 아예 들어가질 않음. 그래서 반복문은 100번 이상 실행될 가능성이 높음

#print(bst_nums)

# 선택된 100개의 숫자를 이진 탐색트리에 입력, 루트노트는 500으로 임의로 지정
# 1이나 999이러면 한쪽에 치우친 트리가 될것이다. 주의하자
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
    binary_tree.insert(num)

# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
    if binary_tree.search(num) == False:
        print("search failed", num)  # 이게 사실 나오면 코드 잘못짠것임

# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)  # 인덱스로 접근하기 위해 list타입으로 변형시킨다.
while len(delete_nums) != 10:
    delete_nums.add(bst_nums[random.randint(0, 99)])

# 선택한 10개의 숫자를 삭제(삭제 기능확인)
for del_num in delete_nums:
    if binary_tree.delete(del_num) == False:
        print('delete failed', del_num)  # 이게 사실 나오면 코드 잘못짠것임

2. 순회 확인해보기

tree = BinaryTree()
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
n4 = Node(40)
n5 = Node(50)
n6 = Node(60)
n7 = Node(70)
n8 = Node(80)

tree.root = n1
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
n4.left = n8

print('트리 높이 : ', tree.height(tree.root))

# 전위 순회: 10 20 40 80 50 30 60 70
print('전위 순회: ', end='')
tree.preorder(tree.root)
print()

# 후위 순회: 80 40 50 20 60 70 30 10 
print('후위 순회 : ', end='')
tree.postorder(tree.root)
print()

# 중위 순회: 80 40 20 50 10 60 30 70
print('중위 순회 : ', end='')
tree.inorder(tree.root)
print()

# 레벨 순회: 10 20 30 40 50 60 70 80
print('레벨 순회 : ', end='')
tree.levelorder(tree.root)
print()

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

이진탐색트리(Binary Search Tree) · ratsgo's blog

이번 글에서는 자료구조의 일종인 이진탐색트리(Binary Search Tree)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님, 그리고 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정

ratsgo.github.io

https://doing7.tistory.com/92

[자료구조] 이진 탐색 트리 with Python

💡 이진 탐색 트리(Binary Search Tree) : 이진트리에 다음과 같은 추가적인 조건이 있는 트리 1) 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰값을 가진다. 2) 모든 노드는 오른쪽 가지에 포

doing7.tistory.com

https://qqplot.github.io/python/2021/09/18/binary_tree.html

파이썬으로 이진트리 구현하기

파이썬으로 이진 트리를 구현해보자 이진 트리란 트리는 노드(Node)와 엣지(Edge)로 구성된다. 노드는 동그라미이고 엣지는 선이다. 노드는 자식을 가질 수 있다. 맨 꼭 대기에 있는 1번 노드는 루

qqplot.github.io