자료구조 멘토링 4주차 - Tree, Binary Tree 그리고 Binary Search Tree

모깅·2025년 1월 12일

멘토링 자료구조

자료구조 멘토링

목록 보기

5/8

✏️ Tree

9번 노드의 자식은 11번, 11번의 자식 노드는 8, 1, 4번이 됩니다.

5번 노드의 경우 리프 노드는 3번과 7번이 존재합니다. 이때 가장 긴 경로의 간선 수는 3까지 갔을 경우인 2이므로 5의 높이는 2입니다.

cf) 높이를 간선 수가 아니라 노드 수로 할 경우도 있으니 노드 수로 한다면 +1 해주면 됩니다.

✏️ Binary Tree

형태에 따른 Binary Tree의 종류

0번이 없다면 이는 완전 이진 트리가 아닙니다.

4번 노드 다음으로 노드가 생성된 것이 아니라 3번의 자식으로 노드가 생성됐다면 이는 완전 이진 트리가 아닙니다.

2번 노드의 자식을 보면 5번 서브트리의 높이는 1, 9번 서브트리의 높이는 2이므로 그 차이가 1입니다.
5번 노드의 자식을 보면 왼쪽 서브트리는 없으므로 -1, 오른쪽 서브트리의 높이가 0 이므로 그 차이가 1입니다.
9번 노드를 보면 왼쪽 서브트리의 높이는 1, 오른쪽 서브트리의 높이는 0이므로 그 차이는 1입니다.
1번 노드를 보면 왼쪽 서브트리의 높이는 0, 오른쪽 서브트리의 높이는 -1이므로 그 차이가 1입니다.
3번 노드를 보면 왼쪽 서브트리의 높이는 -1, 오른쪽 서브트리의 높이 또한 -1이므로 그 차이는 1입니다.

따라서 모든 노드의 높이 차이가 1 이하이므로 이 트리는 balanced binary tree 입니다.

Binary Tree 구현

class BinaryTree:
    def __init__(self, data):
        self.data = data
        self.left_tree = None
        self.right_tree = None

    def get_data(self):
        return self.data

    def set_data(self, data):
        self.data = data

    def get_left_sub_tree(self):
        return self.left_tree

    def set_left_sub_tree(self, left_tree):
        self.left_tree = left_tree

    def get_right_sub_tree(self):
        return self.right_tree

    def set_right_sub_tree(self, right_tree):
        self.right_tree = right_tree

    def pre_order_traversal(self, tree):
        if tree is None:
            return

        print(tree.data)
        self.pre_order_traversal(tree.left_tree)
        self.pre_order_traversal(tree.right_tree)

    def in_order_traversal(self, tree):
        if tree is None:
            return

        self.in_order_traversal(tree.left_tree)
        print(tree.data)
        self.in_order_traversal(tree.right_tree)

    def post_order_traversal(self, tree):
        if tree is None:
            return

        self.post_order_traversal(tree.left_tree)
        self.post_order_traversal(tree.right_tree)
        print(tree.data)

if __name__ == "__main__":
    tree1 = BinaryTree(1)
    tree2 = BinaryTree(2)
    tree3 = BinaryTree(3)
    tree4 = BinaryTree(4)
    tree5 = BinaryTree(5)
    tree6 = BinaryTree(6)
    tree7 = BinaryTree(7)

    tree1.set_left_sub_tree(tree2)
    tree1.set_right_sub_tree(tree3)
    tree2.set_left_sub_tree(tree4)
    tree2.set_right_sub_tree(tree5)
    tree3.set_left_sub_tree(tree6)
    tree3.set_right_sub_tree(tree7)

    print("루트노드의 오른쪽 자식 노드:", tree1.get_right_sub_tree().get_data())
    print("루트노드의 오른쪽 자식 노드의 왼쪽 자식노드:", tree1.get_right_sub_tree().get_left_sub_tree().get_data())

    print("전위 순회")
    tree1.pre_order_traversal(tree1)

    print("중위 순회")
    tree1.in_order_traversal(tree1)

    print("후위 순회")
    tree1.post_order_traversal(tree1)

