이진 트리 (Binary Tree)

트리(Tree) 자료구조

임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 자료구조.
노드 중에서 단 하나의 루트 노드(root node)가 있고, 루트 노드에서 하위 노드(sub node)들이 연결된 비선형 계층 구조.

트리 자료구조의 용도

트리 자료구조의 구현은 배열이나 연결 리스트를 사용한다
주로 운영체제의 파일 시스템에서 사용한다.

이진트리(Binary Tree)

트리 자료구조 중에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조
왼쪽 서브 트리의 값은 루트의 값보다 작고, 오른쪽 서브 트리의 값은 루트보다 큰 값을 갖도록 구성한다.

이진트리 자료구조의 용도

빠른 검색이 필요한 곳에서 사용한다.

이진트리 자료구조 구현

python 3.8
# Binary Tree

class BinaryTree(object):
    def __init__(self):
        self.root = None

    def insert(self, data):
        self.root = self.__insert_data(self.root, data)

    def __insert_data(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self.__insert_data(node.left, data)
            else:
                node.right = self.__insert_data(node.right, data)
        return node

    def find(self, data):
        return self.__find_data(self.root, data)

    def __find_data(self, node, data):
        if node is None or node.data == data:
            return node is not None
        elif data <= node.data:
            return self.__find_data(node.left, data)
        else:
            return self.__find_data(node.right, data)

    def delete(self, data):
        self.root, deleted = self.__delete_data(self.root, data)
        return deleted

    def __delete_data(self, node, data):
        if node is None:
            return node, False

        if data == node.data:
            deleted = True
            # 왼쪽, 오른쪽 모두 있을 때 이동
            if node.left and node.right:
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.right
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            # 왼쪽 이나 오른쪽 한 곳만 있을 때
            elif node.left or node.right:
                node = node.left or node.right
            else:
                node = None
        elif data < node.data:
            node.left, deleted = self.__delete_data(node.left, data)
        else:
            node.right, deleted = self.__delete_data(node.right, data)
        return node, deleted

github : https://github.com/honeybeeveloper/data-structure/blob/develop/binary-tree.py
참고 : 책 <그림으로 정리한 알고리즘과 자료구조>