Tree

정의

트리구조란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결그래프이다. - wikipedia

개념

• 계층적인 자료를 표현하는데 이용되는 자료구조
• 상위 노드와 하위 노드가 부모-자식 관계로 이어진 자료구조
• 하나의 루트노드는 0개 이상의 자식노드를 가지고, 각각의 노드는 0개 이상의 자식노드를 가진다.
• 용어
  • root node : 부모가 없는 노드
  • leaf node : 자식이 없는 노드
  • size : 자신을 포함한 모든 자손 노드의 개수
  • depth : 루트에서 특정 노드까지 가기 위해 거쳐야 하는 간선의 개수
  • level : 트리의 특정 깊이를 가지는 노드의 집합
  • degree : 각 노드가 가진 간선의 수
  • height : 루트노드에서 가장 깊숙히 있는 노드의 깊이

특징

• Directed Acyclic Graphs의 일종으로 사이클이 존재할 수 없다
• 루트 노드로부터 특정 노드로 가는 경로는 하나뿐이다
• 노드의 개수가 N개라면 간선의 개수는 N-1개이다
• 데이터를 순차적으로 저장하지 않는다
• 모든 자식노드는 단 하나의 부모노드를 가진다

종류

Binary Tree

각 노드의 차수가 2이하인 트리

• Skewed Binary Tree : 모든 노드의 차수가 1이하인 이진트리
  • 선형구조
  • leaf node 탐색 시 모든 노드를 방문해야 하므로 효율적이지 않다
• Complete Binary Tree : 모든 노드가 왼쪽부터 생성되는 이진트리
  • 마지막 레벨을 제외한 모든 레벨이 완전히 채워져있음
  • 마지막 레벨에서 1~2h-1개의 노드를 가질 수 있음
  • 배열을 사용해 효율적으로 표현 가능
• Full Binary Tree : 모든 노드의 차수가 0또는 2인 이진트리
• Perfect Binary Tree : Complete이면서 Full인 이진트리
  • 노드의 개수가 정확히 2^(h-1)이다

Binary Tree 순회

• pre-order : root -> left -> right

  def preorder(root):
      if root:
          print(root.data)                        # root
          if root.left: preorder(root.left)       # left
          if root.right: preorder(root.right)     # right

• in-order : left -> root -> right

  def inorder(root):
      if root:
          if root.left: inorder(root.left)        # left
          print(root.data)                        # root
          if root.right: inorder(root.right)      # right

• post-order : left -> right -> root

  def postorder(root):
      if root:
          if root.left: postorder(root.left)      # left
          if root.right: postorder(root.right)    # right
          print(root.data)                        # root

• level-order : 큐를 사용하여 각 노드를 레벨순으로 순회

  from collections import deque
  
  def level_order(root):
      queue = deque.([root])
      while queue:
          root = queue.popleft()                  # dequeue root node
          if root:
              print(root.data)                    # traverse root node
              if root.left:
                  queue.append(root.left)         # enqueue left subtree
              if root.right:
                  queue.append(root.right)        # enqueue right subtree

Binary Tree 구현

• 인접 리스트 이용
• 배열 : 완전 이진트리의 경우 1번 인덱스를 루트노드로 놓고 왼쪽 노드 부터 순서대로 배열에 저장
  • 자식노드 :
    left child = 부모노드 인덱스 * 2,
    right child = (부모노드 인덱스 * 2) -1
  • 부모노드 : 자식노드 인덱스 // 2

Binary Search Tree

left child < root < right child 를 만족하는 이진트리

• 모든 노드는 중복된 값을 가지지 않는다
• O(logN)에 효율적인 탐색이 이루어진다(배열 탐색시간 : O(N))
• 단, BST가 Skewed인 경우 O(N)에 탐색, 삽입, 삭제가 이루어진다

Binary Search Tree 동작

• 탐색

  1. target == root이면 탐색종료
  2. target < root이면 left subtree 탐색
  3. target > root이면 right subtree 탐색

• 삽입

  1. 삽입할 노드의 키값에 대한 탐색 수행
  2. 탐색이 실패하면 탐색이 끝난 지점에 노드 삽입

