Data Structure (2) Tree (트리)

📌트리

• node와 branch를 이용해서, cycle을 이루지 않도록 구성한 데이터 구조
• 트리 중 binary tree(이진 트리) 형태의 구조는 탐색(search) 알고리즘 구현에 많이 사용됨

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

(출처: wikipedia)

📌용어

• node: 트리에서 데이터를 저장하는 기본 단위(요소)
• root node: tree의 가장 위에 있는 node
• level: 최상위 노드를 level 0 (또는 1)하였을 때, 하위 branch로 연결된 노드의 깊이
• parent node: 어떤 node의 하위 level에 연결된 node
• child node: 어떤 노드의 상위 level에 연결된 node
• leaf node: child node가 없는 node
• sibling (brother node): 동일한 parent node를 가진 노드
• depth: 트리에서 node가 가질 수 있는 최대 level
• width: 한 level에 있는 node의 개수
• breadth: leaf node의 개수

 

📌Binary Tree와 Binary Search Tree

• binary tree: 한 노드가 가질 수 있는 최대 branch(child node)가 2인 트리
• binary search tree (BST): binary tree에서 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 노드는 해당 노드보다 큰 값을 가지고 있는 트리

 

binary search tree의 주요 용도 / 장점

• 주요 용도는 데이터 검색/탐색으로 binary search tree를 이용하면 검색 속도의 이점이 있다.
• BST vs Array

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

 

📌BST 구현 (linked list 활용)

Node class 만들기

class Node:

  def __init__(self, value):
     self.value = value
     self.left = None
    self.right = None

 

Binary Search Tree에 node 삽입

! BST 조건에 맞도록 데이터를 삽입해야 함 (작은 값은 왼쪽에, 큰 값은 오른쪽에)

class NodeMgmt:

  def __init__(self, head):
     self.head = head # root node

  def insert(self, value):
     self.current_node = self.head
     while True:
       if value < self.current_node: #왼쪽으로 삽입
         if self.current_node.left != None: #left에 data가 있는지 확인
           current_node = self.current_node.left #있으면 node 이동(밑 노드 타기)
         else:
           current_node.left = Node(value) #left에 data 없으면 바로 삽입
         break
       else: # value > self.current_node -> 오른쪽으로 삽입
         if self.current_node.right != None: #right에 data가 있는지 확인
           current_node = self.current_node.right #있으면 아래 node 타기
         else:
           current_node.right = Node(value)
           break

 

이진 탐색 트리 탐색 (search() 함수 구현)

데이터가 있는지 없는지 확인하는 함수 (말그대로 검색)

def search(self, value):
     self.current_node = self.head #일단 head부터 search
     while self.current_node:
       if self.current_node == value:
         return True
       elif value < self.current_node:
         self.current_node = self.current_node.left
       else:
         self.current_node = self.current_node.right
     return False #여기까지 왔다는 건 내가 찾는 데이터가 없다는 뜻
{% endhighlight %}

<br>

### <strong><span style = "color:red">이진 탐색 트리 삭제 (delete() 함수 구현)</span></strong>

#### 0) 삭제할 node 탐색

{% highlight python %}
  def delete(self, value):
     searched = False
     self.current_node = self.head
     self.parent = self.head #노드 삭제를 위해서는 parent node도 알고 있으야 하기 때문에 parent변수도 생성해준다.
     while self.current_node:
       if self.current_node == value:
         searched = True
         break
       elif value < self.current_node:
         self.current_node = self.current_node.left
         self.parent = self.current_node
       else:
         self.current_node = self.current_node.right
         self.parent = self.current_node

     if searched == False:
       return False

이렇게 삭제할 node 탐색까지 진행하면 self.current_node가 삭제할 node로 할당되어있고, self.parent는 삭제할 node의 parent node로 할당되어 있는 상태가 된다.

이후 부터는 삭제하는 case를 분리해서 code를 작성한다.

 

Case 1) 삭제할 node의 child node가 0개일 때 (leaf node 삭제)

삭제할 node의 parent node가 삭제할 node를 가리키지 않도록 하기만 하면 끝!
node는 삭제하고 연결 branch는 None으로 초기화

## case1: 삭제할 node의 child node가 0개인 경우
     if self.current_node.left == None and self.current_node.right == None: #leaf node인지 확인!
       if value < self.parent.value: #value값, current_node 자체는 알고 있지만, current_node가 parent의 왼쪽에 있는지, 오른쪽에 있는지는 모르기 때문에 확인해야 한다.
         self.parent.left == None
       else:
         self.parent.left == None

 

Case 2) 삭제할 node의 child node가 1개일 때

