본문 바로가기
도서/프로그래밍

[쓰면서 익히는 알고리즘과 자료구조](6) 트리(Tree)

by 신발사야지 2023. 2. 11.

트리(Tree)는 계층적 데이터를 저장하고 활용하기 위한 자료구조다.

 

6.2 이진 트리(Binary Tree)

다양한 목적과 목표의 트리 구성이 있는데, 이 책에서는 이진 트리 관련 문제를 주로 다루겠다. 기본적으로 이진 트리는 자식 노드가 최대 2개인 트리 구성을 말한다.

이진 트리의 종류로는 다음과 같은 세가지가 있다.

  1. 정 이진 트리(full binary tree)
    1. 모든 노드가 자식 노드를 2개 가지고 있다
  2. 완전 이진 트리(complete binary tree)
    1. 마지막 레벨을 제외한 모든 레벨에 노드가 차있다.
  3. 균형 이진 트리(balanced binary tree)
    1. 루트 노드 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 깊이 차가 1을 넘지 않는 트리를 말한다.

6.2.1 이진 트리 표현

이진 트리는 연결 리스트의 구성과 비슷하다.

다음 노드가 아닌 왼쪽과 오른쪽 2개의 자식 노드를 가리킨다는 점만 다르다.

이진 트리는 단순히 데이터를 저장하는 용도로 사용되는 것이 아니라, 자료를 더 빠르게 정리하고 원하는 데이터를 찾을 수 있도록 하는 구성의 기반이다.

 

이진 탐색 트리

그중 가장 많이 사용되는 이진 탐색 트리(Binary Search Tree)를 구성해보자.

추가(insert)

이진 탐색 트리의 기본 개념은 노드 값을 기준으로 작은 값은 왼쪽 자식으로 할당하고 노드 값보다 크면 오른쪽 자식으로 할당한다.

트리 순회 방법

  • 중위 순회(Inorder traversal)
    • 왼쪽 하위 트리 → 루트 노드 → 오른쪽 하위 트리
  • 전위 순회(Preorder traversal)
    • 루트 노드 → 왼쪽 하위 트리 → 오른쪽 하위 트리
  • 후위 순회(postorder traversal)
    • 왼쪽 하위 트리 → 오른쪽 하위 트리 → 루트 노드

탐색(find)

이진검색트리는 대개 검색 시간이 O(log n) 이지만 트리가 한 쪽으로 치우쳐져 있다면 O(n) 이 될 수 있다.

삭제(delete)

이진 탐색 트리에서 노드 삭제는 추가 및 찾기보다 상대적으로 복잡하다.

이진 탐색 트리의 삭제 노드 위치에 따른 3가지 경우를 다르게 처리해야 한다.

  1. 잎새(leaf) 노드를 지우는 경우다.
    1. 트리 마지막에 달려있는 노드여서 특별히 다른 처리 없이 부의 왼쪽 노드인지 오른쪽 노드인지만 확인하여 부모 노드의 오른쪽 혹은 왼쪽 연결 고리를 끊으면 된다.
  2. 지우려는 노드가 왼쪽 혹은 오른쪽에 하나의 자식만 갖고 있는 경우다.
    1. 이 경우 지워지는 노드의 단일 자식을 지워지는 노드의 부모와 연결하고 삭제하면 된다.
  3. 지우려는 노드의 자식이 왼쪽, 오른쪽에 다 있는 경우이다.
    1. 오른쪽 하위 트리에서 가장 작은 값을 지우는 노드의 위치로 바꾸어준다.
    2. 오른쪽 하위 트리에서 가장 작은 값 = 루트 노드의 하위 노드들 중에서 중간
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def __repr__(self):
        return str(self.data)


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

    def insert(self, data, method='iterative'):
        if method in 'recursion':
            self.__root = self.insert_rec(self.__root, data)
        else:
            self.insert_iter(data)

    def insert_rec(self, node, data):
        if not node:
            node = Node(data)
        else:
            if node.data > data:
                node.left = self.insert_rec(node.left, data)
            else:
                node.right = self.insert_rec(node.right, data)

        return node

    def insert_iter(self, data):
        if not self.__root:
            self.__root = Node(data)
            return

        new_node = Node(data)

        curr = self.__root
        parent = None

        while curr is not None:
            parent = curr
            if curr.data > data:
                curr = curr.left
            else:
                curr = curr.right

        if parent.data > data:
            parent.left = new_node
        else:
            parent.right = new_node

    def inorder_traverse(self):
        result = []

        self.inorder_rec(self.__root, result)

        return result

    def inorder_rec(self, node, result):
        if not node:
            return

        self.inorder_rec(node.left, result)
        result.append(node.data)
        self.inorder_rec(node.right, result)

    def find(self, data):
        return self.find_data(self.__root, data)

    def find_data(self, node, data):
        if node is None:
            return False
        elif node.data == data:
            return True
        elif node.data > data:
            return self.find_data(node.left, data)
        else:
            return self.find_data(node.right, data)

    def find_min_node(self, node):
        while node.left:
            node = node.left
        return node

    def delete(self, data):
        self.delete_data(self.__root, data)

    def delete_data(self, node, data):
        parent = None

        curr = node

        # data에 해당하는 노드 찾기, parent 추적
        while curr and curr.data != data:
            parent = curr

            if curr.data > data:
                curr = curr.left
            else:
                curr = curr.right

        # data 를 못 찾는 경우
        if curr is None:
            return node

        # 자식 노드가 없는 노드의 삭제
        if curr.left is None and curr.right is None:
            if curr != node:
                if parent.left == curr:
                    parent.left = None
                else:
                    parent.rgith = None
            else:
                node = None

        # 오른쪽 왼쪽에 모든 자식이 있는 경우
        elif curr.left and curr.right:
            # 지우려는 노드의 오른쪽 하위 트리에서 가장 작은 노드 찾기
            min_node = self.find_min_node(curr.right)

            min_data = min_node.data

            # 오른쪽 하위 트리에서 가장 작은 노드는
            # 항상 잎새(leaf) 노드이므로 그냥 삭제 진행한다.
            self.delete_data(node, min_data)
            curr.data = min_data
        # 오른쪽 혹은 왼쪽 노드가 하나만 있는 경우
        else:
            if curr.left:
                child = curr.left
            else:
                child = curr.right

            if curr != node:
                if curr == parent.left:
                    parent.left = child
                else:
                    parent.right = child
            else:
                node = child
        return node

