이진 트리

트리

트리는 노드를 연결해 계층 구조를 만드는 비선형 추상 데이터 타입이다.
트리에는 일반 트리, AVL 트리, 레드 블랙 트리, 이진 트리, 이진 탐색 트리가 있다.

일반 트리

맨 위에 하나의 노드를 두고 시작하는 자료구조를 말한다.

• 루트노드 : 트리의 맨 위에 있는 노드
• 자식 노드 : 아래로 연결된 노드
• 부모노드 : 하나 이상의 자식 노드를 가지고 있는 노드
• 형제노드 : 같은 부모를 공유하는 노드
• 리프노드 : 자식 노드가 없는 노드
• 브랜치 노드 : 자식 노드가 있는 노드

• 에지: 두 노드 사이의 연결

두 노드가 에지를 공유하면 한 노드에서 다른 노드로 이동할 수 있다.

이진 트리

각각의 노드가 최대 두 개의 자식 노드만 가질 수 있는 트리 자료구조이다.
➡️ 따라서 루트노트들 제외한 모든 노드는 부모노드의 왼쪽 혹은 오른쪽 노드이다.

이진 탐색 트리

각각의 노드가 최대 두 개의 자식 노드만 가질 수 있는 트리 자료구조이다.
힌 노드의 값은 왼쪽 모든 노드보다 크고 오른쪽 노드보다는 작도록 정렬하려 저장하는 트리 자료구조이다.
중복 값을 저장할 수 없으나 트리의 객체에 횟수를 추가해서 중복 값을 처리할 수 있다.

트리를 사용해야할 때

일반 트리나 이진트리는 모두 O(n)이다.

	접근	탐색	삽입	삭제
이진 탐색 트리	O(log n)	O(log n)	O(log n)	O(log n)

이진 탐색 트리에서는 이진탐색을 사용할 수 있기 때문에 모두 로그함수를 따른다.

트리를 사용하면 배열이나 링크드리스트로 표현하기 어려운 계층적 자료구조를 저장할 수 있다. HTML, XML도 트리의 계층적 구조이다. 수학식을 파스트리로 나타낼 수 있다.

해시테이블과 비교했을 떄 이진 탐색 트리의 장점

• 해시테이블에 비해 메모리를 낭비하지 않고 아낄 수 있다.
• 이진 탐색 트리는 데이터의 정렬된 순서나 역순으로 빠르게 이동할 수 있다.

이진 트리 코드

파이썬에서 이진 트리 만들기

class BinaryTree:
    def __init__(self,value):
        self.key = value
        self.left_child = None
        self.right_child = None
    def insert_left(self,value):
        if self.left_child == None:
            self.left_child = BinaryTree(value)
        else:
            bin_tree = BinaryTree(value)
            bin_tree.left_child = self.left_child
            self.left_child = bin_tree
    def insert_right(self,value):
        if self.right_child == None:
            self.right_child = BinaryTree(value)
        else:
            bin_tree = BinaryTree(value)
            bin_tree.right_child = self.right_child
            self.right_child = bin_tree

트리 탐색 - 너비 우선 탐색 (DFS)

    def breadth_first_search(self,n):
        current = [self]
        next = []
        while current:
            for node in current:
                if node.key == n:
                    return True
                if node.left_child:
                    next.append(node.left_child)
                if node.right_child:
                    next.append(node.right_child)
            current = next
            next = []
        return  False

트리 탐색 - 깊이 우선 이동 (BFS)

• 전위 이동 (Pre-order traversal):
  - 현재 노드를 방문합니다.
  - 왼쪽 서브트리를 전위 이동으로 순회합니다.
  - 오른쪽 서브트리를 전위 이동으로 순회합니다.
  이 방법은 노드를 루트-왼쪽-오른쪽 순서로 방문합니다.

• 후위 이동 (Post-order traversal):
  - 왼쪽 서브트리를 후위 이동으로 순회합니다.
  - 오른쪽 서브트리를 후위 이동으로 순회합니다.
  - 현재 노드를 방문합니다.
  이 방법은 노드를 왼쪽-오른쪽-루트 순서로 방문합니다.

• 중위 이동 (In-order traversal):
  - 왼쪽 서브트리를 중위 이동으로 순회합니다.
  - 현재 노드를 방문합니다.
  - 오른쪽 서브트리를 중위 이동으로 순회합니다.
  이 방법은 노드를 왼쪽-루트-오른쪽 순서로 방문합니다.

중위 이동은 이진 탐색 트리에서 노드를 오름차순으로 방문할 때 유용합니다. 전위 이동과 후위 이동은 트리의 구조를 분석하거나 트리를 복제하는 데 사용될 수 있습니

전위이동 탐색

    def dislocation_movement(self,n):
        current = self
        if current.key == n:
            return True
        elif current.right_child:
            if current.right_child.dislocation_movement(n):
                return True
        elif current.left_child:
            if current.left_child.dislocation_movement(n):
                return True
        return False

이진 트리 뒤집기