[6.3] 09-2 이진 트리와 이진 검색 트리

이진 트리 알아보기

binary tree - 노드가 left child, right child만을 갖는 트리

완전 이진 트리 알아보기

complete binary tree - 루트부터 아래쪽으로 + 왼쪽부터 오른쪽으로 노드가 채워진 이진 트리

* 균형 검색 트리 self-balancing search tree

: 노드의 높이를 O(logn)으로 제한한 트리

- (이진 균형검색 트리) AVL tree, red-black tree가 있음

- (이진 아닌) B트리, 2-3 트리

이진 검색 트리 알아보기 binary search tree

배열 : 왼쪽 서브트리 노드 < 자신의 노드 < 오른쪽 서브트리 노드

(값이 중복되는 노드는 취급하지 않음)

검색 : 중위 순회의 깊이 우선 검색으로 검색

* 중위 순회 - 왼쪽 자식 -> 노드 -> 오른쪽 자식 - 리프에 도달할 때까지 아래쪽으로 내려가면서 검색함

이진 검색 트리 만들기

노드 클래스 Node - key, value, left, right(노드에 대한 참조 = 포인터임)

from __future__ import annotations
from typing import Any, Type

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

이진 검색 트리 클래스 BinarySearchTree

'필드'는 root만 있음 빈 상태임

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

키값으로 노드를 검색하는 search() 함수

-> 키와 노드의 대소관계를 판단하여 왼쪽/오른쪽 서브트리를 따라간다. 

class BinarySearchTree:
    def __init__(self):
        self.root = None
    def search(self, key:Any) -> Any:
        p = self.root
        while True:
            if p is None:
                return None
            if key == p.key:
                return p.value
            elif key < p.key:
                p= p.left
            else:
                p = p.right

노드를 삽입하는 add() 함수

    def add(self, key:Any, value:Any) -> bool:
        def add_node(node:None, key:Any, value:Any) -> None:
            if key == node.key:
                return False
            elif key < node.key:
                if node.left is None:
                    node.left = Node(key, value, None, None)
                else:
                    if node.right is None:
                        node.right = Node(key, value, None, None)
                    else:
                        add_node(node.right, key, value)
                return True
            if self.root is None:
                self.root = Node(key, value, None, None)
                return True
            else:
                return add_node(self.root, key, value)

노드를 삭제하는 remove() 함수

    def remove(self, key:Any) -> bool:
        p = self.root
        parent = None
        is_left_child = True

        while True:
            if p is None:
                return False
            if key == p.key:
                break
            else:
                parent = p
                if key < p.key:
                    is_left_chile = True
                    p = p.left
                else:
                    is_left_child = False
                    p = p.right
        if p.left is None:
            if p is self.root:
                self.root = p.right
            elif is_left_child:
                parent.left = p.right
            else:
                parent.right = p.right
        elif p.right is None:
            if p is self.root:
                self.root = p.left
            elif is_left_child:
                parent.left = p.left
            else:
                parent.right = p.left
        else:
            parent = p
            left = p.left
            is_left_child = True
            while left.right is not None:
                parent = left
                left = left.right
                is_left_child = False
            p.key = left.key
            p.value = left.value
            if is_left_child:
                parent.left = left.left
            else:
                parent.right = left.left
        return True

모든 노드를 오름차순으로 출력하는 dump() 함수

-> 중위 순회의 깊이 우선 검색

    def dump(self)-> None:

        def print_subtree(node:Node):
            if node is not None:
                print_subtree(node.left)
                print(f'{node.key} {node.value}')
                print_subtree(node.right)
        print_subtree(self.root)

최소 키와 최대 키를 반환하는 min_key() 함수와 max_key() 함수

    def min_key(self) -> Any:
        if self.root is None:
            return None
        p = self.root
        while p.left is not None:
            p = p.left
            return p.key
    def max_key(self) -> Any:
        if self.root is None:
            return None
        p = self.root
        while p.right is not None:
            p = p.right
        return p.key

* 키의 내림차순으로 덤프

 

이진 검색 트리 프로그램 만들기

from enum import Enum
from for_class import BinarySearchTree

Menu = Enum('Menu', ['삽입', '삭제', '검색', '덤프', '키의범위', '종료'])

def select_Menu() -> Menu:
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep = ' ', end = '')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)
tree = BinarySearchTree()

while True:
    menu = select_Menu()

    if menu == Menu.삽입:
        key = int(input('삽입할 키를 입력하세요: '))
        value = input('삽입할 값을 입력하세요')
        if not tree.add(key, value):
            print('삽입에 실패했습니다')
    elif menu == Menu.삭제:
        key = int(input('삭제할 키를 입력하세요 : '))
        tree.remove(key)

    elif menu == Menu.검색:
        key = int(input('검색할 키를 입력하세요'))
        t = tree.search(key)
        if t is not None:
            print(f'이 키를 갖는 값은 {t}입니다.')
        else:
            print('해당하는 데이터가 없습니다.')
    elif menu == Menu.덤프:
        tree.dump()
    elif menu == Menu.키의범위:
        print(f'키의 최솟값은 {tree.min_key()}입니다')
        print(f'키의 최댓값은 {tree.max_key()}입니다')
    else:
        break