Tree

Jina·2020년 4월 27일

data structure

Session

목록 보기

10/12

Tree

트리 자료구조는 데이터를 거꾸로된 나무 형태로 저장하는 모양
트리는 노드로 이루어진 자료 구조
트리는 하나의 루트 노드를 갖고 있음
루트 노드는 0개 이상의 자식 노드를 갖고 있음
그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨
대상정보의 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용하는 비선형 자료구조
데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현
트리는 그래프(Graph)의 한 종류이며 사이클이 없음
binary tree(이진 트리)구조가 대표적
이진 트리는 두개의 자식노드를 가진 트리 형태

사용 예시

계층적인 관계의 표현에 사용
윈도우와 리눅스의 파일시스템 구조 역시 트리로 표현됨
대용량의 데이터를 저장할 때 많이 쓰임

용어

노드: 트리 구조의 교점 / Node가 데이터를 가지고 있고 또한 자식노드를 가지고 있음
루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
내부(internal) 노드: 단말 노드가 아닌 노드
간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

개념확인 문제

답

객관식 1 : A
객관식 2 : B
객관식 3 : E, F
객관식 4 : 4
객관식 5 : level 2
객관식 6 : 2
객관식 7 : E, G, H, J, K

트리의 속성

루트 노드를 제외한 모든 노드는 단 하나의 부모노드만을 가짐 (트리의 속성 중 가장 중요한 것)

트리의 탐색

트리의 순회 : 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 의미

노드를 방문하는 순서에 따라 전위순회, 중위순회, 후위순회

전위순회(preorder)

루트노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회하는 방식
깊이 우선 순회

중위순회(inorder)

루트노드에서 시작해서 왼쪽 서브트리 - 노드 - 오른쪽 서브트리 순으로 순회하는 방식
대칭 순회

후위순회(postorder)

루트노드에서 시작해서 왼쪽 서브트리 - 오른쪽 서브트리 - 노드 순으로 순회하는 방식

이진 트리와 이진 탐색 트리

이진 트리는 최대 차수가 2인 트리
이는 하나의 노드에 LEFT or RIGHT만 존재한다고 표현합
이진 트리에는 여러 유형이 존재

이진 트리의 종류

편향 이진 트리(skewed binary tree)

편향이진 트리는 하나의 차수로만 이뤄져 있는 경우를 의미

단점
이런 구조는 배열과 같은 선형 구조이기 때문에 Leaf Node (가장 끝 노드)탐색시 모두 읽어 들여야 해서 효율이 떨어짐
이러한 단점을 보완하기 위해 '높이 균형 트리'라는 것이 있음

노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

전 이진 트리 VS 완전 이진 트리 VS 포화 이진 트리

전 이진 트리 (Full Binary Tree)

전 이진 트리는 모든 노드가 0개 혹은 2개의 자식노드를 가지는 트리를 말한다. 포화 이진 트리의 하위종류이다.

완전 이진 트리(Complete Binary Tree)

포화 이진트리와 같은 개념으로 생성하지만 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미

트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있음
마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

포화 이진 트리(Perfect Binary Tree)

Leaf Node를 제외한 모든 노드의 차수가 두개로 이뤄진 경우를 의미
이 경우에는 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있어 개수 파악이 용이하다는 장점이 있음

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작음
이러한 특성 덕분에 이진 탐색 트리에서는 한번 확인할 때 마다 보아야 하는 원소의 개수가 절반씩 줄어듬
'완전 이진 트리'인 경우 탐색시간에 O(logN)의 시간복잡도를 가짐
이진 탐색 트리에서 탐색(traverse)을 할 때는 찾고자 하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 찾고자 하는 값이 부모 노드보다 클 경우 오른쪽 자식으로 이어 나가면서 방문함
이진 탐색이 항상 동작하도록 구현하여 탐색 속도를 극대화 시킨 자료구조