6.3 깊이 우선 탐색(Depth-First Search)

트리와 관련된 다양한 문제는 깊이 우선 탐색(Depth-First Search)이나 너비 우선 탐색(Breadth-First Search)으로 해결 가능하다.

깊이 우선 탐색의 키워드는 ‘스택(Stack)’ 이다.

기본 논리는 왼쪽부터 가장 깊은 노드까지 방문을 우선적으로 하는 것이다.

스택에 루트 노드를 넣는다. → 스택에서 한 개를 꺼내고 꺼낸 노드의 왼쪽과 오른쪽 노드를 스택에 집어 넣는다 → 스택에서 한 개를 꺼내고 꺼낸 노드의 왼쪽과 오른쪽 노드를 스택에 집어 넣는다 → 스택에 어떠한 노드도 없다면 깊이 우선 탐색은 끝난다.

 

class BinarySearchTree:
    def __init__(self):
        self.__root = None
		def depth_first_search(self):
        res_iter = []
        res_iter = self.df_iter()

        print(f'df iter : {res_iter}')

    def dfs_iter(self):
        if not self.__root:
            return []

        stack = []
        result = []

        stack.append(self.__root)

        while len(stack) != 0:
            node = stack.pop()

            result.append(node.data)

            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

        return result
    
    def dfs_rec(self, node, result):
        if not node:
            return
        
        result.append(node.data)
        
        if node.left:
            self.dfs_rec(node.left, result)
        if node.right:
            self.dfs_rec(node.right, result)

6.4 너비 우선 탐색(Breadth-First Search)

너비 우선 탐색에서의 키워드는 큐(Queue)다.

루트 노드를 큐에 넣는다. → 큐에서 노드를 꺼내면서 해당 노드의 왼쪽, 오른쪽 자식을 모두 큐에 넣는다. → 큐에서 노드를 꺼내면서 해당 노드의 왼쪽, 오른쪽 자식을 모두 큐에 넣는다. → 큐가 빌 때까지 반복한다

def breadth_first_search(self):
        queue = deque()
        res = []
        
        queue.append(self.__root)
        
        while len(queue) != 0:
            qsize = len(queue)
            
            for _ in range(qsize):
                node = queue.popleft()
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                
                res.append(node.data)

6.5 이진 힙(Binary heap)

이진 힙은 완전 이진 트리의 속성을 가진다.

  1. 완전 이진 트리(complete binary tree)
    1. 마지막 레벨을 제외한 모든 레벨에 노드가 차있다.

가장 왼쪽 노드부터 새롭게 추가되고 그로 인해 마지막 레벨은 제외하고 노드가 가득 차 있는 모양을 만들게 된다. 이런 특징 떄문에 이진 힙은 배열을 통해 데이터 관리하기 용이하다. 이진 힙은 2가지 종류가 있는데, 하나는 최대 힙(Max Heap), 다른 하나는 최소 힙(Min Heap)이다.

데이터가 입력되면 최대 힙은 루트 노드 값이 입력된 데이터 중 가장 큰 값이 되고, 최소 힙은 반대로 가장 작은 값이 된다. 이로 인해 루트 노드 값을 꺼내면 항상 가장 큰 값 혹은 가장 작은 값이 된다.

파이썬에는 heapq 라는 모듈을 제공하여 이진 힙의 기능을 제공 한다.

기본적으로 최소 이진 힙을 제공하기 때문에, 최대 힙으로 사용하기 위해서는 값에 -1 을 곱해서 음수로 곱하여 이진 힙을 생성하고, 값을 꺼내서 -1 을 곱해서 사용한다.