2번 case에서 또 경우를 나누어 보면,

1) 삭제하려는 노드가 "왼쪽"에 child node를 가지고 있을 때

• 삭제하려는 노드가 parent node의 왼쪽에 있을 때
• 삭제하려는 노드가 parent node의 오른쪽에 있을 때

2) 삭제하려는 노드가 "오른쪽"에 child node를 가지고 있을 때

• 삭제하려는 노드가 parent node의 왼쪽에 있을 때
• 삭제하려는 노드가 parent node의 오른쪽에 있을 때

## case2: 삭제할 node의 child node가 1개인 경우
     elif 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

     elif 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) 삭제할 node의 child node가 2개일 때

child node가 2개인 경우는 매우 복잡하다...,,ㅠ_ㅠ

우선, case3에서 기본적으로 사용할 수 있는 전략을 2가지 이다. (방향만 반대)

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

나는 1번 전략으로 코드를 구현해보겠다.

세번째 경우에서도 또 경우를 나누면,

Case 3-1) 삭제하려는 노드가 "왼쪽"에 child node를 가지고 있을 때

• Case 3-1-1) change_node의 오른쪽에 child가 있을 때
• Case 3-1-2) change_node의 오른쪽에 child가 없을 때

Case 3-2) 삭제하려는 노드가 "오른쪽"에 child node를 가지고 있을 때

• Case 3-2-1) change_node의 오른쪽에 child가 있을 때
• Case 3-2-2) change_node의 오른쪽에 child가 없을 때

## case3: 삭제할 node의 child node가 2개인 경우
     elif self.current_node.left != None and self.current_node.right != None: # case3
       if value < self.parent.value: #삭제하려는 노드가 "왼쪽"에 child node를 가지고 있을 때
         self.change_node = self.current_node.right
         self.change_node_parent = self.current_node.right
         while self.change_node.left != None: #오른쪽 child 중 가장 작은 값 찾기!(전략1)
           self.change_node_parent = self.change_node
           self.change_node = self.change_node.left #while문은 change_node를 찾아 감을 위함
         if self.change_node.right != None: #Case 3-1-1
           self.change_node_parent.left = self.change_node.right
         else: #Case 3-1-2
           self.change_node_parent.left = None
         self.parent.left = self.change_node
         self.change_node.left = self.current_node.left
         self.change_node.right = self.current_node.right

       else: # 삭제하려는 노드가 "오른쪽"에 child node를 가지고 있을 때
         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-2-1
           self.change_node_parent.left = self.change_node.right
         else: #Case 3-2-2
           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
     return True

 

test code

# test code

# 0~999숫자 중에서 임의로 100개의 숫자를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제

import random
bst_nums = set() #집합 만들기(중복되지 않도록)
while len(bst_nums) != 100:
  bst_nums.add(random.randint(0, 999))

#선택된 100개의 숫자를 이진 탐색 트리에 입력, root node는 임의로 500을 넘음
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
  binary_tree.insert(num)

#입력한 100개의 숫자 search
for num in bst_nums:
  if binary_tree.search(num) == False:
     print("search failed", num)

#입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택하여 삭제
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
  delete_nums.add(bst_nums[random.randint(0, 99)])
for del_num in delete_nums:
  if binary_tree.delete(del_num) == False:
     print("delete failed", del_num)

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

• depth를 h라고 표현하면 BST의 시간 복잡도는 O(h)
• 트리가 n개의 node를 가진다면 h = log(n)에 가까우므로, 시간 복잡도는 O(log n)으로 표현 가능

(빅오 표기법에서 log n에서 log의 밑은 10이 아니라, 2를 의미)

=> 즉, 한 번 실행할 때 마다, 50%의 실행할 수 있는 명령을 제거한다는 의미 (트리가 반씩 쪼개져 가면서 depth는 +1). 즉, 50%의 실행시간을 단축시킬 수 있다는 것을 의미

ex) 균형적인 tree에서 대략 노드가 1개면 depth는1, 노드가 ~3개면 depth는 2, 노드가 ~7개면 depth는 3, 노드가 ~15개이면 depth는 4 ==> 즉, 노드가 n개 이면 depth는 log n에 접근

 

이진 탐색 트리의 단점

: 최악의 경우(트리가 비균형적일 경우) linked list 등과 동일한 성능 $(O(n))$을 보여줌

(평균 시간 복잡도는 $O(log n)$이지만, 이건 트리가 양쪽으로 균형이 잡혀있을 때의 시간복잡도)

ex) branch가 한쪽으로만 뻗어있을 경우, node가 n개 이면, depth도 n이 되기 때문에 시간 복잡도는 $O(n)$이 된다.