본문 바로가기
TIL/Data Structures and Algorithms

(자료구조) 트리구조 (Tree)

parksisi 2021. 1. 26. 08:26

1. 정렬된 배열과 해시 테이블의 단점

- 정렬된 배열은 삽입과 삭제가 느리다. 최악의 시나리오(배열 앞에 값 삽입, 배열 첫번째 값 삭제)의 경우 O(N) 시간복잡도

- 해시 테이블은 순서 유지가 안된다. 

- 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료구조 -> 이진 트리

- 이진 트리와 정렬된 배열의 탐색 비교

 

출처:  https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

 

2. 트리 (Tree) 구조

  • 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
  • 실제로 어디에 많이 사용되나?
    • 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용
    • 브랜치가 최대 2개인 트리구조가 이진 트리이다. 

3. 알아둘 용어

  • 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

 

4. 이진 트리와 이진 탐색 트리 (Binary Search Tree)

  • 이진 트리: 노드의 최대 Branch가 2인 트리
  • 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
    • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!
  • 이진 탐색 트리는 더블 링크드 리스트로 구현

 

5. 자료 구조 이진 탐색 트리의 장점과 주요 용도

  • 주요 용도: 데이터 검색(탐색)
  • 장점: 탐색 속도를 개선할 수 있음

6. 파이썬으로 이진 탐색 트리 구현

 

6.1. 노드 클래스

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

 

6.2 삽입

class NodeMgmt:
	def __init__(self, head):
    	self.head = head
        
    def insert(self, value):
    	self.current_node = self.head
        while True:
           if value < self.current_node.value:
            	if self.current_node.left != None:
            		self.current_node = self.current_node.left
            	else:
            		self.current_node.left = Node(value)
            		break
            else:
            	if self.current_node.right != None:
            		self.current_node = self.current_node.right
            	else:
            		self.current_node.right = Node(value)
            		break

 

삽입의 경우 log N(검색) + 1(삽입) 단계가 걸리며 시간복잡도는 O(log N)이 된다. 정렬된 배열에서는 검색 뿐 아니라 삽입할 공간을 마련하기 위해 많은 데이터를 시프트해야 하므로 삽입에 O(N) 시간복잡도가 걸린다. 

* 정렬된 배열 -> 검색 : O(log N), 삽입 : O(N) 

* 이진 트리    -> 검색: O(log N), 삽입 : O(log N)

이와 같이 이진 트리가 정렬된 배열보다 더욱 효과적임을 알 수 있다. 

 

6.3. 탐색

 

    def search(self, value):
    	self.current_node = self.head:
        while self.current_node:
            if self.current_node.value == value:
            	return True
            elif value < self.current_node.value:
            	self.current_node = self.current_node.left
            else:
            	sefl.current_node = self.current_node.right
        return False

 

위에서 말했듯이 시간복잡도는 O(log N)이다. 각 단계를 수행할 때마다 값이 들어있을 남은 공간 중 반을 제거하기 때문이다.

 

 

6.4. 삭제의 이해

 

가능한 경우의 수는 크게 3가지이다. 

1. leaf node삭제

2. child node가 하나인 node 삭제

  • 삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치로 옮긴다.

3. child node가 두 개인 node 삭제

  • 삭제된 노드를 후속자 노드로 대체한다. 후속자 노드란 삭제된 노드보다 큰 값(오른쪽) 중 최솟값(삭제된 노드보다 큰 값의 제일 왼쪽 노드)

1. 루트노드 삭제

 

2. 후속자노드 탐색
3. 후속자노드를 삭제된 노드에 넣는다

 

  • 만약 후속자 노드에 오른쪽 자식이 있으면 후속자를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

1. 루트삭제. 후속자노드의 오른쪽 자식이 있는것을 알 수 있다.
2. 후속자노드(52)를 루트에 넣는다.

 

 

 

3. 61 후속자노드의 부모였으므로 55는 61의 왼쪽자식이 된다.

6.5. 삭제코드 구현

 

