7. 트리

1. 트리

- 비선형 자료구조

- 계층적 관계를 나타내기 위한 자료구조

2. 트리의 구성 요소

- Node

- 트리를 구성하는 각각의 요소

- Edge

- 노드와 노드를 연결하는 선 

- Root Node

- 트리의 최상위 노드

- Leaf Node

- 하위에 다른 노드가 연결되어 있지 않은 노드

- Internal Node

- leaf node를 제외한 모든 노드

3. 이진 트리

- 루트 노드를 중심으로 두 개의 서브 트리로 나누어 진다

- 서브 트리도 모두 이진 트리여야 한다

- 각 층별로 레벨을 정하고, root node의 레벨은 0 또는 1, 최고 레벨을 height(높이) 라고 한다

- Full Binary Tree(포화 이진 트리)

- 단말 노드를 제외한 모든 노드가 2개의 자식을 갖는 트리

- 노드의 개수는 2^n - 1

- Complete Binary Tree(완전 이진 트리)

- 위쪽 에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워진 이진트리

3. 이진 탐색 트리

- 이진탐색과 연결리스트를 결한한 자료구조

- 이진탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제를 가능하게끔 고안

- 이진 탐색 트리의 규칙

- 이진 탐색 트리의 노드에 저장되는 키는 유일하다

- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다

- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

- 탐색 연산은 Big-O(log n)

- 이진 탐색 트리는 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생

- 배열보다 많은 메모리를 사용하며 데이터를 저장했지만 시간 복잡도가 같아짐

- 이러한 문제를 해결하기 위한 트리로는 AVL, Red Black, 2-3, 2-4, 트리가 있다.

3-1. 이진 탐색 트리 ADT

- init(self)

- 트리를 초기화 한다

- insert(self, data)

- 트리에 데이터를 저장한다

- insert_node(self, node, data)

- 트리에 데이터를 저장하기 위한 재귀 함수이다

- delete(self, data)

- 트리에서 데이터를 삭제한다

- delete_node(self, node, data)

- 트리에서 데이터를 삭제하기 위한 재귀 함수이다

- find(self, data)

- 트리에서 데이터를 탐색

- find_node(self, node, data)

- 트리에서 데이터를 탐색하기 위한 재귀 함수이다.

- pre_order(self, node, data)

- 전위 순회 함수

- 

- 부모노드 방문 -> 왼쪽 서버트리 -> 오른쪽 서브트리

- 전위 순회 결과 : E -> B -> A -> D -> C -> G -> F -> H

- pre_order_recursion(self, node, data)

- 전위 순회 재귀함수

- in_order(self, node, data)

- 중위 순회 함수

- 

- 왼쪽 서브트리에서 왼쪽 에서 오른쪽 노드로 방문 ->루트 노드 방문->오른쪽 서브트리 제일 왼쪽 에서 오른쪽 노드로 방문

- 중위 순회 결과: A -> B -> C -> D -> E -> F -> G -> H

- in_order_recursion(self, node, data)

- 중위 순회 재귀 함수이다. 

- post_order(self, node, data)

- 후위 순회 함수

- 

- 왼쪽노드 -> 오른쪽 노드 -> 부모노드

- 후위 순회 결과 -> A -> C -> D -> B -> F -> H -> G -> E

- post_order_recursion(self, node, data)

- 후위 순회 재귀 함수

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


class BinarySearchTree:
    def __init__(self):
        self.root_node = None
        self.is_root = False
        self.total = 0

    def insert(self, data):
        if not self.root_node:
            self.root_node = Node(data)
            return self.root_node.data
        else:
            node = self.insert_node(self.root_node, data)
            return node.data

    def insert_node(self, node, data):
        if not node:
            return Node(data)

        if node.data > data:
            node.left = self.insert_node(node.left, data)
        else:
            node.right = self.insert_node(node.right, data)
        return node

    def delete(self, data):
        delete_node, is_delete = self.delete_node(self.root_node, data)
        return is_delete

    def delete_node(self, node, data):
        if not node:
            return node, False
        is_delete = False
        if node.data == data:
            is_delete = True
            if node == self.root_node:
                self.is_root = True
            if node.left and node.right:
                parent, child = node, node.right
                while child.left:
                    parent, child = child, child.left
                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.righ
            else:
                node = None
        elif node.data > data:
            node.left, is_delete = self.delete_node(node.left, data)
        else:
            node.right, is_delete = self.delete_node(node.right, data)
        if self.is_root:
            self.root_node = node
        return node, is_delete

    def find(self, data):
        search_result = self.find_node(self.root_node, data)
        return search_result

    def find_node(self, node, data):
        if not self.root_node or not node:
            return False

        if node.data == data:
            return True
        elif node.data > data:
            result = self.find_node(node.left, data)
        else:
            result = self.find_node(node.right, data)
        return result

    def pre_order(self):
        self.pre_order_recursion(self.root_node)

    def pre_order_recursion(self, node):
        if not node:
            return
        print(node.data)
        self.pre_order_recursion(node.left)
        self.pre_order_recursion(node.right)

    def in_order(self):
        self.in_order_recursion(self.root_node)

    def in_order_recursion(self, node):
        if not node:
            return
        self.in_order_recursion(node.left)
        print(node.data)
        self.in_order_recursion(node.right)

    def post_order(self):
        self.post_order_recursion(self.root_node)

    def post_order_recursion(self, node):
        if not node:
            return
        self.post_order_recursion(node.left)
        self.post_order_recursion(node.right)
        print(node.data)


bst = BinarySearchTree()
bst.insert(5)
bst.insert(2)
bst.insert(1)
bst.insert(4)
bst.insert(3)
bst.insert(7)
bst.insert(6)
bst.insert(8)
print(f'pre_order')
bst.pre_order()
print(f'in_order')
bst.in_order()
print(f'post_order')
bst.post_order()
print(f'find 8 : {bst.find(8)}')
print(f'delete 8 : {bst.delete(8)}')
print(f'find 8 : {bst.find(8)}')

---------------------------------------------------

pre_order
5
2
1
4
3
7
6
8
in_order
1
2
3
4
5
6
7
8
post_order
1
3
4
2
6
8
7
5
find 8 : True
delete 8 : True
find 8 : False