• 삭제

  1. 삭제할 노드의 키값에 대한 탐색 수행
  2. 삭제할 노드가 leaf node인 경우
     • leaf node 삭제
  3. 삭제할 노드가 하나의 subtree를 가지는 경우
     • 노드 삭제 후 subtree의 root를 삭제한 노드의 부모노드와 연결
  4. 삭제할 노드가 두개의 subtree를 가지는 경우
     • 노드 삭제 후 삭제한 노드의 자리에 왼쪽 subtree에서 가장 큰 값 또는 오른쪽 subtree에서 가장 작은 값은 넣음

Binary Search Tree 구현

• 직접 구현

  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):
          self.root = self._insert_value(self.root, data)
          return self.root is not None
  
      def _insert_value(self, node, data):
          if node is None:                                            
              node = Node(data)                                       # node를 생성
          else:
              if data <= node.data:                                   # data가 현재노드의 값보다 작거나 같으면
                  node.left = self._insert_value(node.left, data)     # left child로 이동
              else:                                                   # data가 현재노드의 값보다 크면
                  node.right = self._insert_value(node.right, data)   # right child로 이동
          return node
  
      def search(self, key):
          return self._search_value(self.root, key)
  
      def _search_value(self, root, key):
          if root is None or root.data == key:                        # 현재 노드가 찾는 값이면
              return root is not None                                 # 현재 노드를 반환
          elif key < root.data:                                       # 찾는 값이 현재 노드의 값보다 작으면
              return self._search_value(root.left, key)               # left child로 이동
          else:                                                       # 찾는 값이 현재 노드의 값보다 크면
              return self._search_value(root.right, key)              # right child로 이동
  
      def delete(self, key):
          self.root, deleted = self._delete_value(self.root, key)
          return deleted
  
      def _delete_value(self, node, key):
          if node is None:                                                # 만약 찾는 노드가 없으면
              return node, False                                          # False를 반환
  
          deleted = False
          if key == node.data:                                            # 삭제하려는 노드를 찾으면
              deleted = True                                              # True를 반환
  
              if node.left and node.right:                                # child가 둘 다 있으면
                  parent, child = node, node.right                        # 현재 노드의 right child의 left leaf를 찾고
                  while child.left is not None:
                      parent, child = child, child.left                   
  
                  child.left = node.left                                  # 현재 노드로 올림
                  if parent != node:
                      parent.left = child.right                           # 올리기 전에 right child를 parent의 left child로 연결
                      child.right = node.right
                  node = child
  
              elif node.left or node.right:                               # child가 하나만 있으면
                  node = node.left or node.right                          # child를 현재 노드로 올림
              else:                                                       # child가 없으면
                  node = None                                             # 현재 노드 삭제
  
          elif key < node.data:                                           # 만약 찾는 값이 현재 값보다 작으면
              node.left, deleted = self._delete_value(node.left, key)     # left child로 이동
          else:                                                           # 만약 찾는 값이 현재 값보다 크면
              node.right, deleted = self._delete_value(node.right, key)   # right child로 이동
  
          return node, deleted

• bisect 모듈 : 정렬된 배열에서 특정 원소를 찾는 모듈

  • bisect_left(a, x) : 정렬된 리스트 a에서 x를 삽입할 가장 왼쪽 인덱스를 반환
  • bisect_right(a, x) : 정렬된 리스트 a에서 x를 삽입할 가장 오른쪽 인덱스를 반환

활용

• 계층적으로 데이터를 저장할 때 사용
  • OS의 파일시스템
• 저장된 데이터를 효과적으로 탐색하기 위해 사용
• 데이터베이스 인덱싱 : B-Tree, B+ Tree, AVL Tree
• 검색엔진
• DOM(Document Object Model)

Heap

정의

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 를 기본으로 한 자료구조이다. - wikipedia

개념

• 부모-자식관계의 노드 사이에 대소관계가 성립하는 완전 이진트리
  • 최대 힙 : 부모의 키값이 자식의 키값보다 큰 힙
  • 최소 힙 : 부모의 키값이 자식의 키값보다 작은 힙
• 우선순위 큐를 구현할 수 있는 자료구조
  • 우선순위 큐 : 우선순위가 높은 데이터가 먼저 나가는 큐

특징

• BST와 달리 중복이 허용된다
• 우선순위가 가장 높은 노드가 root에 있다
• 최댓값이나 최솟값을 찾는데 O(1)이 소요된다
• 반 정렬 상태(느슨한 정렬 상태)를 유지한다

동작

• 탐색 : root노드를 반환
  • O(1)
• 삽입
  1. 새로운 노드를 힙의 마지막 노드에 추가한다
  2. 새로 추가된 노드를 부모노드와 비교하면서 정렬한다
  • O(logN)
