[자료구조] 트리(Tree)란?

Posted on | In
트리의 개념과 용도. 이진 트리와 이진 탐색 트리의 차이. 파이썬으로의 구현. 트리의 시간 복잡도와 단점

트리(Tree)란?

  • 노드(Node)와 브랜치(Branch)를 이용하여 사이클을 이루지 않도록 구성한 데이터 구조이다.
    • 트리 중 이진 트리(Binary Tree) 형태의 구조로 탐색 알고리즘 구현을 위해 많이 사용된다.

용어

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

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

  • 이진 트리: 노드의 최대 브랜치가 2인 트리이다.

  • 이진 탐색 트리(BST, Binary Search Tree): 이진 트리에 추가적인 조건이 있는 트리이다.
    • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

이진 탐색 트리의 장점과 용도

  • 데이터 검색(탐색)에서 굉장히 많이 쓰인다.
  • 장점은 탐색 속도를 개선할 수 있다는 점이다.

배열과 비교

구현

1. 노드 클래스 생성

1
2
3
4
5
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

2. 데이터 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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


head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)

3. 데이터 탐색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
        

head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)


BST.search(-1)
'''
False
'''

4. 데이터 삭제

  • 매우 복잡하여 경우를 나눠 이해할 것이다.

4.1. 리프노드 삭제

  • 삭제할 노드의 부모 노드가 삭제할 노드를 가리키지 않도록 한다.

4.2. 자식노드 하나인 노드 삭제

  • 삭제할 노드의 부모 노드가 삭제할 노드의 자식 노드를 가리키도록 한다.

4.3. 자식노드 둘인 노드 삭제

  • 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 한다.
  • 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 부모 노드가 가리키도록 한다.
4.3.1. 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 할 경우
  1. 삭제할 노드의 오른쪽 자식을 선택한다.
  2. 오른쪽 자식의 가장 왼쪽에 있는 노드를 선택한다.
  3. 해당 노드를 삭제할 노드의 부모 노드의 왼쪽 브랜치가 가리키게 한다.
  4. 해당 노드의 왼쪽 브랜치가 삭제할 노드 왼쪽 자식 노드를 가리키게 한다.
  5. 해당 노드의 오른쪽 브랜치가 삭제할 노드 오른쪽 자식 노드를 카리키게 한다.
  6. 만약 해당 노드가 오른쪽 자식 노드를 갖고 있을 경우, 해당 노드의 본래 부모 노드의 왼쪽 브랜치가 해당 오른쪽 자식 노드를 가리키게 한다.

삭제할 수 있는 코드를 짜고, 전체 코드를 짜보자.

시간 복잡도와 단점

시간 복잡도

  • 깊이를 h라고 표기한다면 $O(h)$가 걸린다.
  • $n$개의 노드를 가진다면, $h=log_2{n}$에 가까우므로, 시간복잡도는 $O(log{n})$이다.

단점

  • 평균 시간 복잡도는 $O(log{n})$이지만, 이는 트리가 균형잡혀 있을 때의 평균 시간 복잡도이며, 위 이미지와 같이 구성되어있을 경우, 최악의 경우는 연결 리스트와 동일한 성능($O(n)$)을 보여준다.
0%