4. 자료구조 - 트리

1. 트리 구조

   : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

   : 이진트리의 구조로 탐색 알고리즘 구현을 위해 주로 사용

   : 장점 - 배열에 비해서 탐색 시간이 크게 줄어듦

            -> 시간 복잡도: O(logn) : 레벨을 거칠 때마다 탐색이 1/2씩 일어남

 

   - 관련 basic 용어

     : Node) 데이터와 다른 데이터에 연결된 branch 정보를 포함

     : Root (최상위) / Parent ( 상위 레벨) / Child (다음 레벨) / Sibling (같은 부모 노드) / Leaf (마지막 노드)

     : Level) Root가 Level 1, 아래로 갈수록 레벨이 높아짐

     : Depth) 트리에서 노드가 가질 수 있는 최대 Level

 

2. 이진 트리와 이진 탐색 트리 ( Binary Search Tree, BST)

   : 이진 트리 - 노드의 최대 branch가 2개인 트리

   : 이진 탐색 트리 - 이진트리에 노드의 배치에 대한 추가 조건이 있는 트리

       -> 조건 : 왼쪽 자식 노드 < 현재 노드 < 오른쪽 자식 노드 

 

3.1 기본 구현 - 데이터 삽입/탐색

   1) 노드 만들기

 

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

 

   2) 데이터 삽입/탐색 - 이진트리 탐색 조건

   

       : 노드 삽입, 탐색, 삭제 메서드 모두 "NodeEdit"라는 클래스 안에 정의함

       : 삽입) 현재 노드 기준으로 값이 더 작은지 큰지에 대한 case를 나누고, 각 각에 대해 해당 방향 자식 노드의 유무

         로 세부 case를 나눔

 

class NodeEdit:
   def __init__(self,head):
      self.head = head      # root node
 
   def insert(self,data):
      self.current_node = self.head   #From current_node
      while True:
         if data < self.current_node.data:
            if self.current_node.left != None:        # left child node가 있으면 그 값과 다시 비교해야함.
               self.current_node = self.current_node.left   # 따라서, left child node를 current node로 재 설정
            else:
               self.current_node.left = Node(data)
               break               # 새 노드를 만들었으므로 loop을 빠져나감
         else:
            if self.current_node.right != None:
               self.current_node = self.current_node.right
            else:
               self.current_node.right = Node(data)
               break
   
   def search(self,data):
      self.current_node = self.head     #From current_node
      while True:
         if self.current_node.data == data:
            return True
         elif data < self.current_node.data:
            self.current_node = self.current_node.left
         else:
            self.current_node = self.current_node.right
       return False     # 이 line에 도달했다는  해당 value가 트리에 없다는 의미
       
               

 

head = Node(1)
BST = NodeEdit(head)   #initialize the tree root node

BST.insert(0.5)
BST.insert(3)
BST.insert(2)

BST.search(3)
>>>True

 

   3) 데이터 삭제

       : 복잡하기 때문에 각 case를 나누어서 보는 게 좋음

 

       - Case 1) Leafe Node 삭제 (자식 노드가 없음)

          > 삭제할 노드의 부모 노드 branch가 None을 가리키도록 설정 (연결 끊기)

 

       - Case 2) 하나의 자식 노드가 있음

          > 삭제할 노드의 부모 노드 branch가 삭제할 노드의 자식노드를 가리키도록 설정

 

       - Case 3) 자식 노드가 두 개 다 있음

          > 전략이 2가지 존재, 그 중 하나만 만족하면 이진 탐색 트리 규칙이 깨지지 않음

          > 전략 1) 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 설정

          > 전략 2) 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 부모 노드가 가리키도록 설정

             [전략 1 example]

             - 삭제할 노드의 오른쪽 자식 중 가장 왼쪽에 있는 노드 선택

             - 해당 노드를 삭제할 노드의 부모 노드가 가리키게 함

             - 삭제할 노드의 각 브랜치가 해당 노드의 해당 방향 자식 노드를 가리키도록 함

             

             * 만약 해당 노드가 오른쪽 자식 노드를 가지고 있었을 경우 (해당 노드가 가장 왼쪽이므로 왼쪽 자식 노드는

               있을 수 없음), 그 자식 노드를 해당 노드의 원래 부모 노드의 왼쪽 브랜치가 가리키게 함 

               ( 오른쪽 자식 노드이므로 해당 노드 값보다는 크지만, 여전히 왼쪽 자식 노드 중 하나이므로 부모 노드 값

                 보다는 작기 때문)          

 

## 위에서 정의한 NodeEdit 클래스에 들어가는 메소드 ##
## 삭제 할 노드가 없는 경우 False 리턴, 삭제 할 노드 있는 경우 삭제하고 True 리턴 ##

def delete(self, data):
   searched = False
   self.current_node = head     # 삭제도 root부터 탐색 시작
   self.parent = None 
  
   while self.current_node:                     # 해당 값을 찾아서 탐색
      if self.current_node.data ==data:
         searched = True
         break
      elif data < self.current_node:
         self.parent = self.current_node
         self.current_node = self.current_node.left
      else:
         self.parent = self.current_node
         self.current_node = self.current_node.right
   if searched == False:     # self.current_node == None이 되었는데도 값을 못 찾은 경우   
      return False
      
   ## Case 1 - No child node
   if self.current_node.left == None and self.current_node.right == None:
      if data < self.parent.data:
         self.parent.left = None
      else:
         self.parent.right = None
      del self.current_node

   ## Case 2 - One child node
   # Right child node exist
   if self.current_node.left == None and self.current_node.right != None:
      if data < self.parent.data:
         self.parent.left = self.current_node.right
      else:
         self.parent.right = self.current_node.right
      del self.current_node
   
   # Left child node exist
   elif self.current_node.left != None and self.current_node.right == None:
      if data < self.parent.data:
         self.parent.left = self.current_data.left
      else:
         self.parent.right = self.current_data.left
         
   ## Case 3 - Two child node (전략 1 사용)
   if self.current_node.left != None and self.current_node.right != None:
   
   # 3.1) 삭제할 노드가 부모 노드의 왼쪽에 있음
      if data < self.parent.data:
         self.change_node = self.current_node.right
         self.change_node_parent = self.current_node.right
         while self.change_node.left != None:
            self.change_node = self.change_node.left
            self.change_node_parent = self.change_node
  
   # 3.3.1) 삭제할 노드의 오른쪽 자식 중 가장 왼쪽 노드의 오른쪽 자식 노드가 있는 경우
         if self.change_node.right != None:
            self.change_node_parent.left = self.change_node.right
            
   # 3.3.2) 삭제할 노드의 오른쪽 자식 중 가장 왼쪽 노드의 오른족 자식 노드가 없는 경우
         else:
            self.change_node_parent.left = None
            
         self.parent.left = self.chagne_node
         self.change_node.left = self.current_node.left
         self.change_node.right = self.current_node.right
         
   # 3.2) 삭제할 노드가 부모 노드의 오른쪽에 있음
      else:
         self.change_node = self.current_node.right
         self.change_node_parent = self.current_node.right
         while self.change_node.left != None:
            self.change_node = self.change_node.left
            self.change_node_parent = self.change_node
            
   # 3.3.1) 삭제할 노드의 오른쪽 자식 중 가장 왼쪽 노드의 오른쪽 자식 노드가 있는 경우
         if self.change_node.right != None:
            self.change_node_parent.left = self.change_node.right
            
   # 3.3.2) 삭제할 노드의 오른쪽 자식 중 가장 왼쪽 노드의 오른족 자식 노드가 없는 경우
         else:
            self.change_node_parent.left = None
            
         self.parent_right = self.change_node
         self.change_node.right = self.current_node.right
         self.change_node.left = self.current_node.left
         
      del self.current_node
   return True
   

 

4. 이진 탐색 트리의 시간 복잡도

   - (탐색 시) 시간 복잡도

     : Depth가 h이고 n개의 노드를 가진다고 하면, h = logn에 가까움

     : 한 번 실행마다, 실행을 50% 감소시킴

     > O(logn)

 

   - 단점) 균형된 트리일 경우 평균 시간 복잡도는 위와 같지만, 만약 트리가 한쪽 방향으로만 일직선으로 구성된다면

            최악의 경우, 링크드 리스트와 동일한 성능을 보여줌 O(n)