[Algorithm] 트리

* Python을 기준으로 합니다

---

트리 (Tree)

- 개념

• 트리 : 계층형 구조를 가지는 자료구조로써 순환 (Cycle)이 존재하지 않는 그래프
  • 트리는 재귀적인 특성을 가지는 자기 참조 자료구조임
    - 즉, 트리의 모든 노드는 자기 자신을 root로 하는 다른 서브 트리로 대표될 수 있음
  • 트리의 한 노드가 가질 수 있는 child의 수에는 제한이 없지만, 일반적으로 최대 2개의 child 만을 가지는 이진 트리를 자주 활용함

트리의 구조

• 이진 트리 (Binary Tree)
  • 모든 노드가 최대 2개의 child만을 가지고, 왼쪽과 오른쪽의 child가 구별 가능한 트리
  • 이진 트리의 종류
    1. 정 이진 트리 : 모든 노드가 0 or 2개의 child를 가지는 트리
    2. 완전 이진 트리 : 마지막 level을 제외한 트리의 각 level의 모든 노드가 채워져 있는 트리
       - 마지막 level에서 노드는 반드시 가장 왼쪽부터 채워져야 함
    3. 포화 이진 트리 : 모든 노드가 2개의 child를 가지고 있고, 모든 leaf 노드가 동일한 level을 가지는 트리
       - 높이가 $k$인 포화 이진 트리의 전체 노드 수는 $2^{k}-1$
       - 포화 이진 트리는 각 노드에 순서대로 index를 부여할 수 있음 (위에서 아래, 좌에서 우 방향으로)
    4. 균형 이진 트리 : 모든 노드에서 서브 트리의 높이 차이가 1 이하인 트리
  • 이진 트리의 순회 : 일반적으로 재귀적인 방식으로 구현함
    1. 전위 순회 (Pre-order traversal, NLR)
       - 현재 노드 (parent)를 기준으로 parent -> left child -> right child 순회
    2. 중위 순회 (In-order traversal, LNR)
       - 현재 노드 (parent)를 기준으로 left child -> parent -> right child 순회
    3. 후위 순회 (Post-order traversal, LRN) 
       - 현재 노드 (parent)를 기준으로 left child -> right child -> parent 순회
    4. 레벨 순회 (Level order traversal)
       - Level 순으로 노드를 방문 (위에서 아래, 좌에서 우로 순회)
       - 이때는 재귀가 아닌 큐를 활용함 (큐에서 노드가 dequeue 되는 순서가 트리를 방문하는 순서)
  • 순회 방식의 선택
    - Child를 먼저 처리해야 parent를 처리할 수 있는 경우 후위 순회를 사용
    - Parent가 먼저 결정되어야 child를 결정할 수 있는 경우 전위 순회를 사용
• 이진 탐색 트리 (Binary Search Tree, BST)
  • 정렬된 이진 트리로써, 이진 트리의 값 삽입 시 노드의 값 보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 배치하는 트리
    - 탐색 시 $O(\log n)$의 time complexity를 가짐
  • 최악의 경우 이진 탐색 트리의 time complexity는 $O(n)$을 가지는데, 이를 방지하기 위해 트리의 균형을 맞추는 균형 이진 트리를 사용하기도 함
    - AVL 트리, Red-Black 트리 등
  • 이진 탐색 트리의 순회
    1. 탐색하려는 값이 현재 노드의 값과 같으면 탐색을 종료함
    2. 탐색할 값이 현재 노드보다 작으면 왼쪽 트리를, 크면 오른쪽 트리를 탐색함
    3. 값을 찾을 때까지 위 과정을 반복

- 구현

1. 배열을 통한 트리 표현

• 구현하고자 하는 이진 트리는 포화 이진 트리의 부분 집합으로 보고, 배열의 index를 활용하는 방법
  1. Root를 index 1로 설정함
  2. Parent 노드의 배열 index $i$에 대한 왼쪽 child 노드의 배열 index = $2i$
  3. Parent 노드의 배열 index $i$에 대한 노드 $i$의 오른쪽 child 노드의 배열 index = $2i+1$
• 배열 방식은 구현은 간단하지만 메모리 공간을 비효율적으로 사용함

배열을 통한 표현

2. 연결 리스트를 통한 트리 표현

• 왼쪽, 오른쪽을 가리키는 link가 존재하는 연결 리스트를 사용하는 방식
  - 트리 구현 시 일반적으로 사용하는 방식

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

3. 트리의 순회 : 전위/중위/후위/레벨 순회

• 전위 순회 : parent -> left child -> right child

def preorder(tree):  # 전위순회
    if tree is None:
        return

    print(tree.data) # parent 방문
    preorder(tree.left) # left child
    preorder(tree.right) #right child

• 중위 순회 : left child -> parent -> right child

def inorder(tree):  # 중위순회
    if tree is None:
        return

    inorder(tree.left) #left child
    print(tree.data) #parent 방문
    inorder(tree.right) #right child

• 후위 순회 : left child -> right child -> parent

def postorder(tree):  # 후위순회
    if tree is None:
        return

    postorder(tree.left) #left child
    postorder(tree.right) #right child
    print(tree.data) #parent 방문

• 레벨 순회 : 위 -> 아래, 같은 level에서는 좌 -> 우

import collections

def levelorder(tree):
  queue = collections.deque() #큐 선언
  queue.append(tree)
  
  while queue:
    node = queue.popleft() #큐에서 dequeue
    
    if node is not None:
      print(node.data)
      queue.append(node.left) #left child
      queue.append(node.right) #right child

4. 이진 탐색 트리

• 현재 노드 값보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 삽입하는 정렬된 트리
  
  1. 탐색하려는 값이 현재 노드의 값과 같으면 탐색을 종료함
  2. 탐색할 값이 현재 노드보다 작으면 왼쪽 트리를, 크면 오른쪽 트리를 탐색함
  3. 값을 찾을 때까지 위 과정을 반복

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


class BST: #이진 탐색 트리
  def __init__(self):
    self.root = None
    
  def insert(self, key):
    if not self.root:
      self.root = Node(key) #root가 없으면 root 추가
    else:
      cur = self.root

      while True:
        if key < cur.val: #현재 값보다 작으면 left로
          if cur.left:
            cur = cur.left
          else:
            cur.left = Node(key)
            break
        else: #현재 값보다 크면 right로
            if cur.right:
              cur = cur.right
            else:
              cur.right = Node(key)
              break

  def search(self, key):
    cur = self.root

    while cur and cur.val != key:
      if key < cur.val: #탐색할 값이 현재 값보다 작으면 left
        cur = cur.left
      else: #아니면 right
        cur = cur.right

    if cur is None:
      return False
    else:
      return True

if __name__ == '__main__':
    bst = BST()
    num = [50, 30, 24, 5, 28, 45, 98, 52, 60]
    for i in num:
        bst.insert(i)

    print(bst.search(1000)) #False
    print(bst.search(24)) #True