[자료구조] Binary Tree

오늘은 Tree에 대해 학습하였다.

 

트리와 그래프의 차이점은 무엇일까? 

1. 그래프는 양방향, 트리는 단방향 (부모 -> 자식)

2. 트리는 부모노드를 하나만 가질 수 있다.

 

<트리 순회 방법>

preorder  - M  L  R

F -> B ->  A -> D -> C -> E -> G -> I -> H

inorder - L  M  R

A-> B -> C ->D -> E -> F -> G -> H -> I

postorder - L  R  M

A-> C -> E -> D -> B -> H -> I -> G -> F

 

중앙 노드 값의 위치를 pre, in ,post로 이해하니 쉽게 이해 할 수 있었다.

 

 

<순회 코드>

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

    def preorder(self):
        if self.data:
            print(self.data)
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()

    def inorder(self):
        if self.data:
            if self.left:
                self.left.inorder()
            print(self.data)
            if self.right:
                self.right.inorder()

    def postorder(self):
        if self.data:
            if self.left:
                self.left.postorder()
            if self.right:
                self.right.postorder()
            print(self.data)

 

Binary Search Tree란? 

 

트리의 높이 h정도의 탐색으로 조회가 가능하다 O(logN)

Inorder순회 방식으로 조회시 오름차순으로 가져올 수 있다.

 

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

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

    def insert(self,data):
        if self.root:
            self._insert(data,self.root)
        else:
            self.root = Node(data)

    def _insert(self,data,node):
        if data < node.data:
            if node.left:
                self._insert(data,node.left)
            else:
                node.left = Node(data)

        elif data > node.data:
            if node.right:
                self._insert(data,node.right)
            else:
                node.right = Node(data)
        else:
            print("exist value")

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

    def _find(self,data,node):
        if node.data == data:
            return True
        elif node.data > data and node.left:
            return self._find(data,node.left)
        elif node.data < data and node.right:
            return self._find(data,node.right)
        else:
            return False

    def delete(self, data):
        self.root = self._delete_node(self.root, data)

    def _delete_node(self, root, data):
        if root is None:
            return root

        # 삭제 대상 노드를 찾아 이진 탐색 트리를 재구성하는 로직

        # 삭제 대상 노드의 자식 노드가 없거나 하나만 있는 경우
        if root.data == data:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                # 삭제 대상 노드의 자식 노드가 두 개 있는 경우
                # 오른쪽 서브트리에서 가장 작은 노드를 찾아서 삭제 대상 노드로 대체
                min_node = self._find_min_node(root.right)
                root.data = min_node.data
                root.right = self._delete_node(root.right, min_node.data)

        elif data < root.data:
            root.left = self._delete_node(root.left, data)
        else:
            root.right = self._delete_node(root.right, data)

        return root

    def _find_min_node(self, root):
        if root.left is None:
            return root
        return self._find_min_node(root.left)