<코딩테스트 Level1> 12일차 - 이진 탐색 트리

46616 단어 모각코모각코

📌 이진 탐색 트리

이진 탐색 트리란 이진 탐색과 링크드 리스트를 결합한 자료구조의 일종이다.

이진 탐색은 시간복잡도가 O(Log n)으로 굉장히 빨랐지만 배열이기 때문에 자료의 삽입, 혹은 삭제가 불가능했다.

또한 링크드 리스트의 경우 자료 입력, 혹은 삭제에 필요한 시간복잡도는 O(1)이였지만, 자료를 탐색하기 위해선 O(n)의 시간 복잡도가 필요했다.

즉, 이진 탐색과 링크드 리스트 모두 장점과 단점이 명확했기 때문에 두 가지 장점만 취해서 결합한 게 바로 이진 탐색 트리이다.

이진 탐색 트리는 아래와 같은 조건이 추가된 트리이다.

위 조건들을 만족하는 트리를 예시로 사용하자.

1번과 2번 조건을 만족하는지 살펴보자.

루트 노드 7의 왼쪽 서브 트리는 3, 1, 5 노드가 존재하고, 오른쪽 서브 트리에는 10, 8 노드가 존재한다.

왼쪽 서브 트리는 루트 노드보다 작은 값들이, 오른쪽 서브 트리에는 루트 노드보다 큰 값들이 들어가 있으니 조건을 만족한다.

또한 모든 노드가 중복되지 않고 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이기 때문에 모든 조건을 만족한다.

📌 이진 탐색 트리의 순회

이전 챕터에서 트리 순회 방법 세 가지를 배웠다.

이진 탐색 트리의 특성을 고려해볼 때 루트 노드에서 계속해서 왼쪽 자식을 타고 내려가면 어떤 값이 나올까?

바로 전체 트리에서 가장 작은 값이 나온다.
한 노드 A의 왼쪽 자식은 무조건 A보다 작은 값이 들어가야 하기 때문이다.
계속해서 오른쪽 트리를 타고 내려가다 보면 당연히 트리에서 가장 큰 값이 나온다.

즉 가장 왼쪽 노드에서 탐색을 시작하고 가장 오른쪽 노드에서 탐색을 종료하는 중위 순회 방식을 사용하면 이진 탐색 트리 내의 모든 값을 정렬된 순서로 읽을 수 있다.

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

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

    def set_root(self, data):
        self.root = Node(data)

BST = BinarySearchTree()
BST.set_root(1)

print(BST.root.data)

📌 이진 탐색 트리 검색

이진 탐색 트리는 기본적으로 데이터 삽입, 데이터 검색, 데이터 삭제 기능이 있어야 한다. 연산을 구현하기에 앞서 트리를 탐색하는 방법 먼저 알아보자.

진 탐색 트리 예시를 사용해, 이진 탐색 트리에서 데이터를 검색하는 방법에 대해 알아보자.

이진 탐색 트리는 부모 노드가 왼쪽 자식보다 크고, 오른쪽 자식보다 작다는 특성이 있다. 이 점을 이용하면 효율적인 탐색이 가능하다.
위 예시에서 8을 탐색하는 방식을 알아보자.

8은 7보다 크므로, 목표 값은 오른쪽 서브트리에 존재해요.
따라서, 왼쪽 서브 트리 (1, 3, 5)는 고려할 필요가 없다. 오른쪽 서브 트리로 이동한다.

이번에는 목표 값 8보다 오른쪽 자식 노드의 값이 더 크다.
따라서, 목표 값은 왼쪽 서브 트리에 존재한다는 사실을 알 수 있다.
왼쪽 서브 트리로 이동한다.

원하는 값을 찾았으니 탐색에 성공했다.
트리에 원하는 값이 존재하지 않는 경우는 어떻게 판단할까 ❓

✅ 트리에 원하는 값이 없는 경우

그럼 이번엔 목표 값을 4로 설정하고, 탐색을 진행해보자.
일반적인 경우는 위와 같으니, 바로 노드 5까지 이동해서 경과를 살펴본다.

노드 5에 도착했다. 노드 5와 목표 값 4을 비교했을 때 목표 값이 더 작으므로, 왼쪽 서브 트리로 이동한다.

하지만 노드 5는 자식 노드가 존재하지 않는 리프 노드(leaf node)이다.
(나무(tree)의 끝에 달려있는 잎사귀에 비유해서, Leaf Node라고 한다.)

이런 경우, 값을 찾지 못했다는 표시를 반환하고, 탐색을 종료한다.