• 삭제
  1. 루트노드가 삭제되면 힙의 마지막 노드를 루트로 올린다
  2. 새로 루트가 된 노드를 자식노드와 비교하면서 정렬한다
  • O(logN)

구현

• heaqq 모듈 : 우선순위 큐 알고리즘 제공(최소 힙)

  import heapq
  
  heap = []                   # 빈 리스트 생성
  heapq.heappush(heap, 10)    # heappush(a, x) : 힙 a에 x 삽입
  heapq.heappush(heap, 6)
  heapq.heappop(heap)         # heappop(a) : 힙 a의 루트노드 반환 후 삭제
  heapq.heapify(heap)         # heapify(a) : 리스트 a를 힙으로 변환
  
  # 최대 힙은 키값의 부호를 바꿔주는 방법으로 사용

• 직접 구현 : 배열을 이용하여 구현. 자식노드 인덱스 // 2 = 부모노드 인덱스

  class Heap:
  def __init__(self):
      self.heap = []
      self.heap.append(None)                              # index는 1번부터 시작
  
  def check_swap_up(self,idx):   
      if idx <= 1:                                        # parent가 없으면
          return False                                    # False 반환
      parent_idx = idx // 2                               # parent index 계산
      if self.heap[idx] > self.heap[parent_idx]:          # 부모 노드보다 값이 크면
          return True                                     # True 반환(swap o)
      else:                                               # 부모 노드보다 값이 작으면
          return False                                    # False 반환(swap x)
  
  def insert(self, data):
      self.heap.append(data)                              # 힙의 맨 뒤에 추가
      idx = len(self.heap) - 1                            
  
      while self.check_swap_up(idx):                      # 부모 노드보다 값이 크면
          parent_idx = idx // 2                           # 두 노드의 위치를 바꿈
          self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]   
          idx = parent_idx                                
  
      return True
  
  def check_swap_down(self, idx):
      left_idx = idx * 2
      right_idx = idx * 2 + 1
  
      if left_idx >= len(self.heap):                      # child가 없으면
          return False                                    # False 반환(swap x)
  
      elif right_idx >= len(self.heap):                   # left child만 있으면
          if self.heap[left_idx] > self.heap[idx]:        # left child가 부모 노드의 값보다 크면
              self.flag = 1
              return True                                 # True 반환(swap o)
          else:                                           # left child가 부모 노드의 값보다 작으면
              return False                                # False 반환(swap x)
  
      else:                                               # 양쪽 child가 모두 있으면
          if self.heap[left_idx] > self.heap[right_idx]:  # left child가 right child보다 크면
              if self.heap[left_idx] > self.heap[idx]:    # left child가 부모 노드의 값보다 크면
                  self.flag = 1
                  return True                             # True 반환(swap o)
              else:                                       # left child가 부모 노드의 값보다 작으면
                  return False                            # False 반환(swap x)
          else:                                           # left child가 right child보다 작으면
              if self.heap[right_idx] > self.heap[idx]:   # right child가 부모 노드의 값보다 크면
                  self.flag = 2
                  return True                             # True 반환(swap o)
              else:                                       # right child가 부모 노드의 값보다 작으면
                  return False                            # False 반환(swap x)
  
  def pop(self):
      if len(self.heap) <= 1:                             # parent가 없으면
          return None                                     # None을 반환
  
      max = self.heap[1]                                  # root의 값을 꺼냄
      self.heap[1] = self.heap[-1]                        # 마지막 노드를 root로 올림
      del self.heap[-1]                                   # 맨 뒤 노드 삭제
      idx = 1
      self.flag = 0                                       # 0 = False, 1 = left child와 swap, 2 = right child와 swap
  
      while self.check_swap_down(idx):                    # 자식 노드가 부모 노드보다 값이 크면
          left_idx = idx * 2
          right_idx = idx * 2 + 1
  
          if self.flag == 1:                              # left child와 swap
              self.heap[idx], self.heap[left_idx] = self.heap[left_idx], self.heap[idx]
              idx = left_idx
          elif self.flag == 2:                            # right child와 swap
              self.heap[idx], self.heap[right_idx] = self.heap[right_idx], self.heap[idx]
              idx = right_idx
  
      return max                                          # 아까 꺼낸 root의 값을 반환

활용

• 우선순위 큐
• 힙 정렬
• 작업 스케줄링
• 트래픽 제어