결과

루트노드의 오른쪽 자식 노드: 3
루트노드의 오른쪽 자식 노드의 왼쪽 자식노드: 6
전위 순회
1
2
4
5
3
6
7
중위 순회
4
2
5
1
6
3
7
후위 순회
4
5
2
6
7
3
1

✏️ Binary Search

이진 탐색 트리를 이해하기 위해선 이진 탐색 알고리즘에 대해 먼저 공부해야 합니다.

이진 트리 탐색은 이진 탐색 알고리즘의 장점은 취하고 단점은 뺀 자료구조입니다.

그럼 이진 탐색에 대해 알아보도록 하겠습니다.

UP and Down 게임에 대해서 아시나요?? 진행자는 1부터 50까지 숫자를 하나 선택해서 적어둡니다. 그리고 참가자들은 적힌 숫자를 예측해서 숫자 하나씩 부릅니다. 진행자가 숫자 3을 선택했다고 가정하고 참가자들은 단순하기 때문에 1부터 순서대로 쭉 선택한다고 가정하겠습니다.
그럼 참자가는 1을 부르고 2를 부르고 3을 부를 때 진행자는 정답을 외칠 것입니다.
하지만 만약 진행자가 50을 적어놨다면 1부터 순서대로 부를 경우 50번을 모두 불러야 게임이 종료될 겁니다. 즉, 최악의 경우 O(n)의 성능을 갖게 됩니다.

다른 방식으로 생각해 봅시다. 마찬가지로 진행자가 3을 선택했다고 가정해봅시다. 참가자가 중간값인 25를 외칩니다. 진행자는 down을 외칠 것이고 범위가 1 ~ 24임이 밝혀졌으니 그 중간값인 12를 외칩니다. 이런식으로 다음은 6 그 다음은 3을 외칠 경우 정답을 맞추게 됩니다.

$\log_2(50)$ 은 5.6이므로 6번 이하의 시도록 정답을 맞출 수 있게 됩니다. 따라서 이진 탐색 알고리즘의 성능은 O( $\log n$ )입니다.

하지만 이진 탐색에는 데이터가 정렬 되어있어야 한다는 치명적인 단점이 있습니다. 만약 참가자가 25를 외치고 진행자가 down을 외쳤는데 범위 안에 25보다 큰 값들이 있으면 이 방식을 사용할 수 없을 것입니다.

이진 탐색 알고리즘

def binary_search(arr, target, start, end):
    if start > end:
        return None  # 요소를 찾지 못한 경우

    mid = (start + end) // 2

    if arr[mid] == target:
        return mid  # 요소를 찾은 경우
    elif target > arr[mid]:
        return binary_search(arr, target, mid + 1, end)  # 오른쪽 절반 탐색
    else:
        return binary_search(arr, target, start, mid - 1)  # 왼쪽 절반 탐색


# 테스트 데이터
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
index = binary_search(arr, 3, 0, len(arr) - 1)
print(f"index: {index}")

결과

index: 2

✏️ Binary Search Tree

이진 탐색은 ArrayList가 정렬되어 있다고 가정하고 만들어진 알고리즘입니다. ArrayList는 삽입과 제거에서 많은 오버헤드가 존재했습니다.

리뷰를 하면 중간에 데이터를 삽입할 경우 중간 인덱스 이후의 모든 데이터가 한칸씩 옮겨가야 했습니다. 따라서 O(n)의 성능을 가졌습니다.
ArrayList는 중간에 빈 공간이 있으면 안됐기 때문에 중간 데이터를 제거하면 한 칸씩 당겨져야 했기 때문에 O(n)의 성능을 가졌습니다.