6.5.1. 삭제할 노드 탐색 / Case 1 : 삭제할 노드가 leaf Node

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
    
    # Case1 : 삭제할 노드가 leaf node일 경우
    # self.current_node가 삭제할 노드, self.parent_node가 삭제할 노드의 parent node인 상태
    
    if self.current_node.left == None and self.current_node.right == None: # 현재 leaf Node인 상황
        if value < self.parent_node.value:  # parent node의 왼쪽에 있는 경우
            self.parent_node.left = None
        else:                               # parent node의 오른쪽에 있는 경우
            self.parent_node.right = None
        del self.current_node

 

6.5.2 Case2 : 삭제할 Node가 child node를 한 개 가지고 있을 경우

 

출처 : 잔재미코딩 (https://www.fun-coding.org/Chapter10-tree.html)

    # Case2 : 삭제할 노드가 child node를 한 개 가지고 있을 경우
    
    # child node가 왼쪽에 있을 경우
    if self.current_node.left != None and self.current_node.right == None:
        if value < self.parent_node.value: # current node가 parent의 왼쪽에 있을 때
            self.parent_node.left = self.current_node.left
        else:                              # current node가 parent의 오른쪽에 있을 때
            self.parent_node.right = self.current_node.left
    # child node가 오른쪽에 있을 경우        
    elif self.current_node.left == None and self.current_node.right != None:
        if value < self.parent_node.value: # current node가 parent의 왼쪽에 있을 때
            self.parent_node.left = self.current_node.right
        else:                              # current node가 parent의 오른쪽에 있을 때
            self.parent_node.right = self.current_node.right

 

6.5.3. Case3-1 : 삭제할 Node가 parent node의 왼쪽에 있고 child node를 두 개 가지고 있을 때

  • Case3-1-1 : 삭제할 Node가 parent node의 왼쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 child node가 없을때
  • Case3-1-2 : 삭제할 Node가 parent node의 왼쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 오른쪽에 child node가 있을때

15가 current node이다. 즉 삭제 대상

    if self.current_node.left != None and self.current_node.right != None:  # case3
        if value < self.parent_node.value:  # case 3-1
            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:  # case 3-1-1
                self.change_node_parent.left = None
            self.parent_node.left = self.change_node
            self.change_node.left = self.current_node.left
            self.change_node.right = self.current_node.right

 

 

6.5.4. Case3-2 : 삭제할 Node가 parent node의 오른쪽에 있고 child node를 두 개 가지고 있을 때

  • Case3-2-1 : 삭제할 Node가 parent node의 오른쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 child node가 없을때
  • Case3-2-2 : 삭제할 Node가 parent node의 오른쪽에 있고 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 가진 Node의 오른쪽에 child node가 있을때

41이 current node이다. 즉 삭제 대상

        else:  # case 3-2
            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-2
                self.change_node_parent.left = self.change_node.right
            else:  # case 3-2-1
                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

 

6.6 파이썬 코드 병합

 

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

        
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return 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    

        # case1
        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
        
        # case2
        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
        elif self.current_node.left != None and self.current_node.right != None:
            # case3-1
            if value < self.parent.value:
                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:
                    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.change_node.left
            # case 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_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.right = self.current_node.right
                self.change_node.left = self.current_node.left

        return True

7. 이진탐색트리의 시간복잡도와 단점

7.1 시간복잡도(탐색시)

- depth를 h라 표현한다면 O(h)

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

  - 한번 실행시마다 50%의 실행할 수도 있던 명령을 제거한다는 의미. 50%의 실행시간 단축

- sorted array이 경우는 O(n)이다

 

7.2. 이진탐색트리의 단점

- 평균 시간 복잡도는 O(log n)이지만 이는 트리가 균형잡혀 있을 때의 평균 시간 복잡도

- 최악의 경우(만약 한쪽으로만 치우친 극단적인 경우) 링크드리스트 등과 동일한 성능(O(n))

 

 

** 패스트캠퍼스의 '알고리즘/기술면접 완전 정복 올인원 패키지' 강의를 듣고 작성한 글입니다

'TIL > Data Structures and Algorithms' 카테고리의 다른 글

공간복잡도  (0) 2021.01.26
(자료구조) 힙  (0) 2021.01.26
(자료구조) 해쉬테이블  (0) 2021.01.22
알고리즘 복잡도  (0) 2021.01.22
(자료구조) 링크드리스트 (Linked List)  (0) 2021.01.15

'TIL/Data Structures and Algorithms' Related Articles

티스토리툴바