06. 트리(Tree)

트리(Tree)는 계층구조(Hierarchical Structure)로 자료를 저장한다. 여기서 계층 구조란 트리를 구성하는 노드가 부모-자식(Parent-Child)관계라는 의미이다. 즉, 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조를 말한다. 이러한 계층구조의 대표적인 예로 컴퓨터의 폴더 구조를 들 수 있다.

트리는 하나의 부모 노드에 여러 개의 자식 노드가 연결되어 있다. 그래서 트리를 구성하는 부모-자식 노드의 관계가 일대일이 아니라는 점에서 비선형 자료구조이다. 반대로 각 노드의 부모 노드는 모두 1개라는 점은 주의하기 바란다.

트리의 개념

트리(Tree)는 노드(Node)와 간선(Edge)의 집합이다. 보통 노드는 일반적으로 모델링하려는 시스템의 객체(Object)를 나타낸다. 간선은 이러한 객체들 사이의 부모-자식 관계를 정의한다. 우선 트리를 구성하는 기본 요소인 노드들을 몇가지 기준에 의해 종류를 나누어 볼 수 있다.

구분	용어	내용
트리에서 위치	Root Node	트리의 첫 번째 노드
	Leaf Node (Terminal Node)	자식 노드가 없는 노드
	Internal Node	자식 노드가 있는 노드
노드 사이의 관계	Parent Node	부모 노드와 자식 노드는 간선으로 연결되어 있다
	Child Node
	Ancestor Node	루트 노드로부터 부모 노드까지의 경로상의 있는 모든 노드
	Descendant Node	특정 노드의 아래에 있는 모든 노드
	Sibling Node	같은 부모 노드의 자식 노드

기본적으로 사용되는 노드의 몇가지 속성은 아래와 같다.

용어	내용
레벨(Level)	루트 노드부터의 거리
높이(Height)	루트 노드로부터 가장 먼 거리에 있는 자식 노드의 높이에 1을 더한 값
차수(Degree)	한 노드가 가지는 자식 노드의 개수

 

이진 트리(Binary Tree)

이진 트리(Binary Tree)는 모든 노드의 차수가 2 이하인 트리를 말한다. 이진트리는 형태에 따라 포화 이진 트리, 완전 이진 트리, 편향 이진 트리로 나눌 수 있다. 트리의 현태는 레벨과 노드 수에 따라 결정된다.