만약 사용자가 삽입과 제거를 자주 해야하는 상황이라면 ArrayList는 좋은 선택이 아닐겁니다.

만약 사용자가 삽입과 제거를 자주 하면서 조회도 자주 한다고 하면 어떤 자료구조가 좋을까요?

맞습니다. 해시 테이블(hash table)입니다. 해시 테이블은 해시 함수만 좋다면 데이터의 삽입, 제거가 빠르고 O(1)의 성능으로 아주 빠릅니다. 하지만 해시 테이블의 장점도 존재합니다.

해시 함수를 대충 만드러게 된다면 충돌로 인해 성능이 급격하게 안좋아집니다. 또한 데이터가 정렬되어 있지 않고 테이블을 만들어 놓아야 하기 때문에 메모리도 더 많이 필요하게 됩니다.

그럼 이진 탐색 트리에 대해 알아보겠습니다.

이진 탐색 트리는 기본적으로 이진 트리의 모습을 하고 있습니다. 이진 트리의 특징은 트리 구조이긴 하지만 자식 노드가 최대 2개인 트리였습니다.

여기서 몇가지 조건을 추가하면 이진 탐색 트리가 됩니다.

추가적으로 중복된 노드가 없어야 합니다.

Binary Search Tree insert(), search() 구현

노드가 존재하지 않으면 비교 작업을 마치고 데이터를 삽입합니다. 삽입은 이런식으로 루트 노드부터 시작해 null을 만날 때까지 비교하면서 좌우로 내려가는 간단한 작업입니다.

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = BinaryTree(data)
            return

        current_node = self.root
        parent_node = None

        while current_node:
            parent_node = current_node

            if data < current_node.data:
                current_node = current_node.left
            elif data > current_node.data:
                current_node = current_node.right
            else:
                return  # Data already exists

        new_node = BinaryTree(data)

        if data < parent_node.data:
            parent_node.left = new_node
        else:
            parent_node.right = new_node

    def search(self, target_data):
        current_node = self.root

        while current_node:
            if current_node.data == target_data:
                return current_node
            elif target_data < current_node.data:
                current_node = current_node.left
            else:
                current_node = current_node.right

        return None  # Data not found


if __name__ == "__main__":
    bst = BinarySearchTree()
    bst.insert(18)
    bst.insert(15)
    bst.insert(10)
    bst.insert(6)
    bst.insert(3)
    bst.insert(8)
    bst.insert(12)
    bst.insert(11)
    bst.insert(31)
    bst.insert(27)
    bst.insert(24)
    bst.insert(20)
    bst.insert(33)
    bst.insert(35)
    bst.insert(37)

    print("In-order Traversal:")
    if bst.root:
        bst.root.in_order_traversal()
    print()

    print("========== Search 6 ==========")
    search_result1 = bst.search(6)
    if search_result1:
        print(f"Found: {search_result1.data}")
    else:
        print("Not Found")

    print("========== Search 1 ==========")
    search_result2 = bst.search(1)
    if search_result2:
        print(f"Found: {search_result2.data}")
    else:
        print("Not Found")

결과

In-order Traversal:
3 6 8 10 11 12 15 18 20 24 27 31 33 35 37 
========== Search 6 ==========
Found: 6
========== Search 1 ==========
Not Found

Binary Search Tree remove() 구현

제거의 경우 삽입과 탐색보다는 더 어려울 수 있습니다. 여러가지 케이스가 있으니 하나씩 살펴보도록 합시다.

첫 번째 상황. 터미널 노드 제거

터미널 노드, 즉 리프 노드를 제거하는 상황이라면 해당 노드의 참조만 끊어주면 됩니다.

두 번째 상황. 자식 노드가 한 개인 노드 제거

제거할 노드와 부모 노드의 연결을 끊고 부모 노드와 제거할 노드의 자식 노드를 연결해주어야 합니다.

세 번째 상황. 자식 노드가 두 개인 노드 제거

10을 제거한다고 가정하겠습니다.