📌 데이터 탐색 구현

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

    def set_root(self, data):
        self.root = Node(data)

    def find(self, data):
        if self.find_node_by_data(self.root, data) == False:
            return False
        else:
            return True

    def find_node_by_data(self, current_node, data):
        if current_node == None:
            return False
        print(current_node.data)
        if data == current_node.data:
            return current_node

        if data < current_node.data:
            return self.find_node_by_data(current_node.left, data)
        if data > current_node.data:
            return self.find_node_by_data(current_node.right, data)

def temp_data_insert(root):
    node_2 = Node(3)
    node_3 = Node(10)
    root.left = node_2
    root.right = node_3

    node_4 = Node(1)
    node_5 = Node(5)
    node_2.left = node_4
    node_2.right = node_5

    node_6 = Node(8)
    node_3.left = node_6
    return root

BST = BinarySearchTree()
BST.set_root(7)
BST.root = temp_data_insert(BST.root)
BST.find(5)

기본적인 구조는 트리의 순회와 마찬가지로 재귀 구조를 띄고 있다.

현재 노드가 목표 값보다 큰 경우, 왼쪽 자식 노드로 재귀 호출하고,
현재 노드가 목표 값보다 작은 경우, 오른쪽 자식 노드로 재귀 호출한다.

tmp_data_insert 함수는 데이터 삽입을 배우기 전까지 임시로 사용하는 함수이다.
직접 노드의 left, right에 값을 집어넣는 건 그다지 좋은 방법이 아니다.

📌 이진 탐색 트리의 데이터 삽입

새로운 데이터 노드는 기존 트리의 리프 노드에 붙여야 한다.
우리의 예시 트리에서 데이터 4를 추가한다면, 아래와 같이 추가된다.

여기에 12, 15를 차례로 삽입한다면, 아래와 같이 트리가 구성된다.

트리에 데이터를 삽입하기 위해선 한 레벨씩 내려오면서 값을 비교해야 한다.
트리의 높이가 100일 때, 최악의 경우 100번 값을 비교해야 한다는 의미이다. 따라서 데이터 삽입의 시간 복잡도는 O(h)이다.

📌 데이터 삽입 구현

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

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

    def set_root(self, data):
        self.root = Node(data)

    def find(self, data):
        if self.find_node_by_recursion(self.root, data) == False:
            return False
        else:
            return True

    def find_node_by_recursion(self, current_node, data):
        if current_node == None:
            return False
        if data == current_node.data:
            return current_node

        if data < current_node.data:
            return self.find_node_by_recursion(current_node.left, data)
        if data > current_node.data:
            return self.find_node_by_recursion(current_node.right, data)

    def insert(self, data):
        if self.root == None:
            self.set_root(data)
        else:
            self.insert_node(self.root, data)

    def insert_node(self, current_node, data):
        if data == current_node.data:
            print(f"이미 {data}값이 존재합니다. 중복된 값은 삽입할 수 없습니다.")
            return
        if data < current_node.data:
            if current_node.left == None:
                current_node.left = Node(data)
            else:
                self.insert_node(current_node.left, data)

        elif data > current_node.data:
            if current_node.right == None:
                current_node.right = Node(data)
            else:
                self.insert_node(current_node.right, data)

BST = BinarySearchTree()
BST.set_root(7)

BST.insert(3)
BST.insert(1)
BST.insert(5)
BST.insert(10)
BST.insert(8)

print("root -> left -> left : ", BST.root.left.left.data)
print("root -> left -> right : ", BST.root.left.right.data)
print("root -> right -> left : ", BST.root.right.left.data)

BST.insert(4)
BST.insert(12)
BST.insert(15)

print("root -> right -> right : ", BST.root.right.right.data)
print("root -> right -> right -> right : ", BST.root.right.right.right.data)

📌 데이터 삭제

첫 번째는 삭제 대상 노드가 자식 노드가 없는 경우이다.
이 경우, 단순히 노드를 삭제하면 된답니다. 위의 예시에선 1, 4, 8, 15번 노드가 해당된다.

자식 노드를 하나만 가지는 경우이다.
이 때는 삭제 대상의 부모 노드와, 삭제 대상의 자식 노드를 연결한다.

위 예시에서, 12는 10의 오른쪽 서브 트리이다.
즉, 12를 루트 노드로 하는 모든 서브 트리는 10보다 크다는 의미가 된다.

10보다 작다면 10의 오른쪽 자식으로 진입할 수 없기 때문이다.
따라서, 12를 삭제하면서 10과 15를 연결해 주면 12 노드의 삭제가 마무리 된다.

자식 노드가 두 개인 경우이다.

위 예시에서 3번 노드를 삭제해야 한다고 생각해 보자.
7번 노드와 3번 노드의 서브 노드를 어떤 식으로 연결해 줘야 할까 ❓

위 트리를 중위 순회 방식으로 탐색하면, 아래와 같은 리스트를 볼 수 있다.

1 3 4 5 7 8 10 12 15

