[09-1] 트리(Tree)란?

 

벌써 트리구조까지 왔다.

트리(Tree)구조는 말그래도 트리모양으로 생각하면 된다. 가지치기 된 모양이다. 그림으로 이해해보자.

 

트리(Tree) 구조

 

트리란?

서로 연결된 노드의 계층형 자료구조이며, 부모-자식 관계로 구성되어 있다.

트리구조의 용어

트리를 올바르게 이해하기 위해선 용어들을 이해해야 한다.

 

- 각 노드들이 있고, 노드들을 연결해서 트리를 만든다.

- 루트노드(root): 맨 처음(시작) 노드(A)

- 리프노드(leaf): 더이상 뻗어나갈 수 없는 노드

- 자식노드(child), 부모노드(parent), 형제노드(sibling): 계층 구조를 확인하며 상대적 개념

- 차수(degree) : 노드가 갖는 자식의 수. 모든 노드가 n개 이하의 트리를 가진 n진 트리라고 정의.(그림은 3진 트리)

- 높이(height): 가장 멀리있는 리프 노드부터 루트노드까지의 거리

- 레벨(level): 루트부터 level0으로 같은 라인

- 서브트리(subtree): 트리의 어떤 노드를 루트로 하며, 그 child로 구성된 트리

 

실제 코딩테스트에서는 Binary tree(이진트리)가 많이 활용된다.

이진트리의 구조를 살펴보자.

이진트리 구조

 

이진트리의 구조는 다음과 같다.

value 값을 갖고 있고, LC(Left Child), RC(Right child)를 가지고 있으며 각각 연결되어 있다. 

class Node:
    def __init__(self):
        self.value = 0
        self.left_child = None
        self.right_child = None

 

간단하게 구현해본 이진트리 구조의 노드이다. LC와 RC가 연결되면 된다.

class BinaryTree:
    def __init__(self):
        self.root = None #Linked list에선 head가 필수였듯이 root 필수
        
bt = BinaryTree()
bt.root = Node(value = 1) #value가 1인 root 노드 생성
bt.root.left = Node(value = 2) #왼쪽에 value가 2인 노드(child) 생성
bt.root.right = Node(value = 3) #오른쪽에 value가 3인 노드(child) 생성
bt.root.left.left = Node(value = 4) #왼쪽의 왼쪽에 value가 4인 노드(child) 생성
bt.root.right.right = Node(value = 5) #오른쪽의 오른쪽에 value가 5인 노드(child) 생성

 

이런식으로 트리를 쌓아가면 다음과 같은 그림이 그려진다.

파이썬 예시 코드의 트리

이런식으로 트리를 구축해나갈 수 있다. 이진트리이기 때문에 LC, RC에 연결이 되는 모습이다.

 

Tree 총정리

 

장점

1. 계층구조라서, 실세계의 구조를 잘 표현할 수 있다.

2. 이진트리는 탐색 속도가 매우 빠르다.

 

단점

1. 데이터 삽입과 삭제가 어렵다. 특히 중간 노드의 수정과 삽입이 어렵다.

2. 구조를 잘 고려해야, 트리순회에서 시간이 소요되지 않는다.

.

 

총평

우리가 일반적으로 생각하는 대로 동작하지만, 구조를 잘 짜야함!