이때 자식 노드 중 누군가가 10노드가 있었던 위치에 대신해서 와야 합니다. 하지만 아무 노드가 오면 안되고 이진 탐색 트리의 조건을 무너뜨리지 않는 노드가 와야 합니다.

그럼 어떤 노드가 와야 할까요?

만약 왼쪽 서브 트리의 노드를 10을 대신할 서브 트리의 노드로 결정하고 싶다면 왼쪽 서브 트리 중 가장 큰 값을 이동시켜주면 됩니다. 이 경우 8을 15의 자식노드로 설정해주면 됩니다.

만약 오른쪽 서브 트리의 노드를 10을 대신할 노드로 결정하고 싶다면 오른쪽 서브 트리 중 가장 큰 값을 이동시켜주면 됩니다. 이 경우 11을 15의 자식노드로 설정해주면 됩니다.

둘 중 아무값이나 상용해도 상관없으나 이번 멘토링에서는 왼쪽 서브 트리 중 가장 큰 값을 갖는 노드를 선택하는 방향으로 강의를 진행하겠습니다.

그럼 왼쪽 서브 트리 중 가장 큰 값은 어떻게 구해야 할까요?

해당 서브 트리의 오른쪽으로 계속 이동하면 됩니다.
만약 전체 트리에서 가장 큰 값을 찾고 싶다면 계속 오른쪽으로 이동한 값인 37을 찾을 수 있습니다.

우리는 왼쪽 서브 트리중 가장 큰 값을 찾기로 했으니 10을 제거하고 싶다면 왼쪽으로 한 번 이동 후 계속 오른쪽으로 이동하여 가장 큰 값을 찾을 수 있을 겁니다.

그럼 아래 상황에서 10을 제거해보도록 합시다.

이제 10을 기준으로 왼쪽 서브 트리 중 가장 큰 값인 8을 찾았습니다.

그럼 이제 제거하려는 값이 10 대신에 8을 덮어씁니다.

그리고 6의 오른쪽 자식노드를 8의 왼쪽 자식이었던 7로 설정해줍니다.

구현하기 전에 Binary Tree에 서브 트리를 제거하는 메서드는 추가해줍시다.

def remove_left_subtree(self):
    removed_node = self.left
    self.left = None
    return removed_node

def remove_right_subtree(self):
    removed_node = self.right
    self.right = None
    return removed_node

이제 remove() 메서드를 정의해 봅시다.

def remove(self, target_data):
        fake_parent_root = BinaryTree(0)
        fake_parent_root.right = self.root
        parent_node = fake_parent_root
        current_node = self.root
        removed_node = None

        while current_node and current_node.data != target_data:
            parent_node = current_node

            if target_data < current_node.data:
                current_node = current_node.left
            else:
                current_node = current_node.right

        if current_node is None:
            return None

        deleted_node = current_node

        if deleted_node.left is None and deleted_node.right is None:  # No children
            if parent_node.left == deleted_node:
                parent_node.left = None
            else:
                parent_node.right = None

        elif deleted_node.left is None or deleted_node.right is None:  # One child
            child_node = deleted_node.left if deleted_node.left else deleted_node.right

            if parent_node.left == deleted_node:
                parent_node.left = child_node
            else:
                parent_node.right = child_node

        else:  # Two children
            replacing_node = deleted_node.left
            replacing_node_parent = deleted_node

            while replacing_node.right:
                replacing_node_parent = replacing_node
                replacing_node = replacing_node.right

            deleted_node_data = deleted_node.data
            deleted_node.data = replacing_node.data

            if replacing_node_parent.left == replacing_node:
                replacing_node_parent.left = replacing_node.left
            else:
                replacing_node_parent.right = replacing_node.left

            deleted_node = replacing_node
            deleted_node.data = deleted_node_data

        if fake_parent_root.right != self.root:
            self.root = fake_parent_root.right

        return deleted_node