이 때, 3번 노드의 오른쪽 서브 트리 중 최소 값을 살펴보면, 4번 노드인걸 알 수 있다. 또한 중위 순회로 출력한 리스트에서, 3과 4는 붙어있다

따라서 3번 노드 자리에 4를 대입하고, 기존의 4번 노드를 삭제한다면 중위 순회 시 데이터가 정렬된 상태도 유지하고,이진 탐색 트리 구조도 무너지지 않는 결과가 나온다.

1  /3/  4 5 7 8 10 12 15

❓ 예시에서 4번 노드는 자식 노드가 없었는데, 자식 노드가 있는 경우엔 코드가 꼬이지 않을까 ❓

삭제 대상 노드의 자리에 복사하는 노드를 아래와 같이 제한했다.

  • 삭제 대상 노드의 오른쪽 서브 트리 중 최소 값
    이진 탐색 트리의 순회에서, 트리의 최소 값은 루트 노드에서 계속해서 왼쪽 자식을 타고 내려가면 찾을 수 있다고 했다.

트리의 최소 값은 왼쪽 자식 노드가 존재하지 않는다는 의미이다.

따라서 복사 대상 노드(삭제 대상 노드의 오른쪽 서브 트리의 최소 값)는 자식 노드가 최대 한 개 이므로 데이터 삭제 방법 1번 혹은 2번에 해당한다.

📌 데이터 삭제 구현 및 전체 코드

삭제할 노드의 오른쪽 자식 노드를 인자로 받고, 자식 노드를 루트 노드로 하는 서브 트리의 최소 값 노드를 리턴하는 함수이다.

우리의 예시 트리에서 3번 노드를 삭제하려고 할 때, 5번 노드를 인자로 받고 최소 값 노드 4번을 리턴하는 함수가 된다.

삭제를 담당하는 함수이다.

  1. 삭제 대상 노드가 자식 노드가 없는지?
  2. 삭제 대상 노드가 왼쪽 자식 노드만 갖는지?
  3. 삭제 대상 노드가 오른쪽 자식 노드만 갖는지?
  4. 삭제 대상 노드의 자식 노드가 두 개인지?
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

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

    def set_root(self, data):
        self.root = Node(data)

    def find(self, data):
        if self.find_node_by_recursion(self.root, data) == False:
            return False
        else:
            return True

    def find_node_by_recursion(self, current_node, data):
        if current_node == None:
            return False
        if data == current_node.data:
            return current_node

        if data < current_node.data:
            return self.find_node_by_recursion(current_node.left, data)
        if data > current_node.data:
            return self.find_node_by_recursion(current_node.right, data)

    def insert(self, data):
        if self.root == None:
            self.set_root(data)
        else:
            self.insert_node(self.root, data)

    def insert_node(self, current_node, data):
        if data == current_node.data:
            print(f"이미 {data}값이 존재합니다. 중복된 값은 삽입할 수 없습니다.")
            return
        if data < current_node.data:
            if current_node.left == None:
                current_node.left = Node(data)
            else:
                self.insert_node(current_node.left, data)

        elif data > current_node.data:
            if current_node.right == None:
                current_node.right = Node(data)
            else:
                self.insert_node(current_node.right, data)

    def get_next_node(self, node):
        while node.left != None:
            node = node.left
        return node

    def delete(self, data):
        if self.root == None:
            print("트리에 노드가 존재하지 않습니다.")
        else:
            self.delete_node(None, self.root, data)

    def delete_node(self, parent, current_node, data):
        if current_node == None:
            print(f"트리에 {data}가 존재하지 않습니다.")
            return

        if data < current_node.data:
            self.delete_node(current_node, current_node.left, data)
        elif data > current_node.data:
            self.delete_node(current_node, current_node.right, data)
        else:
            if current_node.left == None and current_node.right == None:
                if data < parent.data:
                    parent.left = None
                else:
                    parent.right = None
            elif current_node.left != None and current_node.right == None:
                if data < parent.data:
                    parent.left = current_node.left
                else:
                    parent.right = current_node.left
            elif current_node.left == None and current_node.right != None:
                if data < parent.data:
                    parent.left = current_node.right
                else:
                    parent.right = current_node.right

            elif current_node.left != None and current_node.right != None:
                next_node = self.get_next_node(current_node.right)

                current_node.data = next_node.data
                self.delete_node(current_node, current_node.right, next_node.data)

def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(f"{node.data}  ", end="")
    in_order(node.right)

BST = BinarySearchTree()
BST.set_root(7)

BST.insert(3)
BST.insert(1)
BST.insert(5)
BST.insert(10)
BST.insert(8)

BST.insert(4)
BST.insert(12)
BST.insert(15)

BST.delete(10)

in_order(BST.root)
코틀린의 제네릭과 가변성에 대해
[ML/DL] Train/Test/Valid Dataset

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage