Tree(트리)

트리

노드와 브랜치로 구성된 사이클을 이루지 않도록 구성한 데이터 구조

* 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용

 

• Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이
• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
• Child Node: 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

이진 트리

트리 + 노드가 가질 수 있는 최대 브랜치의 개수가 두 개

 

이진 탐색 트리

이진 트리 + 브랜치를 만들 때 해당 노드보다 작은 것은 왼쪽, 큰 것은 오른쪽에 넣음

탐색 할 때 시간을 굉장히 단축 시킬 수 있다.

but, 삭제가 매우 복잡함

 

이진 탐색 트리(Binary Search Tree) 구현

출처:https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

class Node:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None
    
class NodeMgmt:
  def __init__(self, value):
    self.head = Node(value)
    
  def insert(self, value):
    self.curr = self.head
    while True:
      if value < self.curr.value:
        if self.curr.left != None:
          self.curr = self.curr.left
        else:
          self.curr.left = Node(value)
          break
      else:
        if self.curr.right != None:
          self.curr = self.curr.right
        else:
          self.curr.right = Node(value)
          break
          
  def search(self, value):
    self.curr = self.head
    while self.curr:
      if self.curr.value == value:
        return True
      elif value < self.curr.value:
        self.curr = self.curr.left
      else:
        self.curr = self.curr.right
    return False
  
tree = NodeMgmt(5)
tree.insert(3)
tree.insert(9)
tree.insert(15)
print(tree.search(15))  # True
print(tree.search(6))  # False

 

이진 탐색 트리 삭제

삭제할 Node의 브랜치가 없을 때, 하나일 때, 두 개일 때로 나눠서 생각

 

Case 1. Leaf Node 삭제

• Leaf Node: Child Node가 없는 Node
• 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

 

Case 2. Child Node가 하나인 Node 삭제

• 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.

 

Case 3. Child Node가 두 개인 Node 삭제

1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

두 방법 중 하나로 진행 시 트리의 규칙이 깨지지 않음

 

삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우

1. 삭제할 Node의 오른쪽 자식 선택

2. 오른쪽 자식의 가장 왼쪽에 있는 Node 선택

3. 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함

4. 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함

5. 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함

6. 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

 

# 삭제할 Node가 없는 경우: False 리턴하고 함수 종료

def delete(self, value):
  searched = False
  self.current_node = self.head
  self.parent = self.head
  while self.current_node:
    if self.current_node.value == value:
      searched = True
      break
    elif value < self.current_node.value:
      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:
    return False
    
  # 이후부터 Case들을 분리해서, 코드 작성
  
  # Case 1. Leaf Node 삭제
  # self.current_node가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
  if self.current_node.left == None and self.current_node.right == None:
    if value < self.parent.value:
      self.parent.left = None
    else:
      self.parent.right = None
    del self.current_node
    
  # Case 2. Child Node가 하나 있는 Node 삭제
  # 2-1. 삭제할 Node의 left에 Child Node가 있을 경우
  if self.current_node.left != None and self.current_node.right == None:
    if value < self.parent.value:
      self.parent.left = self.current_node.left
    else:
      self.parent.right = self.current_node.left
  # 2-2. 삭제할 Node의 right에 Child Node가 있을 경우      
  if self.current_node.left == None and self.current_node.right != None:
    if value < self.parent.value:
      self.parent.left = self.current_node.right
    else:
      self.parent.right = self.current_node.right
      
  # Case 3-1. Child Node가 두 개 있는 Node 삭제 (삭제할 Node가 parent Node 왼쪽에 있을 때)
  # 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 하는 방법 사용
  
  # but, 또 두 가지 경우로 나뉘는데
  # 3-1-1. 삭제할 Node가 Parent Node의 왼쪽에 있고 
  # 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
  # 3-1-2. 삭제할 Node가 parent Node의 왼쪽에 있고
  # 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
  # -> 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없다. 
  # 왜냐면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문
  
  if self.current_node.left != None and self.current_node.right != None:
    if value < self.current.value:
      # change_node, change_node_parent 초기화
      self.change_node = self.current_node.right
      self.change_node_parent = self.current_node.right
      
      while self.change_node.left != None:
        self.change_node_parent = self.change_node
        self.change_node = self.change_node.left
      if self.change_node.right != None:  # Case 3-1-2
        self.change_node_parent.left = self.change_node.right
      else
        self.change_node_parent.left = None
        
      self.parent.left = self.change_node
      self.change_node.right = self.current_node.right
      self.change_node.left = self.current_node.left
  # Case 3-2. 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)
    else:
      # 위와 마찬가지로 오른쪽 자식의 가장 낮은 값을 찾는 방법은 동일
      # change_node, change_node_parent 초기화
      self.change_node = self.current_node.right
      self.change_node_parent = self.current_node.right
      while self.chenge_node.left != None:
        self.change_node_parent = self.change_node
        self.change_node = self.change_node.left
      if self.change_node.right != None:
        self.change_node_parent.left = self.change_node.right
      else:
        self.change_node_parent.left = None
      self.parent.right = self.change_node
      self.change_node.left = self.current_node.left
      self.change_node.right = self.current_node.right

그림을 그리며 코드를 구현해보자.

 

시간복잡도

depth(트리의 높이)를 h라 하면, 시간복잡도는 O(h)

n개의 노드를 가진다면, h = log₂n에 가까우므로, 시간복잡도는 O(logn)

* 빅오 표기법에서 logn에서의 log의 밑은 10이 아닌, 2

* 한번 실행 시 마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉, 50%의 실행시간을 단축시킬 수 있다는 것을 의미한다.

 

단점

평균 시간복잡도는 O(logn)이지만 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,

최악의 경우, 아래처럼 링크드 리스트 등과 동일한 성능을 보여줌 O(n)