import heapq

heap = []

heapq.heappush(heap, 35)
heapq.heappush(heap, 33)
heapq.heappush(heap, 42)
heapq.heappush(heap, 10)
heapq.heappush(heap, 14)

print(heap)
print(heapq.heappop(heap))
print(heap)
print(heap[0])

heap2 = [35, 44, 42, 10, 14]
heapq.heapify(heap2)
print(heap2)

6.6 트리 경로의 합

  1. 정수형 데이터를 가진 트리(양수, 음수, 0)
  2. 트리의 경로 조건
    1. 시작은 어떤 노드나 가능
    2. 다른 경로는 자식 노드만 가능함
  3. sum은 정수형 값

BFS 로 트리를 순회하면서 탐색

 

from collections import deque

from binary_search_tree import Node # 위에 있는 코드 재사용


def path_sum(root: Node, sum: int) -> int:
    cnt = 0

    if root is None:
        return cnt

    def path_sum_sub(node: Node, target: int) -> int:
        if node is None:
            return 0

        find = 0
        if (target - node.data) == 0:
            find = 1

        sum_left = path_sum_sub(node.left, target - node.data)
        sum_right = path_sum_sub(node.right, target - node.data)

        return find + sum_left + sum_right

    queue = deque()  # queue 쓰면 BFS
    queue.append(root)

    while len(queue) != 0:
        q_size = len(queue)

        for _ in range(q_size):
            node = queue.popleft()

            cnt += path_sum_sub(node, sum)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return cnt

6.7 3번째 큰 수

배열에서 3번쨰로 큰 수를 찾아 반환하도록 하자.

  1. 배열을 정렬해서 3번째 요소를 반환
  2. 우선순위 큐(최대 힙 사용) 하여 3번째 꺼낸 요소를 반환

 

def get_third_max(nums: list[int]) -> int:
    cnt = 0
    check_dup = set()
    
    nums.sort(reverse=True)
    third_max = nums[0]
    
    for num in nums:
        if num in check_dup:
            continue
        
        check_dup.add(num)
        
        if cnt == 2:
            third_max = num
            break
        
        cnt += 1
    
    return third_max
import heapq


def third_max(nums: list[int]) -> int:
    prio_queue = [item * -1 for item in list(dict.fromkeys(nums))]
    
    heapq.heapify(prio_queue)
    
    if len(prio_queue) > 2:
        cnt = 2
        
        while cnt > 0:
            heapq.heappop(prio_queue)
            cnt -= 1
    
    return prio_queue[0] * -1

6.8 이진 트리 반전

아주 유명한 문제이다. 트리의 루트를 기준으로 각 좌우 노드의 위치를 바꾸는 것인데, 조금 막막하게 느껴질 수 있다. 하지만 문제 풀이를 통해 이해하면 잊어버리기 힘들 정도로 간단한 문제다.

from binary_search_tree import Node


def invert_tree(root: Node) -> Node:
    if root is None:
        return

    stack = [root]  # stack 이면 DFS

    while len(stack > 0):
        node = stack.pop()

        left = node.left
        node.left = node.right
        node.right = left

        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)

    return root
from binary_search_tree import Node


def invert_tree(root: Node) -> Node:
    if root is None:
        return None

    left = root.left
    root.left = root.right
    root.right = left

    invert_tree(root.left)
    invert_tree(root.right)

    return root
from collections import deque
from binary_search_tree import Node


def invert_tree(root: Node) -> Node:
    if root is None:
        return None
    
    queue = deque()  # queue => BFS
    queue.append(root)
    
    while len(queue) > 0:
        qsize = len(queue)
        
        for _ in range(qsize):
            node = queue.popleft()
            
            left = node.left
            node.left = node.right
            node.right = left
            
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
                
    return root

6.8 이진 검색 트리 검증

왼쪽 자식이 부모보다 작고, 오른쪽 자식이 부모보다 큰지 확인

 

from binary_search_tree import Node


def is_valid_bst(root: Node) -> bool:
    prev = float('-inf')

    def inorder_tree(node: Node) -> bool:
        nonlocal prev

        if node is None:
            return True

        if not inorder_tree(node.left):
            return False

        if node.data <= prev:
            return False

        prev = node.data

        return inorder_tree(node.right)

    return inorder_tree(root)
저작자표시

'도서 > 프로그래밍' 카테고리의 다른 글

[쓰면서 익히는 알고리즘과 자료구조](8) 정렬(Sort)  (0) 2023.02.13
[쓰면서 익히는 알고리즘과 자료구조](7) 동적 프로그래밍(Dynamic Programming)  (0) 2023.02.13
[쓰면서 익히는 알고리즘과 자료구조](5) 큐(Queue)  (0) 2023.02.11
[쓰면서 익히는 알고리즘과 자료구조](4) 스택(Stack)과 재귀(Recursion)  (0) 2023.02.10
[쓰면서 익히는 알고리즘과 자료구조](3) 연결 리스트(Linked List)  (0) 2023.02.08

관련글

티스토리툴바